PhD Thesis
Nash Equilibrium Computation in Various Games
Dept. of CSE, IIT-Bombay, Aug 2012. |
PDF^{}
Summary |
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. |
arXiv | |
Nash Social Welfare Approximation for Strategic Agents
Simina Branzei, Vasilis Gkatzelis, and Ruta Mehta Submitted, 2017. |
PDF^{} | |
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. |
arXiv | |
Mutation, Sexual Reproduction and Survival in Dynamic Environments
Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani Accepted to ITCS, 2017. |
arXiv | |
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. |
arXiv | |
Settling Some Open Problems on Symmetric Nash Equilibria.
Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod SAGT, 2015. |
arXiv | |
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. |
arXiv | |
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. |
arXiv | |
To Save Or Not To Save: The Fisher Game
Ruta Mehta, Nithum Thain, Laszlo A. Vegh and Adrian Vetta. Accepted to WINE, 2014. |
PDF^{} | |
An Incentive Compatible, Efficient Market for Air Traffic
Flow Management.
Ruta Mehta and Vijay V. Vazirani. Manuscript. |
arXiv | |
Constant Rank Bimatrix Games are PPAD-hard.
Ruta Mehta. In proceedings of STOC, 2014 (Invited to SICOMP). |
PDF^{} | |
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). |
PDF^{} | |
Exchange Markets: Strategy meets
Supply-Awareness
Ruta Mehta and Milind Sohoni. In proceedings of WINE, 2013. |
PDF^{} | |
Towards Polynomial Simplex-Like Algorithms for Market
Equilibrium.
Jugal Garg, Ruta Mehta, Milind Sohoni and Nisheeth Vishnoi. In proceedings of SODA, 2013. |
PDF^{} | |
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. |
PDF^{} | |
Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses.
Jugal Garg, Albert X. Jiang and Ruta Mehta In the Proceedings of WINE, 2011. |
arXiv | |
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 |
arXiv | |
Nash Equilibria in Fisher Market.
Bharat Adsul, Ch. Sobhan, Jugal Garg, Ruta Mehta and Milind Sohoni In the Proceedings of SAGT, 2010. |
arXiv | |
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 | SLIDES^{} |
TTIC Colloquium at Toyota Technological Institute (TTI), Chicago. | Oct'14 |
ACO Seminar at Georgia Institute of Technology, Atlanta. | Nov'14 |
(Essentially) Resolving the Complexity of Constant Rank Bimatrix Games | SLIDES^{} |
Theory Seminar at U. Chicago. | Oct'14 |
Dagstuhl Seminar on Equilibrium Computation Germany. | Aug'14 |
Bellairs Workshop on Algorithmic Game Theory, Barbados (plenary talk). | Apr'14 |
Algorithms and Complexity Seminar MIT, Boston. | Nov'13 |
ESRC workshop on Algorithmic Game Theory, LSE, London, UK. | Oct'13 |
Constant Rank Bimatrix Games are PPAD-hard | ^{} |
46th ACM Symposium on Theory of Computing (STOC'14) , New york. | Jun'14 |
Exchange Markets: Strategy Meets Supply-Awareness | ^{} |
9th Conference on Web and Internet Economics (WINE'13) , Harvard University, Cambridge, MA. | Dec'13 |
A Polynomial Time Algorithm for Rank-1 Two-Player Games (Despite Disconnected Solutions) | SLIDES^{} |
Rising Stars in EECS Workshop, MIT, Boston. | Nov'13 |
Workshop on Computational Game Theory, Stony Brook, NY. | July'13 |
Theory Seminar, University of California Berkeley. | Apr'13 |
ACO Colloquium, College of Computing, Georgia Tech, Atlanta. | Apr'13 |
Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm | SLIDES^{} |
China Theory Week 2012, hosted by CTIC, Aarhus University, Denmark. | Aug'12 |
Mysore Park Theory Workshop 2012, Mysore, India. | Aug'12 |
43rd ACM Symposium on Theory of Computing (STOC), San Jose, USA. | June'11 |
Department Seminar, CSE, IIT-Bombay, India. | Feb'11 |
IEOR Department Seminar, IEOR, IIT-Bombay, India. | Feb'11 |
Indo-US Symposium 2010, IISC, Bangalore, India. | Nov'10 |
A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities. | SLIDES^{} |
ARC Colloquium, College of Computing, Georgia Tech, Atlanta. | Dec'11 |
Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses. | SLIDES^{} |
7th Annual International Workshop on Internet & Network Economics (WINE), Singapore. | Dec'11 |
A Simplex-like Algorithm for Fisher Markets | |
3rd International Symposium on Algorithmic Game Theory (SAGT), Athens, Greece. | Oct'10 |
India IBM Research Lab, Delhi, India. | Aug'09 |