PhD Thesis

Nash Equilibrium Computation in Various Games
Dept. of CSE, IIT-Bombay, Aug 2012.


Publications

A Market Model for Scheduling, and a Polynomial-time Algorithm for Computing Equilibria
Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod
Preprint, 2017.
Nash Social Welfare Approximation for Strategic Agents
Simina Branzei, Vasilis Gkatzelis, and Ruta Mehta
Submitted, 2017.
Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria
Jugal Garg, Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod.
Accepted to STOC 2017.
Mutation, Sexual Reproduction and Survival in Dynamic Environments
Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani
Accepted to ITCS, 2017.
Multilinear Games
Hau Chan, Albert Xin Jiang, Kevin Leyton-Brown, and Ruta Mehta
WINE, 2016.
To Give or not to Give: Fair Division with Strict Preferences
Simina Branzei, Yuezhou Lv, and Ruta Mehta
IJCAI, 2016.
Get Me to My GATE On Time: Efficiently Solving General-Sum Bayesian Threat Screening Games
Aaron Schlenker, Matthew Brown, Arunesh Sinha, Milind Tambe, and Ruta Mehta
ECAI, 2016.
The Complexity of Genetic Diversity: Sex with Two Chromosomes is Advantageous but Unpredictable
Ruta Mehta, Ioannis Panageas, Georgios Piliouras, and Sadra Yazdanbod
ESA, 2016.
Settling Some Open Problems on Symmetric Nash Equilibria.
Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod
SAGT, 2015.
Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and a Conjecture of Haploid Genetics
Ruta Mehta, Ioannis Panageas and Georgios Piliouras
ITCS, 2015.
ETR-Completeness of Decision Versions of 3-Nash
Jugal Garg, Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod.
ICALP, 2015.
Learning Economic Parameters from Revealed Preferences
Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner and Vijay V. Vazirani.
Accepted to WINE, 2014.
To Save Or Not To Save: The Fisher Game
Ruta Mehta, Nithum Thain, Laszlo A. Vegh and Adrian Vetta.
Accepted to WINE, 2014.
An Incentive Compatible, Efficient Market for Air Traffic Flow Management.
Ruta Mehta and Vijay V. Vazirani.
Manuscript.
Constant Rank Bimatrix Games are PPAD-hard.
Ruta Mehta.
In proceedings of STOC, 2014 (Invited to SICOMP).
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.
Under revision in MOR. (Preliminary version appeared in STOC'14).
Exchange Markets: Strategy meets Supply-Awareness
Ruta Mehta and Milind Sohoni.
In proceedings of WINE, 2013.
Towards Polynomial Simplex-Like Algorithms for Market Equilibrium.
Jugal Garg, Ruta Mehta, Milind Sohoni and Nisheeth Vishnoi.
In proceedings of SODA, 2013.
The Weighted Majority Algorithm does not Converge in Nearly Zero-sum Games.
Maria Florina Balcan, Florin Constantin and Ruta Mehta
In ICML 2012 workshop on Markets Mechanisms and Multi-Agent Models.
A Complementary Pivot Algorithm for Market Equilibrium under Separable Piecewise-Linear Concave Utilities.
Jugal Garg, Ruta Mehta, Milind Sohoni and Vijay V. Vazirani
SIAM Journal on Computing, 2015. A preliminary version appeared in Proceedings of STOC, 2012.
Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses.
Jugal Garg, Albert X. Jiang and Ruta Mehta
In the Proceedings of WINE, 2011.
Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm.
Bharat Adsul, Jugal Garg, Ruta Mehta and Milind Sohoni
In the Proceedings of STOC, 2011.
A short write-up describing the algorithm in hindsight may be found here
Nash Equilibria in Fisher Market.
Bharat Adsul, Ch. Sobhan, Jugal Garg, Ruta Mehta and Milind Sohoni
In the Proceedings of SAGT, 2010.
A Simplex-like Algorithm for Fisher Markets.
Bharat Adsul, Ch. Sobhan, Jugal Garg, Ruta Mehta and Milind Sohoni
Special issue on Game Theory of Current Science, 103(9), pp 1033-1042, 2012.
Conference Version: In the Proceedings of SAGT, 2010.
Federating Social Networks for Analysis.
Ruta Mehta, Seema Nagar, Natwar Modani, Kuntal Dey and Amit A. Nanavati
Manuscript, 2010.


Talks

Leontief Markets Can Solve Multivariate Polynomial Equations, Yielding FIXP and ETR Hardness
TTIC Colloquium at Toyota Technological Institute (TTI), Chicago.
ACO Seminar at Georgia Institute of Technology, Atlanta.
 
(Essentially) Resolving the Complexity of Constant Rank Bimatrix Games
Theory Seminar at U. Chicago.
Dagstuhl Seminar on Equilibrium Computation Germany.
Bellairs Workshop on Algorithmic Game Theory, Barbados (plenary talk).
Algorithms and Complexity Seminar MIT, Boston.
ESRC workshop on Algorithmic Game Theory, LSE, London, UK.
 
Constant Rank Bimatrix Games are PPAD-hard
46th ACM Symposium on Theory of Computing (STOC'14) , New york.
 
Exchange Markets: Strategy Meets Supply-Awareness
9th Conference on Web and Internet Economics (WINE'13) , Harvard University, Cambridge, MA.
 
A Polynomial Time Algorithm for Rank-1 Two-Player Games (Despite Disconnected Solutions)
Rising Stars in EECS Workshop, MIT, Boston.
Workshop on Computational Game Theory, Stony Brook, NY.
Theory Seminar, University of California Berkeley.
ACO Colloquium, College of Computing, Georgia Tech, Atlanta.
 
Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm
China Theory Week 2012, hosted by CTIC, Aarhus University, Denmark.
Mysore Park Theory Workshop 2012, Mysore, India.
43rd ACM Symposium on Theory of Computing (STOC), San Jose, USA.
Department Seminar, CSE, IIT-Bombay, India.
IEOR Department Seminar, IEOR, IIT-Bombay, India.
Indo-US Symposium 2010, IISC, Bangalore, India.
 
A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities.
ARC Colloquium, College of Computing, Georgia Tech, Atlanta.
 
Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses.
7th Annual International Workshop on Internet & Network Economics (WINE), Singapore.
 
A Simplex-like Algorithm for Fisher Markets
3rd International Symposium on Algorithmic Game Theory (SAGT), Athens, Greece.
India IBM Research Lab, Delhi, India.