Ruta Mehta

For More Information

• Ruta Mehta's DBLP page
• Ruta Mehta's Homepage

Education

• Doctor of Philosophy, Computer Science and Engineering, Indian Institute of Technology (IIT), Bombay, 2012
• Masters of Technology, Computer Science and Engineering, Indian Institute of Technology (IIT), Bombay, 2005
• Bachelor of Engineering, Computer Engineering, Maharaja Saiyajirao University (MSU) Baroda, 2003

Biography

Ruta Mehta is an Associate Professor of Computer Science, an affiliate of Coordinated Science Laboratory, and a founding member of AImpact Center at the University of Illinois at Urbana-Champaign. Prior to joining UIUC, she was a postdoctoral fellow at Simons Institute, UC Berkeley, and at College of Computing, Georgia Tech. She received her Ph.D. from the Indian Institute of Technology Bombay, India. Her research is at the intersection of theoretical computer science, economics, games theory, and machine learning. She on the editorial board of Math. of Operations Research (MOR) and Algorithmica, and has served as chair for flagship conferences and events. For her research, she has received the NSF CAREER Award, the Simons-Berkeley Research Fellowship, and the Best Postdoctoral Award (given by CoC@GT). Her Ph.D. thesis won the ACM India Doctoral Dissertation Award and the IIT-Bombay Excellence in Ph.D. Thesis Award.

Academic Positions

• Affiliate Associate Professor, Coordinate Science Laboratory, University of Illinois Urbana-Champaign, 2023-Present
• Associate Professor, Siebel School of Computing and Data Science, University of Illinois Urbana-Champaign, 2023-Present
• Assistant Professor, Department of Computer Science, University of Illinois Urbana-Champaign, 2016-2023
• Postdoctoral Fellow, Host: Prof. Allistair Sinclair, Simons Institute for Theory of Computing, University of California at Berkeley, July 2015-Dec. 2015
• Postdoctoral Fellow, Host: Prof. Vijay V. Vazirani, College of Computing, Georgia Institute of Technology, Sept. 2012-July 2015

Other Professional Employment

• Software Engineer and Developer, Sybase India, Aug. 2005-July 2007

Major Consulting Activities

• Founding Member, AImpact Center, University of Illinois Urbana-Champaign, 2024-Present

Professional Highlights

• Founding Member of the AImpact Center, UIUC
• Co-founder of the EC (AGT) Mentoring Workshop, co-located with the ACM Economics and Computation Conference.
• Area Chair, 22nd ACM Conference on Economics and Computation (EC), 2021.
• Program Co-Chair, The 16th Conference on Web and Internet Economics (WINE), 2020.
• Associate Editor, Mathematics of Operations Research (MOR), INFORMS, since 2020.

Course Development

• CS 580: Topics on Algorithmic Game Theory

Research Statement

My research is primarily in theoretical computer science. It looks at the fundamental solution concepts from economics, game theory, and social choice from the computational lens. I am also interested in understanding questions related to fairness in society, and evolution in nature.

My main research interests lie in the areas of algorithmic game theory, mathematical economics, and in design efficient and trustwothy systems. More recently, I am interested in exploring trustworthy machine learning systems, emerging economies based on data and AI agents, and online+stochastic fair division. This being said, I never stop exploring the fundamental computational questions at the intersection of NP and co-NP.

Research Interests

• Algorithmic Game Theory: Equilibrium Computation and Complexity, Learning in Games, Strategic and Dynamic Aspects
• Interdisciplinary: Trustworthy Machine Learning, Data Economies, Fair & Efficient Multi-Agent Systems

Selected Articles in Journals

