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, Bombay. 2012. Advisor: Prof. Milind Sohoni
• Masters of Technology,Computer Science and Engineering, Indian Institute of Technology, Bombay, 2005
• Bachelor of Engineering, Computer Engineering, Maharaja Saiyajirao University (MSU) Baroda, 2003

Biography

I am currently an Assistant Professor in the Department of Computer Science. Prior to joining UIUC, I did postdoc at Simons Institute for Theory of Computing at UC Berkeley (Aug'15 to Dec'15), and in College of Computing at Georgia Tech (Aug'12 to July'15, advisor: Prof. Vijay V. Vazirani). I received my Ph.D. in computer science from IIT-Bombay under the supervision of Prof. Milind Sohoni and Prof. Bharat Adsul, in August 2012. My Ph.D. thesis titled "Nash Equilibrium Computation in Various Games" won the ACM India Doctoral Dissertation Award, 2012.

Academic Positions

• Assistant Professor, Dept of Computer Science, University of Illinois at Urbana-Champaign. 2016 - Present
• Postdoctoral Fellow, Simons Institute for Theory of Computing, University of California at Berkeley. July'15 - Dec'15. Host: Prof. Allistair Sinclair.
• Postdoctoral Fellow, College of Computing, Georgia Institute of Technology. Sept'12 - July'15. Host: Prof. Vijay V. Vazirani
• Software Engineer and Developer, Sybase India, Aug'05 - July'07

Professional Registrations

• ACM membership since 2017

Professional Highlights

• 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 of efficient algorithms. I am interested in exploring the computability of equilibria, both market and Nash, under various settings, and also understanding the impact of strategic behavior in multi-agent situations. Currently, I am exploring problems from dynamic matching, fair division of scarce resources, and market design for cloud computing. In addition I am exploring avenues for interdisciplinary applications of these tools to genetic evolution, machine learning and dynamical systems.

Research Interests

• Algorithmic Game Theory: Equilibrium Computation and Complexity, Smoothed Analysis, Learning in Games, Strategic and Dynamic Aspects
• Fair division
• Interdisciplinary applications of game-theoretic tools to machine learning, genetic evolution, and climate change.

Selected Articles in Journals

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

Articles in Conference Proceedings

• Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm. Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni. In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC), 195--204, 2011. ACM. Invited to the Games \& Economic Behavior (GEB) Special Issue for STOC/FOCS/SODA 2011. (28% acceptance rate)
• A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities. Jugal Garg, Ruta Mehta, Milind Sohoni and Vijay V. Vazirani. In Proceedings of the 44th annual ACM symposium on Theory of computing (STOC), 525--534, 2012. ACM. (29% acceptance rate)
• Towards Polynomial Simplex-Like Algorithms for Market Equilibria. Jugal Garg, Ruta Mehta, Milind Sohoni and Nisheeth Vishnoi. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1226--1242, 2013. ACM-SIAM. (29% acceptance rate)
• 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. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), 525--534, 2014. ACM. (29% acceptance rate)
• Constant Rank Bimatrix Games are PPAD-hard. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), 545--554, 2014. ACM. Invited to a special volume of the SIAM Journal on Computing dedicated to the best papers of STOC’14. (29% acceptance rate)
• 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. In 2015 Conference on Innovations in Theoretical Computer Science (ITCS), 73--73, 2015. ACM.(28% acceptance rate)
• Nash Social Welfare Approximation for Strategic Agents. Simina Branzei, Ruta Mehta, and Vasilis Gkatzelis. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC), 611--628, 2017. ACM. (29% acceptance rate)
• Mutation, Sexual Reproduction and Survival in Dynamic Environments. Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), 2017. LIPIcs-Leibniz International Proceedings in Informatics. (35% acceptance rate)
• Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria. Jugal Garg, Ruta Mehta, Vijay V. Vazirani and Sadra Yazdanbod. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 890--901, 2017. ACM. (24% acceptance rate)
• A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications. Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2311--2325, 2018. ACM-SIAM. (33% acceptance rate)
• Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium. Pravesh Kothari and Ruta Mehta. In Proceedings of the 50th Annual Symposium on the Theory of Computation (STOC), 1241--1248, 2018. ACM. (26.6% acceptance rate)
• Nash Equilibrium Computation in Resource Allocation Game. Shivam Gupta and Ruta Mehta. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1953--1955, 2018. ACM. (18% acceptance rate)
• Universal Growth in Production Economies. Simina Branzei, Ruta Mehta, and Noam Nisan. In Proceedings of the 32nd Annual Conference on Neural Information Processing Systems (NuerIPS), 1973–1973, 2018. ACM. (21% acceptance rate)
• Unique End of Potential Line. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. In 46th International Colloquium on Automata, Languages and Programming (ICALP), 56:1 - 56:15, 2019. LIPIcs-Leibniz International Proceedings in Informatics. (29% acceptance rate)
• Multiclass Performance Metric Elicitation. Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta, and Oluwasanmi Koyejo. In 23rd conference on Neural Information Processing Systems (NeuroIPS), 2019. ACM. (21% acceptance rate)
• Smoothed Efficient Algorithms and Reductions for Network Coordination Games. Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. In 11th Innovations in Theoretical Computer Science (ITCS), 2020. LIPIcs-Leibniz International Proceedings in Informatics. (42% acceptance rate)
• Approximate Nash Equilibria of Imitation Games: Algorithms and Complexity. Aniket Murhekar and Ruta Mehta. In 17th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2020. International Foundation for AAMAS. (23% acceptance rate)
• Competitive Allocation of a Mixed Manna. Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021. SIAM. (28% acceptance rate)
• Improving EFX Guarantees through Rainbow Cycle Number. Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), 2021. ACM. (26% acceptance rate)
• Indivisible Mixed Manna: On the Computability of MMS + PO Allocations. Rucha Kulkarni, Ruta Mehta, and Setareh Taki. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), 2021. ACM. (26% acceptance rate)
• Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores. Shant Boodaghians, Bhaskar Ray Chaudhury, Ruta Mehta. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2022. SIAM. (30% acceptance rate)
• On the Existence of Competitive Equilibrium with Chores. Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta. In Proceedings of the 13th Innovations in Theoretical Computer Science (ITCS), 2022. LIPIcs-Leibniz International Proceedings in Informatics. ()
• Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness. Bhaskar Ray Chaudhury, Jugal Garg, Ruta Mehta, and Peter McGlaughlin, In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), 2022. (27% AR)

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

