A | B | C | D | E | F 
 G | H | I | J | K | L | M 
 N | O | P | Q | R | S | T 
 U | V | W | X | Y | Z 

max planck institut
informatik

Homepage

Jugal Garg

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 304
66123 Saarbrücken
Germany

Email: jgarg@mpi-inf.mpg.de
Phone: +49 681 9325 1004
Fax: +49 681 9325 199

---

Research Interests

• Computational Aspects of Economics and Game Theory
• Combinatorial Optimization
• Design and Analysis of Algorithms

---

Publications

• Ascending-Price Algorithms for Unknown Markets
  Xiaohui Bei, Jugal Garg and Martin Hoefer
  


• A Market for Scheduling, with Applications to Cloud Computing
  Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod
  


• On the Complexity of Computing Approximate Market Equilibria
  Jugal Garg
  


• Leontief Exchange Markets Can Solve Multivariate Polynomial Equations, Yielding FIXP and ETR Hardness
  Jugal Garg, Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod
  


• A Rational Convex Program for Linear Arrow-Debreu Markets
  Nikhil R. Devanur, Jugal Garg and László A. Végh
  


• Learning Market Parameters using Aggregate Demand Queries
  Xiaohui Bei, Wei Chen, Jugal Garg, Martin Hoefer and Xiaoming Sun
  AAAI Conference on Artificial Intelligence (AAAI), 2016.


• An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
  Ran Duan, Jugal Garg and Kurt Mehlhorn
  ACM-SIAM Symp. on Discrete Algorithms (SODA), 2016.


• ETR-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria
  Jugal Garg, Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod
  Intl. Colloq. on Automata, Languages and Programming (ICALP), 2015.


• Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange
  Jugal Garg and Ravi Kannan
  ACM Conf. on Economics and Computation (EC), 2015.


• Market Equilibrium under Piecewise Leontief Concave Utilities
  Jugal Garg
  Conf. on Web and Internet Economics (WINE), 2014.


• Dichotomies in Equilibrium Computation, and Complementary Pivot Algorithms for a New Class of Non-Separable Utility Functions
  Jugal Garg, Ruta Mehta and Vijay V. Vazirani
  ACM Symp. on Theory of Computing (STOC), 2014.


• On Computability of Equilibria in Markets with Production
  Jugal Garg and Vijay V. Vazirani
  ACM-SIAM Symp. on Discrete Algorithms (SODA), 2014.


• Towards Polynomial Simplex-Like Algorithms for Market Equilibrium
  Jugal Garg, Ruta Mehta, Milind Sohoni and Nisheeth Vishnoi
  ACM-SIAM Symp. on Discrete Algorithms (SODA), 2013.


• A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities
  Jugal Garg, Ruta Mehta, Milind Sohoni and Vijay V. Vazirani
  SIAM J. Comput. 44(6), 2015.
  Conf. Version: ACM Symp. on Theory of Computing (STOC), 2012.


• Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses
  Jugal Garg, Albert X. Jiang and Ruta Mehta
  Workshop on Internet and Network Economics (WINE), 2011.


• Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm
  Bharat Adsul, Jugal Garg, Ruta Mehta and Milind Sohoni
  ACM Symp. on Theory of Computing (STOC), 2011.


• Nash Equilibria in Fisher Market
  Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta and Milind Sohoni
  Symp. on Algorithmic Game Theory (SAGT), 2010.


• A Simplex-like Algorithm for Fisher Markets
  Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta and Milind Sohoni
  Special issue on Game Theory of Current Science, 103(9), 1033-1042, 2012
  Conf. Version: Symp. on Algorithmic Game Theory (SAGT), 2010.


• Rake Linking for Suburban Train Services
  Narayan Rangaraj, Milind Sohoni, Prashant Puniya and Jugal Garg
  Opsearch, 43(2), 2006.

---

Recent/Upcoming Talks/Tutorials

• ICCOPT 2016, Tokyo, Japan, Aug 2016
  
• Bellairs Workshop on Algorithmic Game Theory, Barbados, Apr 9-15, 2016
  
• Game Theory Workshop, Bonn, Germany, Dec 2015
  
• Oberwolfach Workshop on Complexity Theory, Germany, Nov 2015
  
• Operations Research Seminar , UCL, Louvain-la-Neuve, Belgium, Oct 6, 2015
  
• Operations Research Seminar, LSE, London, UK, Sep 16, 2015
  
• ISMP 2015, Pittsburgh, USA, July 2015
  
• ICALP 2015, Kyoto, Japan, July 2015
  
• EC 2015, Portland, USA, June 2015
  
• WINE 2014, Beijing, China, Dec 14-17, 2014
  
• CSE Seminar IIT-Bombay, Mumbai, India, Dec 12, 2014
  
• IMPECS School on Algorithmic Game Theory, Sangli, India, Dec 8-12, 2014
  
• Dagstuhl Workshop on Equilibrium Computation, Germany, Aug 17-22, 2014
  

---

Teaching

• Advanced Topics in Algorithmic Game Theory
  (co-taught with Ruta Mehta and Georgios Piliouras)
  Georgia Tech, Spring 2013

---

Recent Positions

• Aug 2014 - present
  Postdoctoral Fellow, Max-Planck-Institut für Informatik, Saarbrücken, Germany


• Sep 2012 - Aug 2014
  ARC postdoctoral fellow, Georgia Tech, Atlanta, USA
  

---

Education

• July 2007 - Aug 2012
  PhD student, Indian Institute of Technology, Bombay, India.
  

---

Hobbies

• Long distance running

• Jugal Garg:
  • Research Interests
  • Publications
  • Teaching
  • Recent Positions
  • Education

• Doctoral Research Program
• Max Planck Center
• Cluster of Excellence (MMCI)
• Computer Science Cluster