|
My main research interests are in computational aspects of economics and game theory, design and analysis of algorithms, and mathematical programming. Currently, I am working on designing fast algorithms for computing market equilibria which have applications in network flow and fair division problems. I received my BTech and PhD in Computer Science from IIT-Bombay. Later, I was a postdoc in Algorithms and Randomness Center at Georgia Tech, and in Algorithms and Complexity group at Max-Planck-Institut für Informatik, Saarbrücken. For more information, please see my CV.
My research is funded by NSF CRII Award.
Recent/Upcoming Activities
- Program Committee: EC 2020, AAAI 2020, SODA 2020, ESA 2019, EC 2019, FSTTCS 2018, EC 2018, WINE 2017, WINE 2016
- INFORMS Annual Meeting, Seattle, October 20 - 23, 2019
- Online and Matching-Based Market Design, Simons Institute, UC Berkeley, August 21 - October 4, 2019
- Tutorial (co-organized) on Nash welfare, Market Equilibrium, and Stable Polynomials at STOC 2019, Phoenix, June 23-26, 2019
- Invited talk at UCI, Irvine, May 16, 2019
- Invited talk at LSE, London, UK, March 12-28, 2019
- Invited talk at Purdue University, West Lafayette, October 17, 2018
- Plenary talk at Bellairs Workshop on Algorithmic Game Theory, Barbados, April 7-13, 2018
Teaching
- IE 498: Computing for ISE, Spring 2016, Spring 2017, Spring 2018, Fall 2018, Fall 2019
- IE 598: Games, Markets, and Mathematical Programming, Fall 2016, Fall 2017 (Lecture Notes)
- CS 8803: Advanced Topics in Algorithmic Game Theory, Spring 2013 (co-taught at Georgia Tech)
Students
Peter McGlaughlin
Setareh Taki
Timothy Murray (co-advised with Rakesh Nagi)
Rucha Kulkarni (CS, Advisor: Ruta Mehta)
Pooja Kulkarni (CS)
Aniket Murhekar (MS, CS; Siebel Scholar 2020)
Xiao Tan (BA, Economics)
Omkar Thakoor (MS, CS) (graduated in May 2017; now a Ph.D. student at USC)
Selected Publications (We have implemented some of our algorithms. Source code is available on request, just send me an email)
Preprints
Refereed Journal Papers
- Bharat Adsul, Jugal Garg, Ruta Mehta, Milind Sohoni, and Bernhard von Stengel. Fast Algorithms for Rank-1 Bimatrix Games, Operations Research, forthcoming, 2019.
- Jugal Garg and Peter McGlaughlin. Improving Nash Social Welfare Approximations. Journal of Artificial Intelligence Research, forthcoming, 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).
- Xiaohui Bei, Jugal Garg, and Martin Hoefer. Ascending-Price Algorithms for Unknown Markets. ACM Transactions on Algorithms, 15(3): 37:1-37:33 (2019).
- 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, DOI: 10.1109/TASE.2019.2902360 (2019).
- Jugal Garg, Ruta Mehta, and Vijay Vazirani. Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm. Mathematics of Operations Research, 43(3): 996-1024 (2018).
- Jugal Garg, Ruta Mehta, Vijay Vazirani, and Sadra Yazdanbod. EXISTS-R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria. ACM Transactions on Economics and Computation, 6(1): 1:1-1:23 (2018).
- 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. Market Equilibrium under Piecewise Leontief Concave Utilities. Theoretical Computer Science, 703: 55-65 (2017).
- Nikhil Devanur, Jugal Garg, and 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, and Vijay Vazirani. Dichotomies in Equilibrium Computation, and Membership of PLC markets in FIXP. Theory of Computing, 12(1): 1-25 (2016).
- Jugal Garg, Ruta Mehta, Milind Sohoni, and Vijay Vazirani. A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities. SIAM Journal on Computing 44(6): 1820-1847 (2015).
Refereed Conference Papers
- Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings. To Appear in the Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020.
- Jugal Garg and Peter McGlaughlin. Improving Nash Social Welfare Approximations. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 2019.
- 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.
- Jugal Garg, Peter McGlaughlin, and Setareh Taki. Approximating Maximin Share Allocations. Proceedings of the Symposium on Simplicity in Algorithms (SOSA), 2019.
- Bhaskar Chaudhury, 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.
- 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.
- Jugal Garg and Peter McGlaughlin. A Truthful Mechanism for Interval Scheduling. Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT), 2018.
- 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.
- 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.
- 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.
- 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.
- Ran Duan, Jugal Garg, and Kurt Mehlhorn. An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016.
- Xiaohui Bei, Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Computing Equilibria in Markets with Budget-Additive Utilities. Proceedings of the 24th European Symposium on Algorithms (ESA), 2016.
- 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.
- 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.
- Jugal Garg, Ruta Mehta, Vijay Vazirani, and Sadra Yazdanbod. ETR-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria. Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), 2015.
- 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.
- Jugal Garg, Ruta Mehta, and Vijay Vazirani. Dichotomies in Equilibrium Computation, and Complementary Pivot Algorithms for a New Class of Non-Separable Utility Functions. Proceedings of the 46th Symposium on Theory of Computing (STOC), 2014.
- Jugal Garg and Vijay Vazirani. On Computability of Equilibria in Markets with Production. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.
- Jugal Garg. Market Equilibrium under Piecewise Leontief Concave Utilities. Proceedings of the 10th Conference on Web and & Internet Economics (WINE), 2014.
- 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.
- 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 the 44th Symposium on Theory of Computing (STOC), 2012.
- Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni. Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm. Proceedings of the 43rd Symposium on Theory of Computing (STOC), 2011.
- Jugal Garg, Albert Jiang and Ruta Mehta. Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses. Proceedings of the 7th Workshop on Internet & Network Economics (WINE), 2011.
- Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta, and Milind Sohoni. A Simplex-like Algorithm for Fisher Markets. Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT), 2010.
- Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta, and Milind Sohoni. Nash Equilibria in Fisher Market. Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT), 2010.
|
