24 citations · 73 across the 36 of their papers we have counts for
6 papers · 1 filter
Empirical Distribution of Equilibrium Play and Its Testing Application
Yakov Babichenko, Siddharth Barman, Ron Peretz
We show that in any -player -action normal-form game, we can obtain an approximate equilibrium by sampling any mixed-action equilibrium a small number of times. We study thre…
Small-Support Approximate Correlated Equilibria
Yakov Babichenko, Siddharth Barman, Ron Peretz
We prove the existence of approximate correlated equilibrium of support size polylogarithmic in the number of players and the number of actions per player. In particular, using the…
Approximate Nash Equilibria via Sampling
Yakov Babichenko, Ron Peretz
We prove that in a normal form n-player game with m actions for each player, there exists an approximate Nash equilibrium where each player randomizes uniformly among a set of O(lo…
Query Complexity of Correlated Equilibrium
Yakov Babichenko, Siddharth Barman
We study lower bounds on the query complexity of determining correlated equilibrium. In particular, we consider a query model in which an n-player game is specified via a black box…
Query Complexity of Approximate Nash Equilibria
Yakov Babichenko
We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players . Our main result states that for -player binary-action games…
Small Support Equilibria in Large Games
Yakov Babichenko
In this note we provide a new proof for the results of Lipton et al. on the existence of an approximate Nash equilibrium with logarithmic support size. Besides its simplicity, the…