AN ITERATIVE METHOD OF SOLVING A GAME

By J. Robinson. 1951

Abstract : In the paper, demonstration is made of the validity of an iterative procedure suggested by George W. Brown for a two-person game. This method corresponds to each player choosing in turn the best pure strategy against the accumulated mixed strategy of his opponent up to then.

Subfields: Game & Decision Theory, Algorithms & Complexity

How researchers see this paper

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

In Game & Decision Theory

In Algorithms & Complexity

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “Fictitious Play and Best Response-Based Iterative Algorithms Fictitious play (FP) is a classic iterative procedure for computing policies in (normal-form) games [12, 57].”
Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness (2017, background): “The disadvantage is that Fictitious Play is only known to converge to equilibrium in the limit (Robinson, 1951), rather than in a polynomial number of rounds (though it is conjectured to converge quickly under rather general circumstances; see (Daskalakis & Pan, 2014) for a recent discussion).”
Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, methodology): “…we choose decentralized PG in this paper, RR can be combined with any other multi-agent learning algorithms for games, such as ﬁctitious play (Robinson, 1951; Monderer & Shapley, 1996; Heinrich & Silver, 2016; Kamra et al., 2019; Han & Hu, 2019), double-oracle (McMahan et al., 2003; Lanctot…”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, methodology): “A general algorithm scheme was developed for solving this problem in which the min and max players each run a simple learning procedure in tandem (Robinson, 1951).”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, background): “Most of these methods belong to one of the following two families: fictitious play (Brown, 1951; Robinson, 1951), and counterfactual regret minimization (Zinkevich et al.”
Deep Fictitious Play for Finding Markovian Nash Equilibrium in Multi-Agent Games (2019, background): “Even in the static finite-action games, there are numerous examples when it converges (Robinson (1951); Miyasawa (1961); Milgrom and Roberts (1991); Monderer and Shapley (1996b,a); Berger (2005); Hofbauer and Sandholm (2002)) and when it does not (Shapley (1964); Jordan (1993); Monderer and Sela…”
Introduction to Multi-Armed Bandits (2019, background): “e., the historical frequency distribution over the arms). CHAPTER 9. BANDITS AND GAMES 111 Introduced in Brown (1949), ﬁctitious play was proved to converge at the rate O(t 1=n) for n ngame matrices (Robinson, 1951). This convergence rate is the best possible (Daskalakis and Pan, 2014). While all co”
The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization (2018, background): “This has been the topic of a long line of investigation starting with Julia Robinson’s celebrated analysis of ﬁctitious play [4, 20], and leading to the development of no-regret learning [5].”
Efficient Exploration via State Marginal Matching (2019, background): “A slight variant, fictitious play (Brown, 1951) does converge to a Nash equilibrium in finite time (Robinson, 1951; Daskalakis & Pan, 2014).”