Approximate Equilibria in Games with Few Players
| dc.creator | Briest, Patrick | |
| dc.creator | Goldberg, Paul W. | |
| dc.creator | Roeglin, Heiko | |
| dc.date | 2008-04-29 | |
| dc.date.accessioned | 2026-07-07T12:18:30Z | |
| dc.date.available | 2026-07-07T12:18:30Z | |
| dc.description | We study the problem of computing approximate Nash equilibria (epsilon-Nash equilibria) in normal form games, where the number of players is a small constant. We consider the approach of looking for solutions with constant support size. It is known from recent work that in the 2-player case, a 1/2-Nash equilibrium can be easily found, but in general one cannot achieve a smaller value of epsilon than 1/2. In this paper we extend those results to the k-player case, and find that epsilon = 1-1/k is feasible, but cannot be improved upon. We show how stronger results for the 2-player case may be used in order to slightly improve upon the epsilon = 1-1/k obtained in the k-player case. | |
| dc.identifier | https://arxiv.org/abs/0804.4524 | |
| dc.identifier | http://arxiv.org/abs/0804.4524 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/212434 | |
| dc.subject | Computer Science and Game Theory | |
| dc.title | Approximate Equilibria in Games with Few Players | |
| dc.type | text |