Approximate Equilibria in Games with Few Players
Briest, Patrick
Goldberg, Paul W.
Roeglin, Heiko
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
info:eu-repo/semantics/report
doc-type:report
text
http://purl.org/coar/resource_type/c_93fc
https://ris.uni-paderborn.de/record/19688
Briest P, Goldberg PW, Roeglin H. <i>Approximate Equilibria in Games with Few Players</i>.; 2008.
eng
info:eu-repo/semantics/altIdentifier/arxiv/0804.4524
info:eu-repo/semantics/closedAccess