• Adsul, Bharat, Ch Sobhan Babu, Jugal Garg, Ruta Mehta, and Milind Sohoni. "A simplex-like algorithm for linear Fisher markets." Current Science (2012), 103(9),1033-1042.
• Ruta Mehta. "Constant Rank Bimatrix Games are PPAD-hard." Special Section on the 46th Annual ACM Symposium on Theory of Computing (STOC 2014); SIAM Journal on Computing (2018), 47(5):1858-1887.
• Jugal Garg, Ruta Mehta, Milind Sohoni, and Vijay V. Vazirani. "A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities." SIAM Journal on Computing (2015), 44(6), 1820-1847.
• Jugal Garg, Ruta Mehta, and Vijay V. Vazirani. "Dichotomies in Equilibrium Computation and Membership of PLC Markets in FIXP."Theory of Computing (2016), 12(1),1-25.
• Jugal Garg, Ruta Mehta, Vijay Vazirani, and Sadra Yazdanbod. "ETR-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria." ACM Transactions on Economics and Computation (2018), 6(1):1:1–1:23.
• Jugal Garg, Ruta Mehta, and Vijay Vazirani. "Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm." Mathematics of Operations Research (2018), 43(3):996-1024.

Articles in Conference Proceedings

• Tˆatonnement Dynamics for Fisher Markets with Chores. Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, and Tianlong Nan. Accepted to ACM Symposium on Theory of Computation (STOC), 2026
• Monotone Contractions. Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. In Proceedings of the 44th annual ACM symposium on Theory of computing (STOC), 2025.
• Online Fair Division: Towards Ex-Post Constant MMS Guarantees. Pooja Kulkarni, Ruta Mehta, and Parnian Shahkar:. In Proceedings of ACM Conference on Economics and Computation (EC), 2025.
• A Unified and Distribution-Optimal Analysis of the Max and Min IID Prophet Inequality. Vasilis Livanos, and Ruta Mehta. In Proceedings of ACM Conference on Economics and Computation (EC), 2025.
• On the structure of envy-free orientations on graphs. Jinghan A Zeng, and Ruta Mehta. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2025. (With an undergraduate student)
• You Get What You Give: Reciprocal Fair Federated Learning. Aniket Murhekar, Jiaxin Song, Parnian Shahkar, Bhaskar Ray Chaudhury, Ruta Mehta. In Proceedings of The Forty-first International Conference on Machine Learning (ICML), 2025.
• On the existence of EFX under picky or non-differentiative agents. Maya Viswanathan, and Ruta Mehta, In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2024. (With a high-school student)
• Bhaskar Ray Chaudhury, Linyi Li, Mintong Kang, Bo Li, and Ruta Mehta. "Fairness in Federated Learning via Core-Stability." In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), 2022. (Invited for the Spotlight or equivalent). (Acceptance Rate: 25%)
• Bhaskar Ray Chaudhury, Jugal Garg, Ruta Mehta, and Peter McGlaughlin. "Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness." In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), 2022. (Acceptance Rate: 27%)
• Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta. "On the Existence of Competitive Equilibrium with Chores." In Proceedings of the 13th Innovations in Theoretical Computer Science (ITCS), 2022. LIPIcs-Leibniz International Proceedings in Informatics. (Acceptance Rate: )
• Shant Boodaghians, Bhaskar Ray Chaudhury, Ruta Mehta. "Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores." In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2022. SIAM. (Acceptance Rate: 30%)
• Rucha Kulkarni, RutaMehta, and Setareh Taki. "Indivisible Mixed Manna: On the Computability of MMS + PO Allocations." In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), 2021. ACM. (Acceptance Rate: 26%)
• Bhaskar Ray Chaudhury, Jugal Garg,Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. "Improving EFX Guarantees through Rainbow Cycle Number." In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), 2021. ACM. (Acceptance Rate: 26%)
• Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. "Competitive Allocation of a Mixed Manna." In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021. SIAM. (Acceptance Rate: 28%)
• Aniket Murhekar and Ruta Mehta. "Approximate Nash Equilibria of Imitation Games: Algorithms and Complexity." In Proceedings of 17th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2020. International Foundation for AAMAS. (Acceptance Rate: 23%)
• Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. "Smoothed Efficient Algorithms and Reductions for Network Coordination Games." In Proceedings of 11th Innovations in Theoretical Computer Science (ITCS), 2020. LIPIcs-Leibniz International Proceedings in Informatics. (Acceptance Rate: 42%)
• Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta, and Oluwasanmi Koyejo. "Multiclass Performance Metric Elicitation." In Proceedings of 23rd Conference on Neural Information Processing Systems (NeurIPS), pp. 1042-1052, 2019. ACM. (Acceptance Rate: 21%)
• John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. "Unique End of Potential Line." In Proceedings of 46th International Colloquium on Automata, Languages and Programming (ICALP), 56:1-56:15, 2019. LIPIcs-Leibniz International Proceedings in Informatics. (Acceptance Rate: 29%)
• Simina Branzei, Ruta Mehta, and Noam Nisan. "Universal Growth in Production Economies." In Proceedings of the 32nd Annual Conference on Neural Information Processing Systems (NuerIPS), pp. 1973-1983, 2018. ACM. (Acceptance Rate: 21%)
• Shivam Gupta and Ruta Mehta. "Nash Equilibrium Computation in Resource Allocation Game." In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1953-1955, 2018. ACM. (Acceptance Rate: 18%)
• Pravesh Kothari and Ruta Mehta. "Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium." In Proceedings of the 50th Annual Symposium on the Theory of Computation (STOC), pp. 1241-1248, 2018. ACM. (Acceptance Rate: 26.6%)
• Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. "A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications." In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2311-2325, 2018. ACM-SIAM. (Acceptance Rate: 33%)
• Jugal Garg, Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod. "Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria." In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 890-901, 2017. ACM. (Acceptance Rate: 24%)
• Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani. "Mutation, Sexual Reproduction and Survival in Dynamic Environments." In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), 24:1-24:19, 2017. LIPIcs-Leibniz International Proceedings in Informatics. (Acceptance Rate: 35%)
• Simina Branzei, Ruta Mehta, and Vasilis Gkatzelis. "Nash Social Welfare Approximation for Strategic Agents." In Proceedings of the ACM Conference on Economics and Computation (EC), pp. 611-628, 2017. ACM. (Acceptane Rate: 29%)
• Ruta Mehta, Ioannis Panageas, and Georgios Piliouras. "Multiplicative Weights Updates Algorithm." In the Proceedings of the Conference on Innovations in Theoretical Computer Science (ITCS), pp. 73-73, 2015. ACM. (Acceptance Rate: 28%)
• Ruta Mehta. "Constant Rank Bimatrix Games are PPAD-hard." In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pp. 545-554, 2014. ACM. (Acceptance Rate: 29%)
• Jugal Garg, Ruta Mehta, and Vijay V. Vazirani. "Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions." In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pp. 525-534, 2014. ACM. (Acceptance Rate: 29%)
• Jugal Garg, Ruta Mehta, Milind Sohoni and Nisheeth Vishnoi. "Towards Polynomial Simplex-Like Algorithms for Market Equilibria." In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1226-1242, 2013. ACM-SIAM. (Acceptance Rate: 29%)
• Jugal Garg, Ruta Mehta, Milind Sohoni and Vijay V. Vazirani. "A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities." In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 525-534, 2012. ACM. (Acceptance Rate: 29%)
• Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni. "Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm." In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC), pp. 195-204, 2011. ACM. (Acceptance Rate: 28%)

