ECCC-Report TR07-059https://eccc.weizmann.ac.il/report/2007/059Comments and Revisions published for TR07-059en-usWed, 11 Jul 2007 16:31:27 +0300
Paper TR07-059
| Algorithms for Playing Games with Limited Randomness |
Shankar Kalyanaraman,
Chris Umans
https://eccc.weizmann.ac.il/report/2007/059We study multiplayer games in which the participants have access to
only limited randomness. This constrains both the algorithms used to
compute equilibria (they should use little or no randomness) as well
as the mixed strategies that the participants are capable of playing
(these should be sparse). We frame algorithmic questions that
naturally arise in this setting, and resolve several of them.
We give deterministic algorithms that can be used to find
sparse $\epsilon$-equilibria in zero-sum and non-zero-sum games, and
a randomness-efficient method for playing repeated zero-sum
games. These results apply ideas from derandomization (expander
walks, and $\delta$-independent sample spaces) to the algorithms of
Lipton, Markakis, and Mehta \cite{LMM03}, and the online algorithm of
Freund and Schapire \cite{FS99}.
Subsequently, we consider a large class of games in which sparse
equilibria are known to exist (and are therefore amenable to
randomness-limited players), namely games of small rank. We give the
first ``fixed-parameter'' algorithms for obtaining approximate
equilibria in these games. For rank-$k$ games, we give a
deterministic algorithm to find $(k+1)$-sparse $\epsilon$-equilibria
in time polynomial in the input size $n$ and some function
$f(k,1/\epsilon)$. In a similar setting Kannan and Theobald
\cite{KT05} gave an algorithm whose run-time is $n^{O(k)}$. Our
algorithm
works for a slightly different notion of a game's ``rank,'' but is
fixed parameter tractable in the above sense, and extends easily to
the multi-player case.
Wed, 11 Jul 2007 16:31:27 +0300https://eccc.weizmann.ac.il/report/2007/059