Ruta Mehta

Ruta Mehta

Associate Professor

Siebel School of Computing and Data Science
Coordinated Science Laboratory (Affiliate)
University of Illinois at Urbana-Champaign

TCS@UIUC group
CS-CARES @UIUC
SafeToC

Email: rutameht (at) illinois edu
CV, Short Bio, DBLP page

Research Interests: Theoretical Computer Science; Economics, Game Theory and Computation; Fair Division; Interdisciplinary Applications of GT, e.g., to ML and Evolution.

Selected Recent Publications (For the complete list see DBLP.)

Tâtonnement Dynamics for Fisher Markets with Chores. Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, and Tianlong Nan. Accepted to ACM Symposium on Theory of Computing (STOC) 2026
Online Fair Division With Subsidy: When Do Envy-Free Allocations Exist, and at What Cost? Pooja Kulkarni, Ruta Mehta, Vishnu Narayanan, and Tomasz Ponitka. Accepted to International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2026
EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta: Operations Research (OR) 73(2): 738-751 (2025).
Polynomial Time Algorithm to Find an Approximate Competitive Equilibrium for Chores. Shant Boodaghians, Bhaskar Ray Chaudhury, and Ruta Mehta. Operations Research (OR) (minor revision).
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. Bhaskar Ray Chaudhury, Aniket Muarhekar, and 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)
Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number. Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, Pranabendu Misra. Mathematics of Operations Research (MOR) 49(4): 2323-2340 (2024).
Fair Federated Learning via the Proportional Veto Core. In Proceedings of The Forty-first International Conference on Machine Learning (ICML), 2024.
Competitive Equilibrium for Chores: from Dual Eisenberg-Gale to a Fast, Greedy, LP-based Algorithm. In Proceedings of ACM Conference on Economics and Computation (EC), 2024.
Minimization is Harder in the Prophet World. Vasilis Livanos, and Ruta Mehta. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA24), 2024.
Competitive Allocation of a Mixed Manna. Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. Mathematics of Operations Research (MOR). 48(3): 1630-1656 (2023).
Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization. Aniket Murhekar, Zhuowen Yuan, Bhaskar Ray Chaudhury, Bo Li, and Ruta Mehta. In Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS), 2023.
EFX: A Simpler Approach, and an (Almost) Optimal Guarantee via Rainbow Cycle Number. Han- naneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. In Proceedings of the 24th Conference on Economics and Computation (EC), 2023.
Nash Social Welfare Approximation for Strategic Agents. Simina Branzei, Vasilis Gkatzelis, and Ruta Mehta. Operations Research (OR). 70(1): 402-415 (2022).
Fairness in Federated Learning via Core-Stability. Bhaskar Ray Chaudhury, Linyi Li, Mintong Kang, Bo Li, Ruta Mehta. NeurIPS 2022. (Spotlight or equivalent.)
Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness. Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta. EC 2022.
Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores. Shant Boodaghians, Bhaskar Ray Chaudhury, Ruta Mehta. SODA 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).
Indivisible Mixed Manna: On the Computability of MMS + PO Allocations. Rucha Kulkarni, Ruta Mehta, Setareh Taki. EC 2021. (all women authors 😊)
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.

Selected Recent Invited Talks/Panels

Information in Games and Mechanisms Workshop, FSTTCS'25, Dec 2025.
ACO Seminar, Georgia Tech, Nov 2025.
OR Seminar, Business School, UIUC, Oct 2025.
CS Seminar, Oxford University, UK, May 2025.
CS Seminar, U. of Liverpool, UK, May 2025.
CS Seminar, Indian Institute of Technology, Gandhinagar, Jan 2025.
Keynote at exSPLORe2025 Workshop, Ashoka University, Jan 2025.
Seminar in CS@IIT Bombay, Oct 2024.
Theory Seminar at TIFR, Oct 2024.
Keynote at EC 2024 Workshop on New Directions in Social Choice, Yale, July 2024.
Keynote at the Workshop on Algorithms for Learning and Economics (WALE), Greece, June 2024. (could not attend due to visa issues)
Theory Seminar at UC Irvine, May 2024.
SLMath workshop Randomization, Neutrality, and Fairness, MSRI, Berkeley, Oct 2023.
Workshop in the Honor of 70th Birthday of Mihalis Yannakakis, Aug 2023.
Mini Symposium on Algorithmic Game Theory at CanaDAM, June 2023.
TCS Seminar at Jagiellonian, April 2023.
Duke CS Theory Seminar, April 2023.
Multi-Agent Systems Workshop at Bellairs, Barbados, March 2023.
Recent Advances on Total Search Problems Workshop, July 2022.
Cornell University, Theory Seminar, May 2022.
C3.AI DTI Colloquium, April 2022. (talk video)
MIT, Algorithms and Complexity Seminar, April 2022.
University of Washington, Theory Seminar, April 2022.
Israel AGT Seminar, March 2022.
Harvard, EconCS seminar, March 2022.
Purdue, CS Colloquim, Nov 2021.
CSL Seminar, U. of I. at Urbana-Champaign, Oct 2021.
Columbia Theory Seminar, Oct 2021.
ISYE Seminar, U. of I. at Urbana-Champaign, Oct 2021.
FaiRACAC workshop, co-located with EC 2021.
Job Market Panel w/ Shuchi Chawla, Scott Kominer, and Ariel Procaccia. EC Mentoring workshop, 2021.
Keynote at 13th Symposium on Algorithmic Game Theory (SAGT 2020).
21st Max Planck Advanced Course on the Foundations of Computer Science (ADFOCS 2020). (honored to be one of three speakers)
RAIN Seminar at Stanford, Oct 2020.

Selected Awards

Campus Award for Excellence in Guiding Undergraduate Research, 2025.
College Award for Sustained Excellence in Diversity, Equity, and Inclusion, 2025.
Placed on the List of Instructors Rated as Excellent by Their Students, Fall 2021, Spring 2017 and Fall 2021.
NSF CAREER Award, 2018.
Simons Berkeley Research Fellow, 2015.
Outstanding Post-Doctoral Researcher Award, Georgia Tech, 2014.
ACM India Doctoral Dissertation Award 2012.

Fun trivia

independent projects