Patents

• Systems and methods for federating open social networks for analyses. Kuntal Dey, Ruta Mehta, Natwar Modani, Seema Nagar, Amit Anil Nanavati. US 20120124134 A1, 2012.
• Federating open social networks for analyses. Kuntal Dey, Ruta Mehta, Natwar Modani, Seema Nagar, Amit Anil Nanavati. US 20120324014 A1, 2012.

Conferences Organized or Chaired

• Co-organizing New Pepspectives on Algorithmic Game Theory, co-located with the Stonybrook Game Theory Conference, 2026.
• Co-organizing the AImpact Seminar Series, 2025-present.
• Program Committee Track Chair, ACM Conference on Economics and Computation (EC), 2025.
• Program Committee Chair, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Track A, 2025.
• Area Chair for 22nd ACM Conference on Economics and Computation (EC), 2021.
• Program Co-Chair for the 16th Conference on Web and Internet Economics (WINE), 2020.
• Co-organized Rising Stars in EECS, 2019, held at University of Illinois at Urbana-Champaign. Mentoring workshop for women PhD students interested in academia.
• Co-organized AGT Mentoring Workshop co-located with the 19th ACM Conference on Economics and Computation (EC), June 18, 2018, Cornell University, Ithaca, USA.
• Tutorial Chair for the 13th Conference on Web and Internet Economics (WINE), 2017.
• Co-organized Game Theory Workshop (14 - 17 Dec, 2015), as a part of Combinatorial Optimization trimester at Hausdorff Center for Mathematics, Universitat at Bonn, Germany.

