SODA Conference 2019 Conference Paper
Theorems of Carathéodory, Helly, and Tverberg without dimension
- Karim A. Adiprasito
- Imre Bárány
- Nabil H. Mustafa
Author name cluster
Imre Bárány
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
3 papers
1 author row
Possible papers
3FOCS Conference 2005 Conference Paper
Nash Equilibria in Random Games
- Imre Bárány
- Santosh S. Vempala
- Adrian Vetta
We consider Nash equilibria in 2-player random games and analyze a simple Las Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a Nash equilibrium; on m /spl times/ n payoff matrices, it runs in time O(m/sup 2/n log log n + n/sup 2/m log log m) with high probability. Our main tool is a polytope formulation of equilibria.