Learning Mixed Equilibria

By Drew Fudenberg, David M. Kreps. 1993

We study learning processes for finite strategic-form games, in which players use the history of past play to forecast play in the current period. In a generalization of fictitious play, we assume only that players asymptotically choose best responses to the historical frequencies of opponents′ past play. This implies that if the stage-game strategies converge, the limit is a Nash equilibrium. In the basic model, plays seems unlikely to converge to a mixed-strategy equilibrium, but such convergence is natural when the stage game is perturbed in the manner of Harsanyi′s purification theorem. Journal of Economic Literature Classification Number: C72.

How researchers see this paper

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

Citations in the corpus

Empirically Evaluating Multiagent Learning Algorithms (2014, background): “This algorithm’s general structure has been extended in a number of ways, including smooth ﬁctitious play (Fudenberg and Kreps, 1993), and we will see later that fictitious play provides the foundation for several more modern algorithms.”
Analyzing Complex Strategic Interactions in Multi-Agent Systems (2002, background): “Definitive, positive theoretical properties of equilibrium convergence for general games of A agents and S strategies, have not yet been established (Fudenberg & Kreps 1993; Fudenberg & Levine 1993; Jordan 1993).”
Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria (2005, background): “The case with positive, often referred to as stochastic FP, can be viewed as a smoothed version of the matrix game [20], in which rewards are subject to random perturbations.”
A survey of random processes with reinforcement (2006, background): “s known. (The coordination problems that can arise with two players can be thought of in the same way: a failure to model dependence between the opponent’s plays one’s own plays.) Fudenberg and Kreps [FK93] address these concerns via a greatly generalized framework of optimum response. There chiefco”
Sampling best response dynamics and deterministic equilibrium selection (2015, background): “Hofbauer and Sandholm (2002, 2007) show that stochastically perturbed best response dynamics for supermodular games are monotone dynamical systems, and use this fact to prove convergence results for stochastic fictitious play (Fudenberg and Kreps (1993)). Oyama et al. (2008) establish a comparison t”
A 2£ 2 Game without the Fictitious Play Property ⁄ (1996, background): “Other variations of the process can include deterministic perturbations of payoffs (see, e.g., Robinson, 1951) or stochastic perturbations (see, e.g., Fudenberg and Kreps, 1993).”
Cognition and Behavior in Normal-Form Games: An Experimental Study (2000, unknown): “…even know that they are playing a game, to models in which players have complete models of the structure but simplified models of others' decisions (Fudenberg and Kreps (1993), Crawford (1995), Crawford and Broseta (1998), Ho, Camerer, and Weigelt (1998), Camerer and Ho (1998)) and models whose…”
Thermodynamics as a theory of decision-making with information-processing costs (2012, unknown): “The literature on Boltzmann distributions for decision-making goes back to Luce [71], extending through McFadden [72], Meginnis [73], Fudenberg [74] and Wolpert [55, 75, 50].”
Learning and Equilibrium (2009, background): “To explain this “strategic myopia,” Fudenberg & Kreps (1993) appealed to a “large population model" with many “agents” in each “player role.””
The anatomy of choice: active inference and agency (2013, background): “Boltzmann-like stochastic choice rules have a long history in the psychology and economics literature, particularly in the form of logit choice models (Luce, 1959; Fudenberg and Kreps, 1993).”
Limit Points of Endogenous Misspecified Learning (2020, methodology): “Then we combine an observation from FII with a generalization of the arguments in Fudenberg and Levine (1992) and the Dubins’ upcrossing inequality to guarantee that if the probability initially assigned to the neighborhood is sufficiently high, it is unlikely to drop below the threshold that makes ”
ON THE GLOBAL CONVERGENCE OF STOCHASTIC FICTITIOUS PLAY (2002, methodology): “Fudenberg and Kreps (1993), Kaniovski and Young (1995), and Benaïm and Hirsch (1999a) are therefore able to extend Miyasawa's (1961) result for 2 x 2 games to stochastic fictitious play, proving not only convergence of beliefs to equilibrium, but also convergence of behavior.”
Generalised weakened fictitious play (2006, background): “One of the major recent modifications of fictitious play is stochastic fictitious play (Fudenberg and Kreps, 1993; Benaïm and Hirsch, 1999), in which players use a smooth best response to their beliefs.”
Multi-Agent Reinforcement Learning:a critical survey (2003, background): “Although one could have expected a game theory purist to adopt this perspective, it is not one studied in game theory, and in fact is explicitly rejected in at least one place [Fudenberg and Kreps1993]; we have only seen it pursued recently, outside game theory [Tennenholtz2002].”
If multi-agent learning is the answer, what is the question? (2007, background): “In fact, the only example we know originates in AI rather than game theory [9], and it is explicitly rejected by at least some game theorists [18].”
Modeling the Psychology of Consumer and Firm Behavior with Behavioral Economics (2006, background): “However, the theory builds in a sensible principle that actions with higher expected payoffs are chosen more often - players “better-respond” (cf. Fudenberg and Kreps 1993), rather than “best-respond”.”
Potential Games (1994, background): “…for non-zero-sum games by Miyasawa (1961), Shapley (1964), Deschamps (1973), and lately by Krishna (1991), Milgrom and Roberts (1991), Sela (1992), Fudenberg and Kreps (1993), Jordan (1993), Hofbauer (1994), Krishna and Sjöström (1994), Fudenberg and Levine (1994), Monderer et al. (1994), and…”
Just Starting Out: Learning and Equilibrium in a New Market (2018, unknown): “…aims to derive conditions on the underlying game under which the canonical models of belief-based learning (including fictitious play) and reinforcement learning imply convergence to equilibrium (Milgrom and Roberts 1991, Fudenberg and Kreps 1993, Börgers and Sarin 1997, Hart and Mas-Colell 2000).”