report
Approximate Equilibria in Games with Few Players
Patrick
Briest
author
Paul W.
Goldberg
author
Heiko
Roeglin
author
63
department
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.
2008
eng
0804.4524
P. Briest, P. W. Goldberg, and H. Roeglin, <i>Approximate Equilibria in Games with Few Players</i>. 2008.
Briest, Patrick, et al. <i>Approximate Equilibria in Games with Few Players</i>. 2008.
@book{Briest_Goldberg_Roeglin_2008, title={Approximate Equilibria in Games with Few Players}, author={Briest, Patrick and Goldberg, Paul W. and Roeglin, Heiko}, year={2008} }
Briest, P., Goldberg, P. W., & Roeglin, H. (2008). <i>Approximate Equilibria in Games with Few Players</i>.
Briest P, Goldberg PW, Roeglin H. <i>Approximate Equilibria in Games with Few Players</i>.; 2008.
Briest, Patrick, Paul W. Goldberg, and Heiko Roeglin. <i>Approximate Equilibria in Games with Few Players</i>, 2008.
P. Briest, P.W. Goldberg, H. Roeglin, Approximate Equilibria in Games with Few Players, 2008.
196882020-09-25T09:52:57Z2022-01-06T06:54:10Z