Ruta Mehta

According to our database, Ruta Mehta authored at least 78 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Competitive Equilibrium for Chores: from Dual Eisenberg-Gale to a Fast, Greedy, LP-based Algorithm.

Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, Tianlong Nan

CoRR, 2024

Minimization is Harder in the Prophet World.

Vasilis Livanos, Ruta Mehta

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations.

Chandra Chekuri, Pooja Kulkarni, Rucha Kulkarni, Ruta Mehta

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

A Complementary Pivot Algorithm for Competitive Allocation of a Mixed Manna.

Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta

Math. Oper. Res., August, 2023

Approximating APS under Submodular and XOS valuations with Binary Marginals.

Pooja Kulkarni, Rucha Kulkarni, Ruta Mehta

CoRR, 2023

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

Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization.

Aniket Murhekar, Zhuowen Yuan, Bhaskar Ray Chaudhury, Bo Li, Ruta Mehta

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Fair and Efficient Allocation of Indivisible Chores with Surplus.

Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

Maximin Share Allocations for Assignment Valuations.

Pooja Kulkarni, Rucha Kulkarni, Ruta Mehta

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, 2023

2022

Introduction to the Special Issue on WINE'20: Part 1.

Martin Hoefer, Xujin Chen, Nikolai Gravin, Ruta Mehta

ACM Trans. Economics and Comput., 2022

Nash Social Welfare Approximation for Strategic Agents.

Simina Brânzei, Vasilis Gkatzelis, Ruta Mehta

Oper. Res., 2022

On the Envy-free Allocation of Chores.

Lang Yin, Ruta Mehta

CoRR, 2022

Prophet Inequalities for Cost Minimization.

Vasilis Livanos, Ruta Mehta

CoRR, 2022

EFX Allocations: Simplifications and Improvements.

Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta

CoRR, 2022

Online revenue maximization for server pricing.

Shant Boodaghians, Federico Fusco, Stefano Leonardi, Yishay Mansour, Ruta Mehta

Auton. Agents Multi Agent Syst., 2022

Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores.

Shant Boodaghians, Bhaskar Ray Chaudhury, Ruta Mehta

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness.

Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta

Proceedings of the EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11, 2022

Fairness in Federated Learning via Core-Stability.

Bhaskar Ray Chaudhury, Linyi Li, Mintong Kang, Bo Li, Ruta Mehta

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

On the Existence of Competitive Equilibrium with Chores.

Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna.

Vasilis Livanos, Ruta Mehta, Aniket Murhekar

Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, 2022

2021

Fast Algorithms for Rank-1 Bimatrix Games.

Bharat Adsul, Jugal Garg, Ruta Mehta, Milind A. Sohoni, Bernhard von Stengel

Oper. Res., 2021

Competitive Allocation of a Mixed Manna.

Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Indivisible Mixed Manna: On the Computability of MMS+PO Allocations.

Rucha Kulkarni, Ruta Mehta, Setareh Taki

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Improving EFX Guarantees through Rainbow Cycle Number.

Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, Pranabendu Misra

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

On the PTAS for Maximin Shares in an Indivisible Mixed Manna.

Rucha Kulkarni, Ruta Mehta, Setareh Taki

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

Fair and Efficient Allocations under Subadditive Valuations.

Bhaskar Ray Chaudhury, Jugal Garg, Ruta Mehta

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020

An incentive compatible, efficient market for air traffic flow management.

Ruta Mehta, Vijay V. Vazirani

Theor. Comput. Sci., 2020

Unique end of potential line.

John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani

J. Comput. Syst. Sci., 2020

Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores.

Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta

CoRR, 2020

Approximating Maximin Shares with Mixed Manna.

Rucha Kulkarni, Ruta Mehta, Setareh Taki

CoRR, 2020

Smoothed Efficient Algorithms and Reductions for Network Coordination Games.

Shant Boodaghians, Rucha Kulkarni, Ruta Mehta

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Approximate Nash Equilibria of Imitation Games: Algorithms and Complexity.

Aniket Murhekar, Ruta Mehta

Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, 2020

2019

Multiclass Performance Metric Elicitation.

Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta, Oluwasanmi Koyejo

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Performance Metric Elicitation from Pairwise Classifier Comparisons.

Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta, Oluwasanmi Koyejo

Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018

∃R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria.

Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

ACM Trans. Economics and Comput., 2018

Constant Rank Two-Player Games are PPAD-hard.

Ruta Mehta

SIAM J. Comput., 2018

Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm.

Jugal Garg, Ruta Mehta, Vijay V. Vazirani

Math. Oper. Res., 2018

Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium.

Pravesh Kothari, Ruta Mehta

Electron. Colloquium Comput. Complex., 2018

Nash Equilibrium in Smoothed Polynomial Time for Network Coordination Games.

Shant Boodaghians, Rucha Kulkarni, Ruta Mehta

CoRR, 2018

Resource Allocation Game on Social Networks: Best Response Dynamics and Convergence.

