Jugal Garg

For More Information

• Jugal Garg's homepage

Resident Instruction

• IE 310 Deterministic Models in Optimization, Spring 2023
• IE 598 Topics in Game Theory and Fair Division, Spring 2021, Spring 2022, Spring 2024
• IE 405 Computing for ISE, Fall 2019, Fall 2020, Fall 2021, Fall 2022, Fall 2023, Fall 2024
• SE 494 Senior Design Project, Spring 2018, Fall 2018, Spring 2019, Spring 2021, Fall 2021, Spring 2022
• IE 598 Games, Markets, and Mathematical Programming, Fall 2016, Fall 2017, Spring 2020
• IE 498 Computing for ISE, Spring 2016, Spring 2017, Spring 2018, Fall 2018
• CS 8803 Advanced Topics in Algorithmic Game Theory, Spring 2013 (Georgia Tech)

Research Interests

• Computational Aspects of Economics and Game Theory
• Design and Analysis of Algorithms
• Mathematical Programming
• Fair Division

Selected Articles in Journals

• Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. Operations Research (accepted).
• Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. Improving EFX Guarantees through Rainbow Cycle Number. Mathematics of Operations Research (accepted).
• Jugal Garg, Edin Husić, and László Végh. Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands and their Applications. ACM Transactions on Economics and Computation (accepted).
• Jugal Garg and Aniket Murhekar. Computing Pareto-Optimal and Almost Envy-Free Allocations of Indivisible Goods. Journal of Artificial Intelligence Research 80: 1-25 (2024).
• Jugal Garg, Thorben Trobst, and Vijay Vazirani. One-Sided Matching Markets with Endowments: Equilibria and Algorithms. Autonomous Agents and Multi-Agent Systems 38(2): 40 (2024).
• Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Satiation in Fisher Markets and Approximation of Nash Social Welfare. Mathematics of Operations Research 49(2): 1109-1139 (2024).
• Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX Exists for Three Agents. Journal of the ACM 71(1): 4:1-4:27 (2024).
• Jugal Garg, Martin Hoefer, Peter McGlaughlin, and Marco Schmalhofer. Competitive Equilibria with a Constant Number of Chores. Journal of Artificial Intelligence Research 78: 1201-1219 (2023).
• Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings. ACM Transactions on Algorithms, ACM Trans. Algorithms 19(4): 36:1-36:25 (2023).
• Jugal Garg and László Végh. A Strongly Polynomial Algorithm for Linear Exchange Markets. Operations Research, 71(2): 487-505 (2023).
• Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. A Complementary Pivot Algorithm for Competitive Allocation of a Mixed Manna. Mathematics of Operations Research 48(3): 1630-1656 (2023).
• Jugal Garg and Aniket Murhekar. Computing Fair and Efficient Allocations with Few Utility Values, Theoretical Computer Science, 962: 113932 (2023).
• Bhaskar Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn. Fair Division of Indivisible Goods for a Class of Concave Valuations. Journal of Artificial Intelligence Research, 74: 111-142 (2022).
• Timothy Murray, Jugal Garg, and Rakesh Nagi. Prize-Collecting Multi-Agent Orienteering: Price of Anarchy Bounds and Solution Methods. IEEE Transactions on Automation Science and Engineering, 19(1): 531-544 (2022).
• Jugal Garg, Edin Husić, and László Végh. Approximating Nash Social Welfare under Rado Valuations. SIGecom Exch. 19(1): 45-51 (2021).
• Bharat Adsul, Jugal Garg, Ruta Mehta, Milind Sohoni, and Bernhard von Stengel. Fast Algorithms for Rank-1 Bimatrix Games, Operations Research, 69(2): 613-631 (2021).
• Jugal Garg and Setareh Taki. An Improved Approximation Algorithm for Maximin Shares. Artificial Intelligence, 300: 103547 (2021).
• Timothy Murray, Jugal Garg, and Rakesh Nagi. Limited-Trust Equilibria. European Journal of Operational Research, 289(1): 364-380 (2021).
• Jugal Garg and Peter McGlaughlin. Improving Nash Social Welfare Approximations. Journal of Artificial Intelligence Research, 68: 225-245 (2020) .
• Omkar Thakoor, Jugal Garg, and Rakesh Nagi. Multi-Agent UAV Routing: A Game Theory Analysis with Tight Price of Anarchy Bounds. IEEE Transactions on Automation Science and Engineering, 17(1): 100-116 (2020).
• Xiaohui Bei, Jugal Garg, and Martin Hoefer. Ascending-Price Algorithms for Unknown Markets. ACM Transactions on Algorithms, 15(3): 37:1-37:33 (2019).
• Xiaohui Bei, Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Earning and Utility Limits in Fisher Markets. ACM Transactions on Economics and Computation, 7(2): 10:1-10:35 (2019).
• Jugal Garg, Ruta Mehta, Vijay Vazirani, and Sadra Yazdanbod. ETR-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria. ACM Transactions on Economics and Computation, 6(1): 1:1-1:23 (2018).
• Jugal Garg, Ruta Mehta, Vijay V. Vazirani, "Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm," Math. Oper. Res., 43(3): 996-1024 (2018).
• Jugal Garg. Market Equilibrium under Piecewise Leontief Concave Utilities. Theoretical Computer Science, 703: 55-65 (2017).
• Reshmina William, Jugal Garg, and Ashlynn Stillwell. A Game Theory Analysis of Green Infrastructure Implementation Policies. Water Resources Research, 53:9 8003-8019 (2017).
• Jugal Garg, Ruta Mehta, Vijay V. Vazirani, "Dichotomies in Equilibrium Computation, and Membership of PLC markets in FIXP," Theory of Computing, 12(1): 1-25 (2016).
• Nikhil Devanur, Jugal Garg, László Végh, "A Rational Convex Program for Linear Arrow-Debreu Markets," ACM Transactions on Economics and Computation, 5(1): 6:1-6:13 (2016).
• Jugal Garg, Ruta Mehta, Milind Sohoni, Vijay V. Vazirani, "A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities," SIAM Journal on Computing 44(6): 1820-1847 (2015).
• Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta and Milind Sohoni. A Simplex-like Algorithm for Fisher Markets. Current Science, 103(9): 1033-1042 (2012).
• Narayan Rangaraj, Milind Sohoni, Prashant Puniya, and Jugal Garg. Rake Linking for Suburban Train Services. Opsearch, 43(2), (2006).

