• NEWS!
  
•  
• Organized EC Mentoring Workshop 2022 with Aviad Rubinstein and Alex Teytelboym.
  
•  
• Placed on the List of Teachers Ranked as Excellent by Their Students, Fall 2021.
  
•  
• Keynote/Plenary Talks:
  13th Symposium on Algorithmic Game Theory (SAGT 2020).
  21st Max Planck Advanced Course on the Foundations of Computer Science (ADFOCS 2020).
•  
• Co-Chair of WINE 2020.
  Stay tuned for its ACM TEAC special issue!
•  
• Journal Associate Editor:
  Mathematics of Operations Research (MOR)
•  
• Honored to receive NSF CAREER Award (2018 - 2023).
  Thank you NSF!
•  
• Aniket Murhekar wins the prestigeous Siebel Scholar Award, 2020.
•  
• Committee work: EC 2021 (area chair), STOC 2021, EC 2020 (SPC), AAAI 2020, ICALP 2019, EC 2019, ITCS 2018.
•  
• Organization:
  Rising Stars in EECS Workshop 2019.
  AGT Mentoring Workshop 2018.

Publications

Author names are in alphabetical order in most of my publications (as per the TCS tradition).

This page may be outdated. For an up-to-date list see my DBLP page.

Journal Publications

• Polynomial Time Algorithm to Find an Approximate Competitive Equilibrium for Chores. Shant Boodaghians, Bhaskar Ray Chaudhury, and Ruta Mehta. Operations Research (OR) (minor revision).
• Improving EFX Guarantees Through Rainbow Cycle Number. Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, Pranabendu Misra. Mathematics of Operations Research (MOR) (major revision)
• Competitive Allocation of a Mixed Manna. Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. Mathematics of Operations Research (MOR) (accepted) (link).
• Online revenue maximization for server pricing. Shant Boodaghians, Federico Fusco, Stefano Leonardi, Yishay Mansour, and Ruta Mehta. Journal of Autonomous Agents Multi Agent Systems (JAAMAS) 36(1): 11 (2022).
• Nash Social Welfare Approximation for Strategic Agents. Simina Branzei, Vasilis Gkatzelis, and Ruta Mehta. Operations Research (OR). 70(1): 402-415 (2022).
• Fast Algorithms for Rank-1 Bimatrix Games. Bharat Adsul, Jugal Garg, Ruta Mehta, Milind Sohoni, and Bernhard von Stengel. Operations Research (OR). 69(2): 613-631 (2021).
• Unique end of potential line. John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani. J. Comput. Syst. Sci. (JCSS), 114: 1-35 (2020).
• An incentive compatible, efficient market for air traffic flow management. Ruta Mehta, Vijay V. Vazirani. Theor. Comput. Sci (TCS), 818: 41-50 (2020). (invited)
• Constant Rank Bimatrix Games are PPAD-hard. Ruta Mehta. SIAM Journal on Computing (SICOMP), 47(5), 1858--1887, 2018. Special Section on the 46th Annual ACM Symposium on Theory of Computing (STOC 2014). (invited)
• Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm. Jugal Garg, Ruta Mehta, and Vijay Vazirani. Mathematics of Operations Research (MOR), 43(3): 996-1024, 2018.
• ETR-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria. Jugal Garg, Ruta Mehta, Vijay Vazirani, and Sadra Yazdanbod. ACM Transactions on Economics and Computation (TEAC), 6(1): 1:1-1:23, 2018.
• Dichotomies in Equilibrium Computation, and Membership of PLC markets in FIXP. Jugal Garg, Ruta Mehta, and Vijay Vazirani. Theory of Computing (ToC), 12(1): 1-25, 2016.
• A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities. Jugal Garg, Ruta Mehta, Milind Sohoni, and Vijay Vazirani. SIAM Journal on Computing (SICOMP), 44(6): 1820-1847, 2015.
• A Simplex-like Algorithm for Fisher Markets. Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta and Milind Sohoni. Current Science , 103(9): 1033-1042, 2012.

Conference Publications

2022

