Publications by TopicPublications by YearTalks

Publications by Topic

Equilibrium Computation and Complexity:
Sum-of-Squares meets Nash: Algorithms and Optimal Lower Bounds. Pravesh K. Kothari and Ruta Mehta. Preprint, 2017.
A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications. Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. To Appear in 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). PDF
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) PDF
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. PDF
Towards Polynomial Simplex-Like Algorithms for Market Equilibrium. Jugal Garg, Ruta Mehta, Milind Sohoni and Nisheeth Vishnoi. SODA, 2013. PDF
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. PDF
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. PDF
Exchange Markets: Strategy meets Supply-Awareness. Ruta Mehta, and Milind Sohoni. WINE, 2013. PDF
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
Submitted, 2017.
A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications
Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod
To Appear in SODA, 2018.
CLS: New Problems and Completeness
John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani
Preprint, 2017.
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)
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.
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.
Mutation, Sexual Reproduction and Survival in Dynamic Environments
Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani
ITCS, 2017.
An Incentive Compatible, Efficient Market for Air Traffic Flow Management.
Ruta Mehta and Vijay V. Vazirani.
COCOON, 2017.
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.
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.
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.
WINE, 2014.
To Save Or Not To Save: The Fisher Game
Ruta Mehta, Nithum Thain, Laszlo A. Vegh and Adrian Vetta.
WINE, 2014.
Constant Rank Bimatrix Games are PPAD-hard.
Ruta Mehta.
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.
STOC, 2014.
Exchange Markets: Strategy meets Supply-Awareness
Ruta Mehta and Milind Sohoni.
WINE, 2013.
Towards Polynomial Simplex-Like Algorithms for Market Equilibrium.
Jugal Garg, Ruta Mehta, Milind Sohoni and Nisheeth Vishnoi.
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
STOC, 2012.
Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses.
Jugal Garg, Albert X. Jiang and Ruta Mehta
WINE, 2011.
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
Nash Equilibria in Fisher Market.
Bharat Adsul, Ch. Sobhan, Jugal Garg, Ruta Mehta and Milind Sohoni
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 (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
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.