• 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

• Conference Program Committee: The Web Conference (2022) (2018) (2015 poster session)
• Conference Program Committee: 53rd ACM Symposium on Theory of Computing (STOC) (2021)
• Conference Program Committee: Innovations in Theoretical Computer Science (ITCS) (2022, 2018, 2016)
• Conference Program Committee: AAAI Conference on Artificial Intelligence (AAAI) (2020)
• Conference Program Committee: ACM Conference on Economics and Computations (EC) (2019-2020) (2016-18 secondary PC)
• Conference Program Committee: International Colloquium on Automata, Languages and Programming (ICALP) (2019)
• Conference Program Committee: International Symposium on Algorithmic Game Theory (SAGT) (2018,2016)
• Panels: Women in computing for the admitted female students visit (2017, 2016).
• Conference Program Committee: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (2017, 2015)
• Conference Program Committee: SIAM: ACM-SIAM Symposium on Discrete Algorithms (SODA) (2017)
• Conference Program Committee: Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2015)

Service on Department Committees

• CS CARES Committee, 2021-present
• 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 to Federal and State Government

• NSF proposal review panel for CISE.

Other Outside Service

• (Senior) Program Committees: 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.
• 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

• NSF CAREER Award (2018)
• Outstanding Post-Doctoral Researcher Award, College of Computing, Georgia Tech. (2014)
• Rising Stars in EECS, 2013. (2013)
• First ACM India Doctoral Dissertation Award 2012 . (2012)
• Google India Anita Borg Memorial Scholarship 2012. (2012)
• Selected for China Theory Week 2012, hosted by Aarhus University, Denmark. (2012)
• IBM PhD Award in 2010 . (2010)
• IBM PhD Fellowship for the year 2009-2010. (2009)

Teaching Honors

• Places on the list of "Teachers Rated as Excellent by Their Students" (Spring'17)

Research Honors

• NSF CAREER Award (2018)

Recent Courses Taught

• CS 374 AL1 (CS 374 AYA, CS 374 AYB, CS 374 AYC, CS 374 AYD, CS 374 AYE, CS 374 AYF, CS 374 AYG, CS 374 AYH, CS 374 AYJ, CS 374 AYK, ECE 374 AL1, ECE 374 AYA, ECE 374 AYB, ECE 374 AYC, ECE 374 AYD, ECE 374 AYE, ECE 374 AYF, ECE 374 AYG, ECE 374 AYH, ECE 374 AYJ, ECE 374 AYK) - Intro to Algs & Models of Comp
• CS 473 (CSE 414, MATH 473) - Algorithms
• CS 580 - Topics in Algrthmc Game Theory
• CS 598 RM - Algorithmic Game Theory
• CS 598 TH1 - Recent Advances in TCS