• Fairness in Federated Learning via Core-Stability. Bhaskar Ray Chaudhury, Linyi Li, Mintong Kang, Bo Li, Ruta Mehta. NeurIPS 2022. (Spotlight or equivalent.)
• (Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna. Vasilios Livanos, Ruta Mehta, Aniket Murhekar. AAMAS, 2022
• On the Existence of Competitive Equilibrium with Chores. Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta. ITCS, 2022.
• Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores. Shant Boodaghians, Bhaskar Ray Chaudhury, Ruta Mehta. SODA, 2022.

2021

• Indivisible Mixed Manna: On the Computability of MMS + PO Allocations. Rucha Kulkarni, Ruta Mehta, Setareh Taki. EC, 2021. (with all women students)
• Improving EFX Guarantees through Rainbow Cycle Number. Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, Pranabendu Misra. EC, 2021.
• Competitive Allocation of a Mixed Manna. Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta. SODA, 2021.
• PTAS for Maximin Shares in an Indivisible Mixed Manna. Rucha Kulkarni, Ruta Mehta, and Setareh Taki. AAAI, 2021. (with all women students, again :D)
• Fair and Efficient Allocations under Subadditive Valuations. Bhaskar Ray Chaudhury, Jugal Garg, and Ruta Mehta. AAAI, 2021.

2020

• Smoothed Ecient Algorithms and Reductions for Network Coordination Games. Shant Boodaghians,
• Smoothed Ecient Algorithms and Reductions for Network Coordination Games. Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. ITCS, 2020.
• Online Revenue Maximization for Server Pricing. Shant Boodaghians, Federico Fusco, Stefano Leonardi, Ruta Mehta, and Yishay Mansour. IJCAI-PRICAI, 2020.
• Approximate Nash Equilibria of Imitation Games: Algorithms and Complexity. Aniket Murhekar and Ruta Mehta. AAMAS, 2020.

2019

• Multiclass Performance Metric Elicitation. Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta, and Oluwasanmi Koyejo. NeuroIPS, 2019.
• Unique End of Potential Line. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. ICALP, 2019.
• Eliciting Binary Performance Metrics. Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta, and Oluwasanmi Koyejo. AISTATS, 2019.

2018

• Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium. Pravesh Kothari and Ruta Mehta. 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.
• Universal Growth in Production Economies. Simina Branzei, Ruta Mehta, and Noam Nisan. NeuroIPS, 2018.
• Maximizing Profit with Convex Costs in the Random-order Model. Anupam Gupta, Ruta Mehta, and Marco Molinaro. ICALP, 2018.
• Social Welfare and Profit Maximization from Revealed Preferences. Ziwei Ji, Ruta Mehta, and Matus Telgarsky. WINE, 2018.
• Nash Equilibrium Computation in Resource Allocation Games. Shivam Gupta and Ruta Mehta. AAMAS, 2018. (with an undergraduate student at UIUC)

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.
• Nash Social Welfare Approximation for Strategic Agents. Simina Branzei, Ruta Mehta, and Vasilis Gkatzelis. EC, 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, Ecient Market for Air Trac Flow Management. Ruta Mehta and Vijay V. Vazirani. COCOON, 2017. Invited to a special issue of Theoretical Computer Science.

2016

• Multilinear Games. Hau Chu, Albert Jiang, Kevin Leyton-Brown, and Ruta Mehta. WINE, 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.
• 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: Eciently Solving General-Sum Bayesian Threat Screening Games. Aaron Schlenker, Matthew Brown, Arunesh Sinha, Milind Tambe, and Ruta Mehta. ECAI, 2016.

2010 - 2015

• ETR-Completeness of Decision Versions of 3-Nash. Jugal Garg, Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod. ICALP, 2015.
• Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Update Algorithm and a Conjecture of Haploid Genetics. Ruta Mehta, Ioannis Panageas, and Georgios Piliouras. ITCS, 2015.
• Settling Some Open Problems on Symmetric Nash Equilibria. Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. SAGT, 2015.
• Constant Rank Bimatrix Games are PPAD-hard. Ruta Mehta. STOC,2014. Invited to SIAM Journal on Computing (SICOMP) for special issue dedicated to the best papers of STOC'14.
• 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.
• 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.
• Towards Polynomial Simplex-Like Algorithms for Market Equlibria. Jugal Garg, Ruta Mehta, Milind A. Sohoni, Nisheeth K. Vishnoi. SODA, 2013.
• Exchange Markets: Strategy meets Supply-Awareness. Ruta Mehta, and Milind Sohoni. WINE, 2013.
• 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.
• The Weighted Majority Algorithm does not Converge in Nearly Zero-sum Games. Maria Florina Balcan, Florin Constantin, and Ruta Mehta. ICML 2012 workshop on Markets Mechanisms and Multi-Agent Models, 2012.
• Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm. Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni. STOC, 2011. Invited to the GEB Special Issue for STOC/FOCS/SODA 2011.
• Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses. Jugal Garg, Albert X. Jiang, and Ruta Mehta. WINE, 2011.
• Nash Equilibria in Fisher Market. with Bharat Adsul, Ch. Sobhan Babu, Ruta Mehta, Jugal Garg, and Milind Sohoni. SAGT, 2010. Invited to the TOCS Special Issue for SAGT 2010.
• A Simplex-like Algorithm for Fisher Markets. Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta, and Milind Sohoni. SAGT, 2010.