Simple algorithmic techniques to approximate nash equilibria
| Autor: | Panagiota N. Panagopoulou |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
TheoryofComputation_MISCELLANEOUS
Computer Science::Computer Science and Game Theory Computer science ComputingMilieux_PERSONALCOMPUTING TheoryofComputation_GENERAL Performance guarantee symbols.namesake Nash equilibrium Simple (abstract algebra) symbols Bimatrix game Order (group theory) Applied mathematics SIMPLE algorithm |
| Zdroj: | PCI |
| DOI: | 10.1145/3291533.3291535 |
| Popis: | We study the problem of computing approximate Nash equilibria in symmetric bimatrix games. We first give an approximation scheme for Nash equilibria in such games. Even though this scheme is not polynomial-time, it gives an interesting performance guarantee that depends on structural properties of the (exact) Nash equilibria of the game. Next, we propose and experimentally evaluate a simple algorithm for computing approximate Nash equilibria of symmetric 2-player games. Starting from an arbitrary symmetric strategy profile, we continue by repeatedly modifying it slightly, in order to improve the approximation factor achieved. The algorithm is based on letting the players of a new, suitably defined multi-player game perform greedy selfish improvement steps, so that they converge to a strategy profile that corresponds to a sufficiently good approximate Nash equilibrium of the original bimatrix game. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|