Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof)
| Autor: | Paul G. Spirakis, Panagiota N. Panagopoulou |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
TheoryofComputation_MISCELLANEOUS
Computer Science::Computer Science and Game Theory Correlated equilibrium Lemke–Howson algorithm Normal-form game Trembling hand perfect equilibrium TheoryofComputation_GENERAL Theoretical Computer Science Combinatorics symbols.namesake Strategy Computational Theory and Mathematics Nash equilibrium Best response symbols Epsilon-equilibrium Mathematics |
| Zdroj: | Theory of Computing Systems. 54:479-490 |
| ISSN: | 1433-0490 1432-4350 |
| DOI: | 10.1007/s00224-013-9446-3 |
| Popis: | We focus on the problem of computing approximate Nash equilibria and well-supported approximate Nash equilibria in random bimatrix games, where each player's payoffs are bounded and independent random variables, not necessarily identically distributed, but with almost common expectations. We show that the completely mixed uniform strategy profile, i.e., the combination of mixed strategies (one per player) where each player plays with equal probability each one of her available pure strategies, is with high probability a $\sqrt{\frac{\ln n}{n}}$ -Nash equilibrium and a $\sqrt{\frac{3\ln n}{n}}$ -well supported Nash equilibrium, where n is the number of pure strategies available to each player. This asserts that the completely mixed, uniform strategy profile is an almost Nash equilibrium for random bimatrix games, since it is, with high probability, an ∈-well-supported Nash equilibrium where ∈ tends to zero as n tends to infinity. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink