34 citations · 120 across the 32 of their papers we have counts for
6 papers · 1 filter
Settling Some Open Problems on 2-Player Symmetric Nash Equilibria
Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod
Over the years, researchers have studied the complexity of several decision versions of Nash equilibrium in (symmetric) two-player games (bimatrix games). To the best of our knowle…
The Complexity of Genetic Diversity
Ruta Mehta, Ioannis Panageas, Georgios Piliouras +1
A key question in biological systems is whether genetic diversity persists in the long run under evolutionary competition or whether a single dominant genotype emerges. Classic wor…
Settling the Complexity of Arrow-Debreu Markets under Leontief and PLC Utilities, using the Classes FIXP and \Exists-R
Jugal Garg, Ruta Mehta, Vijay V. Vazirani +1
This paper resolves two of the handful of remaining questions on the computability of market equilibria, a central theme within algorithmic game theory (AGT). Our results are as fo…
Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and a Conjecture of Haploid Genetics
Ruta Mehta, Ioannis Panageas, Georgios Piliouras
In a recent series of papers a surprisingly strong connection was discovered between standard models of evolution in mathematical biology and Multiplicative Weights Updates Algorit…
Learning Economic Parameters from Revealed Preferences
Maria-Florina Balcan, Amit Daniely, Ruta Mehta +2
A recent line of work, starting with Beigman and Vohra (2006) and Zadimoghaddam and Roth (2012), has addressed the problem of {\em learning} a utility function from revealed prefer…
Constant Rank Bimatrix Games are PPAD-hard
Ruta Mehta
The rank of a bimatrix game (A,B) is defined as rank(A+B). Computing a Nash equilibrium (NE) of a rank-, i.e., zero-sum game is equivalent to linear programming (von Neumann'28,…