Ruta Mehta
Ruta Mehta
Assistant Professor
(217) 300-4650
3218 Siebel Center for Comp Sci

For more information

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

Resident Instruction

  • CS598 RM: Topics on Algorithmic Game Theory, Fall'18
  • CS 473: Theory II (Algorithms), Spring'18 (40+ students completed the course)
  • CS598 RM: Topics on Algorithmic Game Theory, Spring'17 (Listed in the "Instructors rated as excellent by students")
  • CS473: Theory II (Algorithms), Fall'16 (60+ students completed the course)
  • CS598 RM: Topics on Algorithmic Game Theory, Spring'16

Course Development

  • CS598 RM: 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 Analysis of Games and Markets
  • Game Theoretic Analysis of Genetic Diversity

Research Areas

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.
  • An incentive compatible, efficient market for air traffic flow management. Ruta Mehta and Vijay V. Vazirani. ELSEVIER Theoretical Computer Science (2017).
  • 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).
  • Constant Rank Bimatrix Games are PPAD-hard. Ruta Mehta. SIAM Journal on Computing. 47(5): 1858­1887 (2018). (Invited to the special issue on the STOC'14)
  • 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).

Articles in Conference Proceedings

  • Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses. Jugal Garg, Albert X. Jiang, and Ruta Mehta. In Proceedings of the International Workshop on Internet and Network Economics (WINE), 399--407, 2011. Springer. (31% acceptance rate)
  • 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, 2012. (27% 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)
  • To Save Or Not To Save: The Fisher Game. Ruta Mehta, Nithum Thain, Laszlo A. Vegh, and Adrian Vetta. In Proceedings of the 10th International Conference on Web and Internet Economics (WINE), 294--307, 2014. Springer. (29% acceptance rate)
  • Learning Economic Parameters from Revealed Preferences. Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner, and Vijay V. Vazirani. In Proceedings of the 10th International Conference on Web and Internet Economics (WINE), 338--353, 2014. Springer. (29% acceptance rate)
  • ETR-Completeness of Decision Versions of 3-Nash. Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), 554--566, 2015. Springer. (28% 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 Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS), 73--73, 2015. (28% acceptance rate)
  • Settling Some Open Problems on Symmetric Nash Equilibria. Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. In Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT), 272--284, 2015. Springer. (34% acceptance rate)
  • Multilinear Games. Hau Chu, Albert Jiang, Kevin Leyton-Brown, and Ruta Mehta. In Proceedings of the12th International Conference on Web and Internet Economics (WINE), 44-58, 2016. Springer. (39% acceptance rate)
  • The Complexity of Genetic Diversity: Sex with Two Chromosomes is Advantageous but Unpredictable. Ruta Mehta, Ioannis Panageas, Georgios Piliouras and Sadra Yazdanbod. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA), 65:1--65:17, 2016. LIPIcs-Leibniz International Proceedings in Informatics. (27% acceptance rate)
  • 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. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI), 1476--1484, 2016. (27% acceptance rate)
  • To Give or not to Give: Fair Division with Strict Preferences. Simina Branzei, Yuezhou Lv, and Ruta Mehta. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), 123--129, 2016. AAAI Press. (24% acceptance rate)
  • An Incentive Compatible, Efficient Market for Air Traffic Flow Management. Ruta Mehta, and Vijay V. Vazirani. In Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON), 407-- 419, 2017. Springer. (43% 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. (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 (NIPS), forthcoming, 2018. ACM. (21% acceptance rate)
  • Social Welfare and Profit Maximization from Revealed Preferences. Ziwei Ji, Ruta Mehta, and Matus Telgarsky. In Proceedings of the 14th Conference on Web and Internet Economicsn (WINE), forthcoming, 2018. ACM. (30% 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.
  • Smoothed Efficient Algorithms and Reductions for Network Coordination Games. Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. To appear in Innovations in Theoretical Computer Science (ITCS), 2020.
  • Online Revenue Maximization for Server Pricing. Shant Boodaghians, Federico Fusco, Stefano Leonardi, Ruta Mehta, and Yishay Mansour. In IJCAI-PRICAI, 2020.

Pending Articles

  • Games that (Busy) Neighbors Play. Wei-Chun Lee, Vasileios Livanos, Ruta Mehta, and Hari Sundaram. Preprint, 2018.

Invited Lectures

Patents

Conferences Organized or Chaired

  • Area Chair EC'21
  • Co-Chair WINE 2020, to be held Dec. 2020 in Beijing.
  • Co-organized Rising Stars in EECS, 2019, held at U. of I. 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, June 18, 2018, Cornell University, Ithaca, USA.
  • Chaired WINE, 2017 Tutorial Session.
  • 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: AAAI (2020)
  • Conference Program Committee: STOC'20
  • Conference Program Committee: International Colloquium on Automata, Languages and Programming (ICALP) (2019)
  • Conference Program Committee: ACM Conference on Economics and Computations (EC) (2019-2020) (2016-18 secondary PC)
  • Conference Program Committee: Innovations in Theoretical Computer Science (ITCS) (2022, 2018, 2016)
  • Conference Program Committee: International Symposium on Algorithmic Game Theory (SAGT) (2018,2016)
  • Conference Program Committee: The Web Conference (2022) (2018) (2015 poster session)
  • 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

  • Diversity Committee, 2019 - now.
  • Outreach Committee, 2017 - 2019.
  • The undergraduate study committee, 2016- 2019
  • Panel: Women in computing for the admitted female students visit 2016, 2017.
  • PhD thesis committee of Haiming Jin, 2017 ( Advisor: Klara Nahrstedt)
  • PhD thesis proposal committee of Vivek Madan, 2017 (Advisor: Chandra Chekuri)

Service to Federal and State Government

  • NSF proposal review panel for CISE, 2017

Other Outside Service

  • Journal Reviewing: INFORMS Mathematics of Operations Research
  • Journal Reviewing: INFORMS Operations Research
  • Journal Reviewing: Journal of ACM
  • Journal Reviewing: SAIM Journal on Computing
  • Journal Reviewing: Games and Economic Behavior
  • Journal Reviewing: International Journal Game Theory
  • Journal Reviewing: Algorithmica
  • Journal Reviewing: Trans. on Econ & Comp.
  • Journal Reviewing: Theory of Computing
  • Committees Served on: Research scholar representative at IIT-Bombay for the year 2008-2009.  
  • PhD thesis of Sadra Yazdanbod, 2018 (Georgia Tech, Advisor: Vijay Vazirani)
  • PhD thesis of Ioannis Panageas, 2016 (Georgia Tech, Advisor: Prasad Tetali)
  • PhD thesis of Eric Chastain, 2016 (Rutgers U., Advisor: Eric Allender)

Honors

  • Outstanding Post-Doctoral Researcher Award, College of Computing, Georgia Tech. (2014)
  • Rising Stars in EECS, 2013. (2013)
  • Excellence in Ph.D. Thesis Award, 2012, IIT-Bombay. (2012)
  • First ACM India Doctoral Dissertation Award 2012 . (2012)
  • Google India Anita Borg Memorial Scholarship 2012. (2012)
  • Part of the 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

  • Teachers Rated as Excellent (Spring'17)

Research Honors

  • NSF CAREER Award (Jan'18)

Recent Courses Taught

  • CS 374 (ECE 374) - 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

Related News