Wei-Chun Lee, Vasilis Livanos, Ruta Mehta, Hari Sundaram

CoRR, 2018

Eliciting Binary Performance Metrics.

Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta, Oluwasanmi Koyejo

CoRR, 2018

End of Potential Line.

John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani

CoRR, 2018

Social Welfare and Profit Maximization from Revealed Preferences.

Ziwei Ji, Ruta Mehta, Matus Telgarsky

Proceedings of the Web and Internet Economics - 14th International Conference, 2018

Sum-of-squares meets nash: lower bounds for finding any equilibrium.

Pravesh K. Kothari, Ruta Mehta

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications.

Nikhil R. Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Universal Growth in Production Economies.

Simina Brânzei, Ruta Mehta, Noam Nisan

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Maximizing Profit with Convex Costs in the Random-order Model.

Anupam Gupta, Ruta Mehta, Marco Molinaro

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Nash Equilibrium Computation in Resource Allocation Games.

Shivam Gupta, Ruta Mehta

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

2017

CLS: New Problems and Completeness.

John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani

CoRR, 2017

Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria.

Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Mutation, Sexual Reproduction and Survival in Dynamic Environments.

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, Vijay V. Vazirani

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

Dichotomies in Equilibrium Computation and Membership of PLC Markets in FIXP.

Jugal Garg, Ruta Mehta, Vijay V. Vazirani

Theory Comput., 2016

To Give or not to Give: Fair Division for Strict Preferences.

Simina Brânzei, Yuezhou Lv, Ruta Mehta

CoRR, 2016

Multilinear Games.

Hau Chan, Albert Xin Jiang, Kevin Leyton-Brown, Ruta Mehta

Proceedings of the Web and Internet Economics - 12th International Conference, 2016

To Give or Not to Give: Fair Division for Single Minded Valuations.

Simina Brânzei, Yuezhou Lv, Ruta Mehta

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016

The Computational Complexity of Genetic Diversity.

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Sadra Yazdanbod

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Get Me to My GATE on Time: Efficiently Solving General-Sum Bayesian Threat Screening Games.

Aaron Schlenker, Matthew Brown, Arunesh Sinha, Milind Tambe, Ruta Mehta

Proceedings of the ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands, 2016

2015

A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities.

Jugal Garg, Ruta Mehta, Milind A. Sohoni, Vijay V. Vazirani

SIAM J. Comput., 2015

The game of survival: Sexual evolution in dynamic environments.

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, Vijay V. Vazirani

CoRR, 2015

A Market for Scheduling, with Applications to Cloud Computing.

Nikhil R. Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

CoRR, 2015

Settling Some Open Problems on 2-Player Symmetric Nash Equilibria.

Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and a Conjecture of Haploid Genetics [Working Paper Abstract].

Ruta Mehta, Ioannis Panageas, Georgios Piliouras

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria.

Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

The Complexity of Genetic Diversity: Sex with Two Chromosomes is Advantageous but Unpredictable.

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Sadra Yazdanbod

CoRR, 2014

Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and a Conjecture of Haploid Genetics.

Ruta Mehta, Ioannis Panageas, Georgios Piliouras

CoRR, 2014

Leontief Exchange Markets Can Solve Multivariate Polynomial Equations, Yielding FIXP and ETR Hardness.

Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

CoRR, 2014

To Save Or Not To Save: The Fisher Game.

Ruta Mehta, Nithum Thain, László A. Végh, Adrian Vetta

Proceedings of the Web and Internet Economics - 10th International Conference, 2014

Learning Economic Parameters from Revealed Preferences.

Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner, Vijay V. Vazirani

Proceedings of the Web and Internet Economics - 10th International Conference, 2014

Constant rank bimatrix games are PPAD-hard.

Ruta Mehta

Proceedings of the Symposium on Theory of Computing, 2014

Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions.

Jugal Garg, Ruta Mehta, Vijay V. Vazirani

Proceedings of the Symposium on Theory of Computing, 2014

2013

Exchange Markets: Strategy Meets Supply-Awareness - (Abstract).

Ruta Mehta, Milind A. Sohoni

Proceedings of the Web and Internet Economics - 9th International Conference, 2013

Towards Polynomial Simplex-Like Algorithms for Market Equlibria.

Jugal Garg, Ruta Mehta, Milind A. Sohoni, Nisheeth K. Vishnoi

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities.

Jugal Garg, Ruta Mehta, Milind A. Sohoni, Vijay V. Vazirani

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses.

Jugal Garg, Albert Xin Jiang, Ruta Mehta

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm.

Bharat Adsul, Jugal Garg, Ruta Mehta, Milind A. Sohoni

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm

Bharat Adsul, Jugal Garg, Ruta Mehta, Milind A. Sohoni

CoRR, 2010

Nash Equilibria in Fisher Market.

Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta, Milind A. Sohoni

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

A Simplex-Like Algorithm for Fisher Markets.

Bharat Adsul, Ch. Sobhan Babu, Jugal Garg, Ruta Mehta, Milind A. Sohoni

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010