Playing large games using simple strategies

By Richard Jay Lipton, Evangelos K. Markakis, Aranyak Mehta. 2003

440 citations recorded by the source corpus.

Subfields: Economics and Econometrics, Management Science and Operations Research, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Management Science and Operations Research

In Game & Decision Theory

Citations in the corpus

Settling the complexity of computing two-player Nash equilibria (2007, background): “In fact, by taking advantage of the special structure of Nash’s normal form games, Lipton, Markarkis, and Mehta [40] developed a sub-exponential time algorithm for finding an approximate Nash equilibrium.”
Tight Bounds for Approximate Carathéodory and Beyond (2015, positive): “, 2013), via Frank-Wolfe methods (Garber & Hazan, 2013; Jaggi, 2013) and by sampling (Lipton & Young, 1994; Lipton et al., 2003).”
The complexity of computing a Nash equilibrium (2006, background): “While this question remains open, one may find hope (at least for games with a few players) in the existence of a sub-exponential algorithm [19] running in time O(n 2 ), where n is the size of the game.”
Gradient-Based Algorithms for Finding Nash Equilibria in Extensive Form Games (2007, background): “We note that this is a substantial improvement to the black-box generic complexity bound 3 There has been work on finding -equilibria in two-player normal-form games [11, 12].”
Extensive-form game abstraction with bounds (2014, methodology): “To operationalize them, they have to be accompanied by techniques to compute equilibria, an important topic that has received significant attention in the literature [Littman and Stone 2003; Lipton et al. 2003; Gilpin and Sandholm 2007b; Jiang and Leyton-Brown 2011].”
Nash equilibria in random games (2005, background): “[22]; an investigation into the complexity of finding pure Rényi Institute of Mathematics, Hungarian Academy of Scie n es, and Department of Mathematics, University College London.”
Lossy stochastic game abstraction with bounds (2012, background): “, [19, 18, 10, 16]) and research in the intersection of economics and computer science at large.”
The complexity of computing a Nash equilibrium (2009, background): “While this question remains open, one may find hope (at least for games with a few players) in the existence of a subexponential algorithm 18 running in time O ( n log n / e 2 ), where n is the size of the game.”
The complexity of pure Nash equilibria (2004, background): “Research partially supported by the NSF via grants CCR0121555, CCR-0105533 and ITR grant 331494.”
From Duels to Battlefields: Computing Equilibria of Blotto and Other Games (2016, background): “It has been found that many natural and important classes of games have structure that can be exploited to admit computational results [14, 20, 29, 35].”
Computing the optimal strategy to commit to (2006, background): “A significant amount of research has recently been devoted to the computation of solutions according to various solution concepts for settings in which the agents choose their strategies simultaneously, such as dominance [7, 11, 3] and (especially) Nash equilibrium [8, 21, 16, 15, 2, 22, 23, 4].”