Other Scholarly Activities

• Panelist: Tech Pulse 2030-The Reliable Agent Challenge: Building AI You Can Trust, Chicago, 2026
• Invited and Participated in TCS Visioning Workshop, 2021.
• Panel: Job Market, EC Mentoring workshop (2021), held at 22nd ACM Conference on Economics and Computation (EC), 2021.
• Panels: Women in computing for the admitted female students visit (2017, 2016).

Professional Societies

• ACM membership since 2017

Service on Department Committees

• CS CARES, Chair (2025-present)
• CS CARES, Vice Chair (2023-2024)
• CS Advisory Committee (2023-2024)
• CS CARES Committee, 2020-2023
• Faculty Recruiting Committee, 2021 - 2022 (secondary member)
• Graduate Study Committee, 2019 - 2020
• Co-organized Rising Stars in EECS Workshop 2019, held at the University of Illinois at Urbana-Champaign
• Diversity Committee, 2018 - 2019
• Outreach Committee, 2017 - 2019.
• Panel: Women in computing for the admitted female students visit 2016, 2017.
• Undergraduate Study Committee, 2016 - 2019

Service on College Committees

• Grainger College of Engineering, Council for Community, Opportunity, and Engagement (CCOE) (2025-present)

Service to Federal and State Government

• Invited to serve on a European Research Council (ERC) panels.
• Served as a reviewer for U.S.-Israel Binational Science Foundation
• NSF proposal review panel for CISE.

Other Outside Service

• (Senior) Program Committees: IEEE FOCS 2026, ACM EC 2026, EATCS ICALP 2024, SIAM SOSA 2023, ACM EC 2022, TheWebConf 2022, ITCS 2022, STOC 2021, ACM EC 2020, AAAI 2020, ACM EC 2019, ICALP 2019, ITCS 2019, WWW 2018, ACM EC 2018, SODA 2017, FSTTCS 2017, ITCS 2016, SAGT 2016, FOCS 2015, FSTTCS 2015, WWW (poster) 2015.
• Co-organizing EC (AGT) Mentoring Workshop 2022, co-located with the ACM Conference on Economics and Computation.
• Served on the committee for Spotlight beyond WINE, 2021.
• Program Committee Area Chair, ACM Conference on Economics and Computation (EC), 2021.
• Guest Editor, ACM Transactions on Economics and Computation (TEAC) for the special issue of WINE 2020.
• Associate Editor, Mathematics of Operations Research (MOR), INFORMS, since 2020.
• Program Committee Co-Chair, 16th Conference on Web and Internet Economics (WINE), 2020.
• Co-organized EC (AGT) Mentoring Workshop 2018, co-located with the ACM Conference on Economics and Computation (EC). (I played a pivotal role in conceptualizing this workshop, and the success in its debutant year led SIGecom to make it a permanent workshop at the ACM EC conference).
• Tutorial Chair, 13th Conference on Web and Internet Economics (WINE), 2017.
• Co-organized Game Theory Workshop, Dec 14 - 17, 2015, as a part of Combinatorial Optimization trimester at Hausdorf Center for Mathematics (HIM), Universitat Bonn, Germany.

Honors

• Dean's Award for Excellence in Research, Associate Professor, 2026 (2026)
• Campus Award for Excellence in Guiding Undergraduate Research, University of Illinois Urbana-Champaign, 2025 (2025)
• College Award for Sustained Excellence in Diversity, Equity, and Inclusion, SSCDS, Illinois, 2025 (2025)
• Invited Speaker, 21st Max Planck Advanced Course on the Foundations of Computer Science (ADFOCS), 2020 (2020)
• NSF CAREER Award, 2018 (2018)
• Simons-Berkeley Research Fellow, 2015 (2015)
• Outstanding Post-Doctoral Researcher Award, College of Computing, Georgia Tech, 2014 (2014)
• ACM India Doctoral Dissertation Award, 2012 (2012)