Name
Abstract | ||
|---|---|---|
We 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 ε-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 δ-independent sample spaces) to the algorithms of Lipton, Markakis, and Mehta [LMM03], and the online algorithm of Freund and
Schapire [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 ε-equilibria in time polynomial in the input size n and some function f(k,1/ε). In a similar setting Kannan and Theobald [KT07] 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.
|
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-75520-3_30 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
algorithmic question,different notion,online algorithm,deterministic algorithm,limited randomness,algorithm work,independent sample space,zero-sum game,small rank,approximate equilibrium,zero sum game,mixed strategy | Simultaneous game,Combinatorial game theory,Combinatorics,Repeated game,Symmetric game,Sequential game,Game tree,Example of a game without a value,Mathematics,Randomness | Journal |
Volume | Issue | ISSN |
14 | 059 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-75519-5 | 6 | 0.54 |
References | Authors | |
16 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shankar Kalyanaraman | 1 | 20 | 2.52 |
| Christopher Umans | 2 | 879 | 55.36 |