Publications by Topic
Equilibrium Computation and Complexity: | ||
---|---|---|
Sum-of-Squares meets Nash: Algorithms and Optimal Lower Bounds. Pravesh K. Kothari and Ruta Mehta. To Appear in STOC, 2018. | ||
A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications. Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. SODA, 2018. | arXiv | |
CLS:New Problems and Completeness. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Preprint, 2017. | arXiv | |
Constant Rank Bimatrix Games are PPAD-hard. Ruta Mehta. SIAM Journal on Computing, forthcoming. (Invited. Preliminary version appeared in STOC'14). | ||
Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm. Jugal Garg, Ruta Mehta, and Vijay V. Vazirani. Mathematics of Operations Research, forthcoming. (Preliminary version appeared in STOC'14). | ||
Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria. Jugal Garg, Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod. STOC, 2017. | arXiv | |
EXISTS-R-Completeness of Decision Versions of Multi-Player (Symmetric) Nash Equilibria. Jugal Garg, Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod. Transactions on Economics and Computation, forthcoming. (Preliminary version appeared in ICALP'15). | ||
Dichotomies in Equilibrium Computation, and Membership of PLC markets in FIXP. Jugal Garg, Ruta Mehta, and Vijay V. Vazirani. Theory of Computing, 2016. | ||
Multilinear Games. Hau Chan, Albert Xin Jiang, Kevin Leyton-Brown, and Ruta Mehta. WINE, 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. | ||
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. (Preliminary version appeared in STOC'12) | ||
Settling Some Open Problems on Symmetric Nash Equilibria. Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod. SAGT, 2015. | arXiv | |
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. STOC, 2014. | ||
Towards Polynomial Simplex-Like Algorithms for Market Equilibrium. Jugal Garg, Ruta Mehta, Milind Sohoni and Nisheeth Vishnoi. SODA, 2013. | ||
Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses. Jugal Garg, Albert X. Jiang and Ruta Mehta. WINE, 2011. | arXiv | |
Rank-1 Two-Player Games: A Homeomorphism and a Polynomial Time Algorithm. Bharat Adsul, Jugal Garg, Ruta Mehta and Milind Sohoni. STOC, 2011.
A short write-up describing the algorithm in hindsight may be found here |
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. (Preliminary version appeared in SAGT'10). | ||
Strategic Analysis: | |
---|---|
Social Welfare and Profit Maximization from Revealed Preferences. Ziwei Ji, Ruta Mehta, and Matus Telgarsky. Preprint, 2017. | |
Nash Social Welfare Approximation for Strategic Agents. Simina Branzei, Vasilis Gkatzelis, and Ruta Mehta. EC, 2017. | |
An Incentive Compatible, Efficient Market for Air Traffic Flow Management.. Ruta Mehta, and Vijay V. Vazirani. COCOON, 2017. | arXiv |
To Give or not to Give: Fair Division with Strict Preferences. Simina Branzei, Yuezhou Lv, and Ruta Mehta. IJCAI, 2016. | |
To Save Or Not To Save: The Fisher Game. Ruta Mehta, Nithum Thain, Laszlo A. Vegh and Adrian Vetta. WINE, 2014. | |
Exchange Markets: Strategy meets Supply-Awareness. Ruta Mehta, and Milind Sohoni. WINE, 2013. | |
Nash Equilibria in Fisher Market. Bharat Adsul, Ch. Sobhan, Jugal Garg, Ruta Mehta and Milind Sohoni. SAGT, 2010. | arXiv |
Evolution, Dynamics, and Learning: | |
---|---|
Fun and Profit with Random Orders. Anupam Gupta, Ruta Mehta, and Marco Molinaro. Preprint, 2017. | |
Social Welfare and Profit Maximization from Revealed Preferences. Ziwei Ji, Ruta Mehta, and Matus Telgarsky. Preprint, 2017. | |
Mutation, Sexual Reproduction and Survival in Dynamic Environments. Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani. ITCS, 2017. | arXiv |
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 |
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 |
Learning Economic Parameters from Revealed Preferences . Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner and Vijay V. Vazirani. WINE, 2014. | arXiv |
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. |
Publications in Chronological Order
Sum-of-Squares meets Nash: Algorithms and Optimal Lower Bounds.
Pravesh K. Kothari and Ruta Mehta To Appear in STOC 2018. |
||
A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications
Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod SODA, 2018. |
arXiv | |
CLS: New Problems and Completeness
John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani Preprint, 2017. |
arXiv | |
Social Welfare and Profit Maximization from Revealed Preferences
Ziwei Ji, Ruta Mehta, and Matus Telgarsky Preprint, 2017. |
||
Fun and Profit with Random Orders
Anupam Gupta, Ruta Mehta, and Marco Molinaro Preprint, 2017. |
||
Constant Rank Bimatrix Games are PPAD-hard.
Ruta Mehta. SIAM Journal on Computing, forthcoming. (Preliminary version appeared in STOC'14) |
PDF^{} | |
Substitution with Satiation: A New Class of Utility Functions and a Comple-
mentary Pivot Algorithm.
Jugal Garg, Ruta Mehta, and Vijay V. Vazirani. Mathematics of Operations Research, forthcoming. (Preliminary version appeared in STOC'14) |
||
EXISTS-R-Completeness for Decision Versions of Multi-Player (Symmetric)
Nash Equilibria
Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. Transactions on Economics and Computation, forthcoming. (Preliminary version appeared in ICALP'15) |
||
Nash Social Welfare Approximation for Strategic Agents
Simina Branzei, Vasilis Gkatzelis, and Ruta Mehta EC, 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. STOC 2017. |
arXiv | |
Mutation, Sexual Reproduction and Survival in Dynamic Environments
Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani ITCS, 2017. |
arXiv | |
An Incentive Compatible, Efficient Market for Air Traffic
Flow Management.
Ruta Mehta and Vijay V. Vazirani. COCOON, 2017. |
arXiv | |
Dichotomies in Equilibrium Computation, and Membership of PLC markets in
FIXP.
Jugal Garg, Ruta Mehta and Vijay V. Vazirani. Theory of Computing, 12(1), 1-25, 2016. |
||
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 | |
A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities
Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod SIAM Journal on Computing, 44(6), 1820-1847, 2015. (Preliminary versio appeared in STOC'12) |
||
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. WINE, 2014. |
arXiv | |
To Save Or Not To Save: The Fisher Game
Ruta Mehta, Nithum Thain, Laszlo A. Vegh and Adrian Vetta. WINE, 2014. |
PDF^{} | |
Constant Rank Bimatrix Games are PPAD-hard.
Ruta Mehta. 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. STOC, 2014. |
PDF^{} | |
Exchange Markets: Strategy meets
Supply-Awareness
Ruta Mehta and Milind Sohoni. WINE, 2013. |
PDF^{} | |
Towards Polynomial Simplex-Like Algorithms for Market
Equilibrium.
Jugal Garg, Ruta Mehta, Milind Sohoni and Nisheeth Vishnoi. 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 STOC, 2012. |
PDF^{} | |
Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses.
Jugal Garg, Albert X. Jiang and Ruta Mehta WINE, 2011. |
arXiv | |
Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm.
Bharat Adsul, Jugal Garg, Ruta Mehta and Milind Sohoni 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 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 (not up-to-date. See my CV for an almost up-to-date list)
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 |