34 citations · 120 across the 32 of their papers we have counts for
9 papers · 1 filter
Fast Algorithms for Rank-1 Bimatrix Games
Bharat Adsul, Jugal Garg, Ruta Mehta +2
The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. This paper comprehensively analyzes games of rank one, and shows the following: (1) For a game…
Unique End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta +1
This paper studies the complexity of problems in PPAD PLS that have unique solutions. Three well-known examples of such problems are the problem of finding a fixpoint of a c…
Smoothed Efficient Algorithms and Reductions for Network Coordination Games
Shant Boodaghians, Rucha Kulkarni, Ruta Mehta
Worst-case hardness results for most equilibrium computation problems have raised the need for beyond-worst-case analysis. To this end, we study the smoothed complexity of finding…
Resource Allocation Game on Social Networks: Best Response Dynamics and Convergence
Wei-Chun Lee, Vasilis Livanos, Ruta Mehta +1
The decisions that human beings make to allocate time has significant bearing on economic output and to the sustenance of social networks. The time allocation problem motivates our…
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium
Pravesh K. Kothari, Ruta Mehta
Several works have shown unconditional hardness (via integrality gaps) of computing equilibria using strong hierarchies of convex relaxations. Such results however only apply to th…
Performance Metric Elicitation from Pairwise Classifier Comparisons
Gaurush Hiranandani, Shant Boodaghians, Ruta Mehta +1
Given a binary prediction problem, which performance metric should the classifier optimize? We address this question by formalizing the problem of Metric Elicitation. The goal of m…
Maximizing Profit with Convex Costs in the Random-order Model
Anupam Gupta, Ruta Mehta, Marco Molinaro
Suppose a set of requests arrives online: each request gives some value if accepted, but requires using some amount of each of resources. Our cost is a convex function of…
End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta +1
We introduce the problem EndOfPotentialLine and the corresponding complexity class EOPL of all problems that can be reduced to it in polynomial time. This class captures problems t…
Universal Growth in Production Economies
Simina Brânzei, Ruta Mehta, Noam Nisan
We consider a simple variant of the von Neumann model of an expanding economy, in which multiple producers make goods according to their production function. The players trade thei…