Refereed Conference Papers and Presentations

• Jugal Garg, Yixin Tao, and L�szl� V�gh. Approximating Competitive Equilibrium by Nash Welfare. To appear in the Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025. (29% acceptance rate)
• Jugal Garg, Aniket Murhekar, and John Qin. Weighted EF1 and PO Allocations with Few Types of Agents or Chores. Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), 2024. (15% acceptance rate)
• Hannaneh Akrami and Jugal Garg. Breaking the 3/4 Barrier for Approximate Maximin Share. Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024. (29% acceptance rate)
• Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. Proceedings of the 24th ACM Conference on Economics and Computation (EC), 2023. (26% acceptance rate)
• Hannaneh Akrami, Jugal Garg, Eklavya Sharma, and Setareh Taki. Simplification and Improvement of MMS Approximation. To appear in the Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), 2023. (15% acceptance rate)
• Jugal Garg, Aniket Murhekar, and John Qin. Improving Fairness and Efficiency Guarantees for Allocating Indivisible Chores. To appear in the Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), 2023. (15% acceptance rate)
• Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, Eklavya Sharma, and Giovanna Varricchio Existence and Computation of Epistemic EFX. To appear in the Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), 2023. (15% acceptance rate)
• Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. Fair and Efficient Allocation of Indivisible Chores with Surplus. To appear in the Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), 2023. (15% acceptance rate)
• Jugal Garg, Edin Husić, Wenzheng Li, László Végh, and Jan Vondrák. Approximating Nash Social Welfare by Matching and Local Search. Proceedings of the 55th Symposium on Theory of Computing (STOC), 2023. (32% acceptance rate)
• Jugal Garg, Thorben Tröbst, and Vijay Vazirani. A Nash-Bargaining-Based Mechanism for One-Sided Matching Markets under Dichotomous Utilities. Proceedings of the 22nd International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2023. (45% acceptance rate)
• Jugal Garg, Edin Husić, Aniket Murhekar, and László Végh. Tractable Fragments of the Maximum Nash Welfare Problem. To appear in the Proceedings of the 18th Conference on Web and Internet Economics (WINE), 2022. (30% acceptance rate)
• Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness. To appear in the Proceedings of the 23rd ACM Conference on Economics and Computation (EC), 2022. (27% acceptance rate)
• Jugal Garg, Thorben Tröbst, and Vijay Vazirani. One-Sided Matching Markets with Endowments: Equilibria and Algorithms. Proceedings of the 21st International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2022. (26% acceptance rate)
• Jugal Garg, Aniket Murhekar, and John Qin. Fair and Efficient Allocations of Chores under Bivalued Preferences. Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 2022. (15% acceptance rate)
• Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. On the Existence of Competitive Equilibrium with Chores. Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), 2022. (49% acceptance rate)
• Jugal Garg, Yixin Tao, and László Végh. Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets. Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022. (30% acceptance rate)
• Jugal Garg, Pooja Kulkarni, and Aniket Murhekar. On Fair and Efficient Allocations of Indivisible Public Goods. Proceedings of the 41st Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2021. (37% acceptance rate)
• Jugal Garg, Edin Husić, and László Végh. Approximating Nash Social Welfare under Rado Valuations. Proceedings of the 53rd Symposium on Theory of Computing (STOC), 2021. (28% acceptance rate)
• Jugal Garg and Aniket Murhekar. Computing Fair and Efficient Allocations with Few Utility Values. Proceedings of the 14th International Symposium on Algorithmic Game Theory (SAGT), 2021. (41% acceptance rate) Invited to the TCS Special Issue for SAGT 2021.
• Jugal Garg, Martin Hoefer, Peter McGlaughlin, and Marco Schmalhofer. When Dividing Mixed Manna is Easier than Dividing Goods: Competitive Equilibria with a Constant Number of Chores. Proceedings of the 14th International Symposium on Algorithmic Game Theory (SAGT), 2021. (41% acceptance rate)
• Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. Improving EFX Guarantees through Rainbow Cycle Number. Proceedings of the 22nd ACM Conference on Economics and Computation (EC), 2021. (26% acceptance rate)
• Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. Competitive Allocation of a Mixed Manna. Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021. (28% acceptance rate)
• Bhaskar Ray Chaudhury, Jugal Garg, and Ruta Mehta. Fair and Efficient Allocations under Subadditive Valuations. Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021. (21% acceptance rate)
• Jugal Garg and Aniket Murhekar. On Fair and Efficient Allocations of Indivisible Goods. Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021. (21% acceptance rate)
• Jugal Garg, Edin Husić, and László Végh. Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands and their Applications. Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS), 2021. (24% acceptance rate)
• Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings. Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020. (30% acceptance rate)
• Jugal Garg and Peter McGlaughlin. Computing Competitive Equilibria with Mixed Manna. Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2020. (23% acceptance rate)
• Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX Exists for Three Agents. Proceedings of the 21st ACM Conference on Economics and Computation (EC), 2020. (20% acceptance rate)
• Jugal Garg and Setareh Taki. An Improved Approximation Algorithm for Maximin Shares. Proceedings of the 21st ACM Conference on Economics and Computation (EC), 2020. (20% acceptance rate)
• Jugal Garg, Peter McGlaughlin, and Setareh Taki. Approximating Maximin Share Allocations. Proceedings of the Symposium on Simplicity in Algorithms (SOSA), 2019. (29% acceptance rate)
• Jugal Garg and László Végh. A Strongly Polynomial Algorithm for Linear Exchange Markets. Proceedings of the 51st Symposium on Theory of Computing (STOC), 2019. (27% acceptance rate)
• Jugal Garg and Peter McGlaughlin. Improving Nash Social Welfare Approximations. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 2019. (18% acceptance rate)
• Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Approximating the Nash Social Welfare with Budget-Additive Valuations. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018. (33% acceptance rate)
• Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay Vazirani and Sadra Yazdanbod. A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018. (33% acceptance rate)
• Rahul Swamy, Timothy Murray, and Jugal Garg. Network Cost-Sharing Games: Equilibrium Computation and Applications to Election Modeling. Proceedings of the 12th International Conference on Combinatorial Optimization and Applications (COCOA), 2018. (47% acceptance rate)
• Jugal Garg and Peter McGlaughlin. A Truthful Mechanism for Interval Scheduling. Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT), 2018. (35% acceptance rate)
• Bhaskar Chaudhuri, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn. On Fair Division of Indivisible Items. Proceedings of the 38th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2018. (35% acceptance rate)
• Xiaohui Bei, Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Earning Limits in Fisher Markets with Spending-Constraint Utilities. Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT), 2017. (45% acceptance rate)
• Jugal Garg, Ruta Mehta, Vijay Vazirani, and Sadra Yazdanbod. Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria. Proceedings of the 49th Symposium on Theory of Computing (STOC), 2017. (24% acceptance rate)
• Xiaohui Bei, Jugal Garg, and Martin Hoefer. Ascending-Price Algorithms for Unknown Markets. Proceedings of the 17th ACM Conference on Economics and Computation (EC), 2016 (33% acceptance rate)
• Xiaohui Bei, Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Computing Equilibria in Markets with Budget-Additive Utilities. Proceedings of the 24th European Symposia on Algorithms (ESA), 2016 (27% acceptance rate)
• Xiaohui Bei, Wei Chen, Jugal Garg, Martin Hoefer, and Xiaoming Sun. Learning Market Parameters using Aggregate Demand Queries. Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), 2016. (26% acceptance rate)
• Ran Duan, Jugal Garg, and Kurt Mehlhorn. An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016. (28% acceptance rate)
• Jugal Garg and Ravi Kannan. Markets with Production: A Polynomial Time Algorithm and a Reduction to Exchange. Proceedings of the 16th ACM Conference on Economics and Computation (EC), 2015. (33% acceptance rate)
• Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. ETR-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria. Proceedings of the 42nd Intl. Colloq. on Automata, Languages and Programming (ICALP), 2015. (28% acceptance rate)
• Jugal Garg. Market Equilibrium under Piecewise Leontief Concave Utilities. Proceedings of 10th Conference on Web and & Internet Economics (WINE), 2014. (43% acceptance rate)
• Jugal Garg, Ruta Mehta, Milind Sohoni, and Vijay V. Vazirani. A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities. Proceedings of 44th Symposium on Theory of Computing (STOC), 2012. (29% acceptance rate)
• Jugal Garg, Albert X. Jiang, and Ruta Mehta. Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses. Proceedings of Workshop on Internet & Network Economics (WINE), 2011. (31% acceptance rate)
• Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta, and Milind Sohoni. Nash Equilibria in Fisher Market. Proceedings of International Symposium on Algorithmic Game Theory (SAGT), 2010. (42% acceptance rate)
• Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta, and Milind Sohoni. A Simplex-like Algorithm for Fisher Markets. Proceedings of International Symposium on Algorithmic Game Theory (SAGT), 2010. (42% acceptance rate)
• Jugal Garg and Vijay V. Vazirani. On Computability of Equilibria in Markets with Production. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014. (28% acceptance rate)
• Jugal Garg, Ruta Mehta, and Vijay V. Vazirani. Dichotomies in Equilibrium Computation, and Complementary Pivot Algorithms for a New Class of Non-Separable Utility Functions. Proceedings of 46th Symposium on Theory of Computing (STOC), 2014. (29% acceptance rate)
• Jugal Garg, Ruta Mehta, Milind Sohoni, and Nisheeth Vishnoi. Towards Polynomial Simplex-Like Algorithms for Market Equilibria. Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013. (29% acceptance rate)
• Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni. Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm. Proceedings of 43rd Symposium on Theory of Computing (STOC), 2011. (28% acceptance rate)

Honors

• Algorithms and Randomness Center (ARC) Postdoctoral Fellowship, Georgia Tech, September 2012 - August 2014
• Microsoft Research India Rising Star Award, 2011

Teaching Honors

• Engineering Council Outstanding Advisor, Top 10% of College, 2024
• The ISE Department Head Teaching Award, 2023
• List of Teachers Ranked as Excellent, Fall 2022
• List of Teachers Ranked as Excellent, Spring 2021 (Spring 2021)
• James Franklin Sharp Outstanding Teaching Award in Industrial Engineering 2019  ( May  2019 )
• List of Teachers Ranked as Excellent, Fall 2018 (Fall 2018)
• List of Teachers Ranked as Excellent, Spring 2016 (Spring 2016)
• Collins Scholar, Spring 2016 (Spring 2016)

Other Honors

• Senior Design - Spring 2024 Hudson Technologies, Inc: Multisite Process and Layout Optimization for Facility Consolidation - Bernt O. Larson Award - Second Place