Abstract. An individual's learning rule is completely uncoupled if it does not depend on the actions or payoffs of anyone else. We propose a variant of log linear learning that is completely uncoupled and that selects an efficient pure Nash equilibrium in all generic nperson games that possess at least one pure Nash equilibrium. In games that do not have such an equilibrium, there is a simple formula that expresses the long-run probability of the various disequilibrium states in terms of two factors: i) the sum of payoffs over all agents, and ii) the maximum payoff gain that results from a unilateral deviation by some agent. This welfare/stability trade-off criterion provides a novel framework for analyzing the selection of disequilibrium as well as equilibrium states in n-person games. JEL: C72, C73 2 Game theory has traditionally focussed on situations that involve a small number of players. In these environments it makes sense to assume that players know the structure of the game and can predict the strategic behavior of their opponents. But there are many situations involving huge numbers of players where these assumptions are not particularly persuasive. Commuters in city traffic are engaged in a game because each person's choice of route affects the driving time of many other drivers, yet it is doubtful that anyone 'knows the game' or fully takes into account the strategies of the other players as is usually posited in game theory. Other examples include procedures for routing data on the internet, and the design of information sharing protocols for distributed sensors that are attempting to locate a target. These types of games pose novel and challenging questions. Can such systems equilibrate even though agents are unaware of the strategies and behaviors of most (or perhaps all) of the other agents? What kinds of adaptive learning rules make sense in such environments? How long does it take to reach equilibrium assuming it can be reached at all? And what can be said about the welfare properties of the equilibria that result from particular learning rules? In the last few years the study of these issues has been developing rapidly among computer scientists and distributed control theorists (Papadimitriou, 2001; Roughgarden, 2005; Mannor and Shamma, 2007; Marden and Shamma, 2008; Asadpour and Saberi, 2009; Shah and Shin, 2010) . Concurrently game theorists have been investigating the question of whether decentralized rules can be devised that converge to Nash equilibrium (or correlated equilibrium) in general n-person games Mas-Colell, 2003, 2006; Young, 2003, 2006; Hart and Mansour, 2010) . Among control theorists and computer scientists, the issue is not whether a given learning rule is descriptively accurate as a model of human behavior, but whether it leads to good system-wide performance when agents are endowed with this behavior; in other words the learning procedure and the agents' payoffs are treated as design elements of the system. To date the main focus of attention has been on potential games, since these arise frequently in applications (Marden and Shamma, 2008; . For this class of games there exist extremely simple and intuitively appealing learning procedures that 3 cause the system to equilibrate from any initial conditions. A notable example is logit learning, in which an agent chooses actions with log probabilities that are a linear function of their payoffs. In this case equilibrium occurs at a local or global maximum of the potential function. However, the potential function need not measure the overall welfare of the agents, hence the equilibrium selected may be quite inefficient. This is a well-known problem in congestion games for example. The problem of inefficient equilibrium selection can be overcome by a congestion pricing scheme, but this requires some type of centralized (or at least not fully decentralized) mechanism for determining the price to charge on each route (Sandholm, 1998). The contribution of this paper is to demonstrate a simple learning rule that incorporates log linear learning as one component, and that selects an efficient equilibrium in any game with generic payoffs that possesses at least one pure Nash equilibrium. (An equilibrium is efficient if there is no other equilibrium in which someone is better off and no one is worse off.) By 'select' we mean that, starting from arbitrary initial conditions, the process is in an efficient equilibrium in a high proportion of all time periods. Our learning rule is completely uncoupled, that is, the updating procedure does not depend on the actions or payoffs of anyone else. Thus it can be implemented even in environments where players know nothing about the game, or even whether they are in a game. All they do is react to the pattern of recent payoffs, much as in reinforcement learning (though the rule differs in certain key respects from reinforcement learning). Our notion of selection -in equilibrium a high proportion of the time -is crucial for this result. It is not true that the process converges to equilibrium or even that it converges to equilibrium with high probability. Indeed it can be shown that, for general n-person games, there exist no completely uncoupled rules with finite memory that select a Nash equilibrium in this stronger sense (Babichenko, 2010; see also Hart and Mas-Colell, 2003, 2006). The learning rule that we propose is related to the trial and error learning procedure of Young (2009), and more distantly related to the 'learning by sampling' procedure of Foster and Young (2006) and Germano and Lugosi (2007) . 1 An essential feature of the rule is that a player has two different search modes: i) deliberate experimentation, which occurs with low 1 Another distant relative is the aspiration-based learning model of Karandikar et al. (1998) . In this procedure each player has an endogenously generated aspiration level that is based on a smoothed average of his prior 4 probability and leads to a change of strategy only if the latter has a higher payoff; ii) random search, which leads to a change of strategy that may or may not have a higher payoff (the probability of acceptance is merely biased towards strategies with high payoffs). A crucial difference between our procedure and trial and error learning is that a player does not always accept the outcome of an experiment even when it does result in higher payoffs: acceptance is probabilistic. Our rule also differs in that the probabilities of accepting the outcome of an experiment (or of a random search) can be expressed as a log linear function of the payoff gain (in the case of an experiment) or the payoff level (in the case of a random search). The advantage of this approach is that it leads to a simple formula for computing the stochastically stable states of the process. This formula shows that the learning process selects an efficient pure Nash equilibrium whenever a pure Nash equilibrium exists, and identifies the disequilibrium states that are selected when a pure Nash equilibrium does not exist. In the latter case there is a tradeoff between welfare and stability: the most likely disequilibrium state is one that maximizes a linear combination of: i) the total welfare (sum of payoffs) across all agents and ii) the payoff gain that would result from a deviation by some agent, where the first is weighted positively and the second negatively. We first describe the learning rule informally, then give a detailed definition. A key feature of the rule is that an agent can search in one of two ways. In 'quiet' search he occasionally experiments with new strategies and adopts a new one with a probability that increases with the realized gain in payoff compared to his previous strategy. In 'noisy' search he frequently tries out new strategies and adopts a new one with a probability that increases in the realized level of payoff. These two forms of search can be associated with different 'psychological states'. A content agent is not strongly motivated to search but occasionally does so anyway (quiet search). A discontent agent flails around trying out new things frequently (noisy search). In the first type of search, the probability of acceptance is determined by the change in payoff, whereas in the second situation the probability of acceptance is determined by the level of payoff. The rationale is that in noisy search an agent tries out many different payoffs. He changes strategy with positive probability if his current payoff falls below his current aspirations. Unlike the present method, this procedure does not necessarily lead to Nash equilibrium behavior even in 2 x 2 games. 5 strategies before settling on one of them, hence the payoff level seems more salient than the change in payoff from the previous period. A second feature of the learning process is the mechanism that triggers transitions between content and discontent states. The essential idea is that a transition from content (c) to
A new natural dynamics converging to Nash equilibria with optimal social welfare in general games has been proposed in REF .
Learning Efficient Nash Equilibria in Distributed Systems
Computer Science Economics