Nash Equilibria in Random Games

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.

Authors

• Imre Bárány
• Santosh S. Vempala
• Adrian Vetta

Keywords

• Nash equilibrium
• Game theory
• Probability distribution
• Mathematics
• Polynomials
• Algorithm design and analysis
• Educational institutions
• Symmetric matrices
• Gaussian distribution
• Linear programming
• Equilibrium Of The Game
• High Probability
• Payoff Matrix
• Normal Distribution
• Uniform Distribution
• Running Time
• Best Response
• Random Points
• Convex Hull
• Mixed Strategy
• Integrand
• General Position
• Spherically Symmetric
• Points In Dimension
• Pure Strategy
• Support Size
• Pairing Scheme
• Unit Cube
• Non-negative Vector
• Number Of Equilibria