A polynomial-time nash equilibrium algorithm for repeated games

By Michael L. Littman, Peter Stone. 2003

157 citations recorded by the source corpus.

Subfields: Economics and Econometrics, Management Science and Operations Research

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

Citations in the corpus

Learning to compete, coordinate, and cooperate in repeated games using reinforcement learning (2011, methodology): “Littman and Stone (2005) give an algorithm to compute the rNE corresponding to the NBS (Nash 1950).”
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].”
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].”
Lossy stochastic game abstraction with bounds (2012, background): “, [19, 18, 10, 16]) and research in the intersection of economics and computer science at large.”
AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents (2003, background): “Interestingly, a recent paper shows that when players are interested in their average payoffs, such equilibria can be constructed in worst-case polynomial time (Littman & Stone, 2003).”
Social reward shaping in the prisoner's dilemma (2008, background): “This extension should be relatively simple, since polynomial-time algorithms for finding subgame perfect equilibria exist [3].”
A Polynomial-time Nash Equilibrium Algorithm for Repeated Stochastic Games (2008, background): “Littman and Stone (2005) provide details on using the attack strategies to stabilize the discovered mutually beneficial payoffs, which we do not repeat here.”
Reaching pareto-optimality in prisoner’s dilemma using conditional joint action learning (2007, background): “As a result a number of learning mechanisms were discovered which were proved to converge to Nash Equilibrium under certain conditions (Hu & Wellman 2003; Littman 1994; Conitzer & Sandholm 2003; Littman & Stone 2005; Bowling & Veloso 2004).”
An Overview of Cooperative and Competitive Multiagent Learning (2005, background): “The work of [96] shows how to construct equilibriums for players that are interested in average payoffs for repeated games in polynomial time.”
Cooperative Multi-Agent Learning: The State of the Art (2005, background): “Stone and Veloso [255] argue that unrestricted communication reduces a multi-agent system to something isomorphic to a single-agent system.”