A Caltech Library Service

Algorithms for Playing Games with Limited Randomness

Kalyanaraman, Shankar and Umans, Christopher (2007) Algorithms for Playing Games with Limited Randomness. In: Algorithms – ESA 2007. Lecture Notes in Computer Science. No.4698. Springer Berlin Heidelberg , Berlin, Heidelberg, pp. 323-334. ISBN 9783540755197.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access
Additional Information:© Springer-Verlag Berlin Heidelberg 2007. This research was supported by NSF grant CCF-0346991, BSF Grant 2004329, a Sloan Research Fellowship and an Okawa Foundation research grant.
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2004329
Alfred P. Sloan FoundationUNSPECIFIED
Okawa FoundationUNSPECIFIED
Subject Keywords:Nash Equilibrium; Mixed Strategy; Player Game; Online Algorithm; Congestion Game
Series Name:Lecture Notes in Computer Science
Issue or Number:4698
Record Number:CaltechAUTHORS:20190828-102317126
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98295
Deposited By: George Porter
Deposited On:28 Aug 2019 20:19
Last Modified:16 Nov 2021 17:38

Repository Staff Only: item control page