Uncoupled Learning Rules for Seeking Equilibria in Repeated Plays: An Overview
---
paper_title: Prediction, Learning, and Games

paper_content:

1. Introduction 2. Prediction with expert advice 3. Tight bounds for specific losses 4. Randomized prediction 5. Efficient forecasters for large classes of experts 6. Prediction with limited feedback 7. Prediction and playing games 8. Absolute loss 9. Logarithmic loss 10. Sequential investment 11. Linear pattern recognition 12. Linear classification 13. Appendix.
---
paper_title: Decentralized dynamic spectrum access for cognitive radios: cooperative design of a non-cooperative game

paper_content:

We consider dynamic spectrum access among cognitive radios from an adaptive, game theoretic learning perspective. Spectrum-agile cognitive radios compete for channels temporarily vacated by licensed primary users in order to satisfy their own demands while minimizing interference. For both slowly varying primary user activity and slowly varying statistics of "fast" primary user activity, we apply an adaptive regret based learning procedure which tracks the set of correlated equilibria of the game, treated as a distributed stochastic approximation. This procedure is shown to perform very well compared with other similar adaptive algorithms. We also estimate channel contention for a simple CSMA channel sharing scheme.
---
paper_title: Nash Equilibrium Seeking in Noncooperative Games

paper_content:

We introduce a non-model based approach for locally stable convergence to Nash equilibria in static, noncooperative games with N players. In classical game theory algorithms, each player employs the knowledge of the functional form of his payoff and the knowledge of the other players' actions, whereas in the proposed algorithm, the players need to measure only their own payoff values. This strategy is based on the extremum seeking approach, which has previously been developed for standard optimization problems and employs sinusoidal perturbations to estimate the gradient. We consider static games with quadratic payoff functions before generalizing our results to games with non-quadratic payoff functions that are the output of a dynamic system. Specifically, we consider general nonlinear differential equations with N inputs and N outputs, where in the steady state, the output signals represent the payoff functions of a noncooperative game played by the steady-state values of the input signals. We employ the standard local averaging theory and obtain local convergence results for both quadratic payoffs, where the actual convergence is semi-global, and non-quadratic payoffs, where the potential existence of multiple Nash equilibria precludes semi-global convergence. Our convergence conditions coincide with conditions that arise in model-based Nash equilibrium seeking. However, in our framework the user is not meant to check these conditions because the payoff functions are presumed to be unknown. For non-quadratic payoffs, convergence to a Nash equilibrium is not perfect, but is biased in proportion to the perturbation amplitudes and the higher derivatives of the payoff functions. We quantify the size of these residual biases and confirm their existence numerically in an example noncooperative game. In this example, we present the first application of extremum seeking with projection to ensure that the players' actions remain in a given closed and bounded action set.
---
paper_title: The Theory of Learning in Games

paper_content:

In economics, most noncooperative game theory has focused on equilibrium in games, especially Nash equilibrium and its refinements. The traditional explanation for when and why equilibrium arises is that it results from analysis and introspection by the players in a situation where the rules of the game, the rationality of the players, and the players' payoff functions are all common knowledge. Both conceptually and empirically, this theory has many problems. In The Theory of Learning in Games Drew Fudenberg and David Levine develop an alternative explanation that equilibrium arises as the long-run outcome of a process in which less than fully rational players grope for optimality over time. The models they explore provide a foundation for equilibrium theory and suggest useful ways for economists to evaluate and modify traditional equilibrium concepts.
---
paper_title: Distributed Seeking of Nash Equilibria With Applications to Mobile Sensor Networks

paper_content:

We consider the problem of distributed convergence to a Nash equilibrium in a noncooperative game where the players generate their actions based only on online measurements of their individual cost functions, corrupted with additive measurement noise. Exact analytical forms and/or parameters of the cost functions, as well as the current actions of the players may be unknown. Additionally, the players' actions are subject to linear dynamic constraints. We propose an algorithm based on discrete-time stochastic extremum seeking using sinusoidal perturbations and prove its almost sure convergence to a Nash equilibrium. We show how the proposed algorithm can be applied to solving coordination problems in mobile sensor networks, where motion dynamics of the players can be modeled as: 1) single integrators (velocity-actuated vehicles), 2) double integrators (force-actuated vehicles), and 3) unicycles (a kinematic model with nonholonomic constraints). Examples are given in which the cost functions are selected such that the problems of connectivity control, formation control, rendezvous and coverage control are solved in an adaptive and distributed way. The methodology is illustrated through simulations.
---
paper_title: Stochastic Uncoupled Dynamics and Nash Equilibrium

paper_content:

In this paper we consider dynamic processes, in repeated games, that are subject to the natural informational restriction of uncoupledness. We study the almost sure convergence to Nash equilibria, and present a number of possibility and impossibility results. Basically, we show that if in addition to random moves some recall is introduced, then successful search procedures that are uncoupled can be devised. In particular, to get almost sure convergence to pure Nash equilibria when these exist, it su±ces to recall the last two periods of play.
---
paper_title: Prediction, Learning, and Games

paper_content:

1. Introduction 2. Prediction with expert advice 3. Tight bounds for specific losses 4. Randomized prediction 5. Efficient forecasters for large classes of experts 6. Prediction with limited feedback 7. Prediction and playing games 8. Absolute loss 9. Logarithmic loss 10. Sequential investment 11. Linear pattern recognition 12. Linear classification 13. Appendix.
---
paper_title: Stochastic Uncoupled Dynamics and Nash Equilibrium

paper_content:

In this paper we consider dynamic processes, in repeated games, that are subject to the natural informational restriction of uncoupledness. We study the almost sure convergence to Nash equilibria, and present a number of possibility and impossibility results. Basically, we show that if in addition to random moves some recall is introduced, then successful search procedures that are uncoupled can be devised. In particular, to get almost sure convergence to pure Nash equilibria when these exist, it su±ces to recall the last two periods of play.
---
paper_title: Learning by Trial and Error

paper_content:

A person learns by trial and error if he occasionally tries out new strategies, rejecting choices that are erroneous in the sense that they do not lead to higher payoffs. In a game, however, strategies can become erroneous due to a change of behavior by someone else. We introduce a learning rule in which behavior is conditional on whether a player experiences an error of the first or second type. This rule, called interactive trial and error learning, implements Nash equilibrium behavior in any game with generic payoffs and at least one pure Nash equilibrium.
---
paper_title: Regret Testing: Learning to Play Nash Equilibrium without Knowing you have an Opponent

paper_content:

A learning rule is uncoupled if a player does not condition his strategy on the opponent's payoffs. It is radically uncoupled if a player does not condition his strategy on the opponent's actions or payoffs. We demonstrate a family of simple, radically uncoupled learning rules whose period-by-period behavior comes arbitrarily close to Nash equilibrium behavior in any finite two-person game.
---
paper_title: Strategic Learning and Its Limits

paper_content:

In this concise book based on his Arne Ryde Lectures in 2002, Young suggests a conceptual framework for studying strategic learning and highlights theoretical developments in the area. He discusses the interactive learning problem; reinforcement and regret; equilibrium; conditional no-regret learning; prediction, postdiction, and calibration; fictitious play and its variants; Bayesian learning; and hypothesis testing. Young's framework emphasizes the amount of information required to implement different types of learning rules, criteria for evaluating their performance, and alternative notions of equilibrium to which they converge. He also stresses the limits of what can be achieved: for a given type of game and a given amount of information, there may exist no learning procedure that satisfies certain reasonable criteria of performance and convergence. In short, Young has provided a valuable primer that delineates what we know, what we would like to know, and the limits of what we can know, when we try to learn about a system that is composed of other learners.
---
paper_title: Prediction, Learning, and Games

paper_content:

1. Introduction 2. Prediction with expert advice 3. Tight bounds for specific losses 4. Randomized prediction 5. Efficient forecasters for large classes of experts 6. Prediction with limited feedback 7. Prediction and playing games 8. Absolute loss 9. Logarithmic loss 10. Sequential investment 11. Linear pattern recognition 12. Linear classification 13. Appendix.
---
paper_title: Prediction, Learning, and Games

paper_content:

1. Introduction 2. Prediction with expert advice 3. Tight bounds for specific losses 4. Randomized prediction 5. Efficient forecasters for large classes of experts 6. Prediction with limited feedback 7. Prediction and playing games 8. Absolute loss 9. Logarithmic loss 10. Sequential investment 11. Linear pattern recognition 12. Linear classification 13. Appendix.
---
paper_title: A simple adaptive procedure leading to correlated equilibrium

paper_content:

We propose a new and simple adaptive procedure for playing a game: "regret-matching." In this procedure, players depart from their current play with probabilities that are proportional to measures of regret for not having used other strategies in the past. It is shown that our adaptive procedure guarantees that, with probability one, the empirical distributions of play converge to the set of correlated equilibria of the game. To compute these regret measures, a player needs to know his payoff function and the history of play. We also offer a variation where every player knows only his own realized payoff history (but not his payoff function).
---
paper_title: A reinforcement procedure leading to correlated equilibrium

paper_content:

We consider repeated games where at any period each player knows only his set of actions and the stream of payoffs that he has received in the past. He knows neither his own payoff function, nor the characteristics of the other players (how many there are, their strategies and payoffs). In this context, we present an adaptive procedure for play called “modified-regret-matching” — which is interpretable as a stimulus-response or reinforcement procedure, and which has the property that any limit point of the empirical distribution of play is a correlated equilibrium of the stage game.
---
paper_title: Stochastic Uncoupled Dynamics and Nash Equilibrium

paper_content:

In this paper we consider dynamic processes, in repeated games, that are subject to the natural informational restriction of uncoupledness. We study the almost sure convergence to Nash equilibria, and present a number of possibility and impossibility results. Basically, we show that if in addition to random moves some recall is introduced, then successful search procedures that are uncoupled can be devised. In particular, to get almost sure convergence to pure Nash equilibria when these exist, it su±ces to recall the last two periods of play.
---
paper_title: Regret Testing: Learning to Play Nash Equilibrium without Knowing you have an Opponent

paper_content:

A learning rule is uncoupled if a player does not condition his strategy on the opponent's payoffs. It is radically uncoupled if a player does not condition his strategy on the opponent's actions or payoffs. We demonstrate a family of simple, radically uncoupled learning rules whose period-by-period behavior comes arbitrarily close to Nash equilibrium behavior in any finite two-person game.
---
paper_title: A reinforcement procedure leading to correlated equilibrium

paper_content:

We consider repeated games where at any period each player knows only his set of actions and the stream of payoffs that he has received in the past. He knows neither his own payoff function, nor the characteristics of the other players (how many there are, their strategies and payoffs). In this context, we present an adaptive procedure for play called “modified-regret-matching” — which is interpretable as a stimulus-response or reinforcement procedure, and which has the property that any limit point of the empirical distribution of play is a correlated equilibrium of the stage game.
---
paper_title: A simple adaptive procedure leading to correlated equilibrium

paper_content:

We propose a new and simple adaptive procedure for playing a game: "regret-matching." In this procedure, players depart from their current play with probabilities that are proportional to measures of regret for not having used other strategies in the past. It is shown that our adaptive procedure guarantees that, with probability one, the empirical distributions of play converge to the set of correlated equilibria of the game. To compute these regret measures, a player needs to know his payoff function and the history of play. We also offer a variation where every player knows only his own realized payoff history (but not his payoff function).
---
paper_title: Strategic Learning and Its Limits

paper_content:

In this concise book based on his Arne Ryde Lectures in 2002, Young suggests a conceptual framework for studying strategic learning and highlights theoretical developments in the area. He discusses the interactive learning problem; reinforcement and regret; equilibrium; conditional no-regret learning; prediction, postdiction, and calibration; fictitious play and its variants; Bayesian learning; and hypothesis testing. Young's framework emphasizes the amount of information required to implement different types of learning rules, criteria for evaluating their performance, and alternative notions of equilibrium to which they converge. He also stresses the limits of what can be achieved: for a given type of game and a given amount of information, there may exist no learning procedure that satisfies certain reasonable criteria of performance and convergence. In short, Young has provided a valuable primer that delineates what we know, what we would like to know, and the limits of what we can know, when we try to learn about a system that is composed of other learners.
---
paper_title: Regret Testing: Learning to Play Nash Equilibrium without Knowing you have an Opponent

paper_content:

A learning rule is uncoupled if a player does not condition his strategy on the opponent's payoffs. It is radically uncoupled if a player does not condition his strategy on the opponent's actions or payoffs. We demonstrate a family of simple, radically uncoupled learning rules whose period-by-period behavior comes arbitrarily close to Nash equilibrium behavior in any finite two-person game.
---
paper_title: Regret Testing: Learning to Play Nash Equilibrium without Knowing you have an Opponent

paper_content:

A learning rule is uncoupled if a player does not condition his strategy on the opponent's payoffs. It is radically uncoupled if a player does not condition his strategy on the opponent's actions or payoffs. We demonstrate a family of simple, radically uncoupled learning rules whose period-by-period behavior comes arbitrarily close to Nash equilibrium behavior in any finite two-person game.
---
paper_title: Regret Testing: Learning to Play Nash Equilibrium without Knowing you have an Opponent

paper_content:

A learning rule is uncoupled if a player does not condition his strategy on the opponent's payoffs. It is radically uncoupled if a player does not condition his strategy on the opponent's actions or payoffs. We demonstrate a family of simple, radically uncoupled learning rules whose period-by-period behavior comes arbitrarily close to Nash equilibrium behavior in any finite two-person game.
---
paper_title: Prediction, Learning, and Games

paper_content:

1. Introduction 2. Prediction with expert advice 3. Tight bounds for specific losses 4. Randomized prediction 5. Efficient forecasters for large classes of experts 6. Prediction with limited feedback 7. Prediction and playing games 8. Absolute loss 9. Logarithmic loss 10. Sequential investment 11. Linear pattern recognition 12. Linear classification 13. Appendix.
---
paper_title: Regret Testing: Learning to Play Nash Equilibrium without Knowing you have an Opponent

paper_content:

A learning rule is uncoupled if a player does not condition his strategy on the opponent's payoffs. It is radically uncoupled if a player does not condition his strategy on the opponent's actions or payoffs. We demonstrate a family of simple, radically uncoupled learning rules whose period-by-period behavior comes arbitrarily close to Nash equilibrium behavior in any finite two-person game.
---
paper_title: Learning by Trial and Error

paper_content:

A person learns by trial and error if he occasionally tries out new strategies, rejecting choices that are erroneous in the sense that they do not lead to higher payoffs. In a game, however, strategies can become erroneous due to a change of behavior by someone else. We introduce a learning rule in which behavior is conditional on whether a player experiences an error of the first or second type. This rule, called interactive trial and error learning, implements Nash equilibrium behavior in any game with generic payoffs and at least one pure Nash equilibrium.
---
paper_title: Prediction, Learning, and Games

paper_content:

1. Introduction 2. Prediction with expert advice 3. Tight bounds for specific losses 4. Randomized prediction 5. Efficient forecasters for large classes of experts 6. Prediction with limited feedback 7. Prediction and playing games 8. Absolute loss 9. Logarithmic loss 10. Sequential investment 11. Linear pattern recognition 12. Linear classification 13. Appendix.
---
paper_title: Stochastic Uncoupled Dynamics and Nash Equilibrium

paper_content:

In this paper we consider dynamic processes, in repeated games, that are subject to the natural informational restriction of uncoupledness. We study the almost sure convergence to Nash equilibria, and present a number of possibility and impossibility results. Basically, we show that if in addition to random moves some recall is introduced, then successful search procedures that are uncoupled can be devised. In particular, to get almost sure convergence to pure Nash equilibria when these exist, it su±ces to recall the last two periods of play.
---
paper_title: Learning Efficient Nash Equilibria in Distributed Systems

paper_content:

An individualʼs learning rule is completely uncoupled if it does not depend directly 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 (welfare-maximizing) pure Nash equilibrium in all generic n-person 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.
---
paper_title: Learning by Trial and Error

paper_content:

A person learns by trial and error if he occasionally tries out new strategies, rejecting choices that are erroneous in the sense that they do not lead to higher payoffs. In a game, however, strategies can become erroneous due to a change of behavior by someone else. We introduce a learning rule in which behavior is conditional on whether a player experiences an error of the first or second type. This rule, called interactive trial and error learning, implements Nash equilibrium behavior in any game with generic payoffs and at least one pure Nash equilibrium.
---
paper_title: Learning Efficient Nash Equilibria in Distributed Systems

paper_content:

An individualʼs learning rule is completely uncoupled if it does not depend directly 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 (welfare-maximizing) pure Nash equilibrium in all generic n-person 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.
---
paper_title: Learning by Trial and Error

paper_content:

A person learns by trial and error if he occasionally tries out new strategies, rejecting choices that are erroneous in the sense that they do not lead to higher payoffs. In a game, however, strategies can become erroneous due to a change of behavior by someone else. We introduce a learning rule in which behavior is conditional on whether a player experiences an error of the first or second type. This rule, called interactive trial and error learning, implements Nash equilibrium behavior in any game with generic payoffs and at least one pure Nash equilibrium.
---
paper_title: Nash Equilibrium Seeking in Noncooperative Games

paper_content:

We introduce a non-model based approach for locally stable convergence to Nash equilibria in static, noncooperative games with N players. In classical game theory algorithms, each player employs the knowledge of the functional form of his payoff and the knowledge of the other players' actions, whereas in the proposed algorithm, the players need to measure only their own payoff values. This strategy is based on the extremum seeking approach, which has previously been developed for standard optimization problems and employs sinusoidal perturbations to estimate the gradient. We consider static games with quadratic payoff functions before generalizing our results to games with non-quadratic payoff functions that are the output of a dynamic system. Specifically, we consider general nonlinear differential equations with N inputs and N outputs, where in the steady state, the output signals represent the payoff functions of a noncooperative game played by the steady-state values of the input signals. We employ the standard local averaging theory and obtain local convergence results for both quadratic payoffs, where the actual convergence is semi-global, and non-quadratic payoffs, where the potential existence of multiple Nash equilibria precludes semi-global convergence. Our convergence conditions coincide with conditions that arise in model-based Nash equilibrium seeking. However, in our framework the user is not meant to check these conditions because the payoff functions are presumed to be unknown. For non-quadratic payoffs, convergence to a Nash equilibrium is not perfect, but is biased in proportion to the perturbation amplitudes and the higher derivatives of the payoff functions. We quantify the size of these residual biases and confirm their existence numerically in an example noncooperative game. In this example, we present the first application of extremum seeking with projection to ensure that the players' actions remain in a given closed and bounded action set.
---
paper_title: Prediction, Learning, and Games

paper_content:

1. Introduction 2. Prediction with expert advice 3. Tight bounds for specific losses 4. Randomized prediction 5. Efficient forecasters for large classes of experts 6. Prediction with limited feedback 7. Prediction and playing games 8. Absolute loss 9. Logarithmic loss 10. Sequential investment 11. Linear pattern recognition 12. Linear classification 13. Appendix.
---
paper_title: The Theory of Learning in Games

paper_content:

In economics, most noncooperative game theory has focused on equilibrium in games, especially Nash equilibrium and its refinements. The traditional explanation for when and why equilibrium arises is that it results from analysis and introspection by the players in a situation where the rules of the game, the rationality of the players, and the players' payoff functions are all common knowledge. Both conceptually and empirically, this theory has many problems. In The Theory of Learning in Games Drew Fudenberg and David Levine develop an alternative explanation that equilibrium arises as the long-run outcome of a process in which less than fully rational players grope for optimality over time. The models they explore provide a foundation for equilibrium theory and suggest useful ways for economists to evaluate and modify traditional equilibrium concepts.
---
paper_title: An Iterative Method of Solving a Game

paper_content:

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.
---
paper_title: On the Global Convergence of Stochastic Fictitious Play

paper_content:

We establish global convergence results for stochastic fictitious play for four classes of games: games with an interior ESS, zero sum games, potential games, and supermodular games. We do so by appealing to techniques from stochastic approximation theory, which relate the limit behavior of a stochastic process to the limit behavior of a differential equation defined by the expected motion of the process. The key result in our analysis of supermodular games is that the relevant differential equation defines a strongly monotone dynamical system. Our analyses of the other cases combine Lyapunov function arguments with a discrete choice theory result: that the choice probabilities generated by any additive random utility model can be derived from a deterministic model based on payoff perturbations that depend nonlinearly on the vector of choice probabilities.
---
paper_title: Learning by Trial and Error

paper_content:

A person learns by trial and error if he occasionally tries out new strategies, rejecting choices that are erroneous in the sense that they do not lead to higher payoffs. In a game, however, strategies can become erroneous due to a change of behavior by someone else. We introduce a learning rule in which behavior is conditional on whether a player experiences an error of the first or second type. This rule, called interactive trial and error learning, implements Nash equilibrium behavior in any game with generic payoffs and at least one pure Nash equilibrium.
---
paper_title: Stochastic Uncoupled Dynamics and Nash Equilibrium

paper_content:

In this paper we consider dynamic processes, in repeated games, that are subject to the natural informational restriction of uncoupledness. We study the almost sure convergence to Nash equilibria, and present a number of possibility and impossibility results. Basically, we show that if in addition to random moves some recall is introduced, then successful search procedures that are uncoupled can be devised. In particular, to get almost sure convergence to pure Nash equilibria when these exist, it su±ces to recall the last two periods of play.
---
paper_title: Nash Equilibrium Seeking in Noncooperative Games

paper_content:

We introduce a non-model based approach for locally stable convergence to Nash equilibria in static, noncooperative games with N players. In classical game theory algorithms, each player employs the knowledge of the functional form of his payoff and the knowledge of the other players' actions, whereas in the proposed algorithm, the players need to measure only their own payoff values. This strategy is based on the extremum seeking approach, which has previously been developed for standard optimization problems and employs sinusoidal perturbations to estimate the gradient. We consider static games with quadratic payoff functions before generalizing our results to games with non-quadratic payoff functions that are the output of a dynamic system. Specifically, we consider general nonlinear differential equations with N inputs and N outputs, where in the steady state, the output signals represent the payoff functions of a noncooperative game played by the steady-state values of the input signals. We employ the standard local averaging theory and obtain local convergence results for both quadratic payoffs, where the actual convergence is semi-global, and non-quadratic payoffs, where the potential existence of multiple Nash equilibria precludes semi-global convergence. Our convergence conditions coincide with conditions that arise in model-based Nash equilibrium seeking. However, in our framework the user is not meant to check these conditions because the payoff functions are presumed to be unknown. For non-quadratic payoffs, convergence to a Nash equilibrium is not perfect, but is biased in proportion to the perturbation amplitudes and the higher derivatives of the payoff functions. We quantify the size of these residual biases and confirm their existence numerically in an example noncooperative game. In this example, we present the first application of extremum seeking with projection to ensure that the players' actions remain in a given closed and bounded action set.
---
paper_title: Learning by Trial and Error

paper_content:

A person learns by trial and error if he occasionally tries out new strategies, rejecting choices that are erroneous in the sense that they do not lead to higher payoffs. In a game, however, strategies can become erroneous due to a change of behavior by someone else. We introduce a learning rule in which behavior is conditional on whether a player experiences an error of the first or second type. This rule, called interactive trial and error learning, implements Nash equilibrium behavior in any game with generic payoffs and at least one pure Nash equilibrium.
---
paper_title: Prediction, Learning, and Games

paper_content:

1. Introduction 2. Prediction with expert advice 3. Tight bounds for specific losses 4. Randomized prediction 5. Efficient forecasters for large classes of experts 6. Prediction with limited feedback 7. Prediction and playing games 8. Absolute loss 9. Logarithmic loss 10. Sequential investment 11. Linear pattern recognition 12. Linear classification 13. Appendix.
---
paper_title: A note on approximate Nash equilibria

paper_content:

In view of the intractability of finding a Nash equilibrium, it is important to understand the limits of approximation in this context. A subexponential approximation scheme is known [LMM03], and no approximation better than 1 4 is possible by any algorithm that examines equilibria involving fewer than log n strategies [Alt94]. We give a simple, linear-time algorithm examining just two strategies per player and resulting in a 1 2-approximate Nash equilibrium in any 2-player game. For the more demanding notion of well-supported approximate equilibrium due to [DGP06] no nontrivial bound is known; we show that the problem can be reduced to the case of win-lose games (games with all utilities 0-1), and that an approximation of 5 6 is possible contingent upon a graph-theoretic conjecture.
---
paper_title: Learning Efficient Nash Equilibria in Distributed Systems

paper_content:

An individualʼs learning rule is completely uncoupled if it does not depend directly 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 (welfare-maximizing) pure Nash equilibrium in all generic n-person 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.
---
paper_title: Evolution and Equilibrium under Inexact Information

paper_content:

Abstract We study a general model of stochastic evolution in games, assuming in which players have inexact information about the game's payoffs or the population state. We show that when the population is large, its behavior over finite time spans follows an almost deterministic trajectory. While this result provides a useful description of disequilibrium behavior adjustment, it tells us little about equilibrium play. To address this issue, we establish that the equilibrium behavior of a large population can be approximated by a diffusion. We then propose a new notion of stability called local probabilistic stability (LPS), which requires that a population which begins play in equilibrium settle into a fixed stochastic pattern around the equilibrium. We use the diffusion approximation to prove a simple characterization of LPS. While LPS accords closely with standard deterministic notions of stability at interior equilibria, it is significantly less demanding at boundary equilibria.
---
paper_title: Information Theory - The Bridge Connecting Bounded Rational Game Theory and Statistical Physics

paper_content:

A long-running difficulty with conventional game theory has been how to modify it to accommodate the bounded rationality of all real-world players. A recurring issue in statistical physics is how best to approximate joint probability distributions with decoupled (and therefore far more tractable) distributions. This paper shows that the same information theoretic mathematical structure, known as Product Distribution (PD) theory, addresses both issues. In this, PD theory not only provides a principled formulation of bounded rationality and a set of new types of mean field theory in statistical physics. It also shows that those topics are fundamentally one and the same.
---
paper_title: Learning by Trial and Error

paper_content:

A person learns by trial and error if he occasionally tries out new strategies, rejecting choices that are erroneous in the sense that they do not lead to higher payoffs. In a game, however, strategies can become erroneous due to a change of behavior by someone else. We introduce a learning rule in which behavior is conditional on whether a player experiences an error of the first or second type. This rule, called interactive trial and error learning, implements Nash equilibrium behavior in any game with generic payoffs and at least one pure Nash equilibrium.
---

Title: Uncoupled Learning Rules for Seeking Equilibria in Repeated Plays: An Overview

Section 1: Introduction
Description 1: Provide an overview of the field of uncoupled learning rules in game theory, set the scope of the paper, and introduce key concepts.

Section 2: Model of Game
Description 2: Describe the finite normal form game model used in the paper and provide relevant definitions and notations.

Section 3: Repeated Game Setup
Description 3: Explain the setup of repeated games including the notation for mixed actions, pure actions, and the history of play.

Section 4: Models of Learning Rules
Description 4: Introduce the definitions for various learning rules considered in subsequent sections, focusing on recall and memory aspects.

Section 5: Uncoupled Learning Rules
Description 5: Define uncoupled learning rules and give an overview of common examples within this category.

Section 6: Completely Uncoupled Learning Rules
Description 6: Define completely uncoupled learning rules and provide examples, highlighting the difference from general uncoupled rules.

Section 7: Notions of Convergence to Equilibria
Description 7: Introduce various notions of convergence relevant to learning rules and explain their importance in the context of game theory.

Section 8: Mixed and Correlated Equilibria: Solution Concepts
Description 8: Define mixed and correlated equilibria along with notions of internal regret, and explain their connection to learning rules.

Section 9: Regret Matching
Description 9: Describe the Regret Matching algorithm, its methodology, and implications for convergence to equilibria.

Section 10: Modified Regret Matching
Description 10: Present the modifications to the Regret Matching rule that address certain drawbacks and discuss implications for complete uncoupling.

Section 11: Mixed Equilibria: Learning Rules
Description 11: Detail learning rules for achieving mixed equilibria, including explanations of Experimental Regret Testing, ALERT, and Payoff-based ALERT.

Section 12: Pure Equilibria: Learning Rules
Description 12: Describe simple uncoupled rules and completely uncoupled rules, such as Trial-and-Error Learning, that aim to reach pure equilibria.

Section 13: Fictitious Play
Description 13: Briefly overview fictitious play and its variants, discussing their applicability and convergence properties.

Section 14: Demarcating Possible and Impossible
Description 14: Discuss the boundary between possible and impossible results for uncoupled and completely uncoupled learning rules in achieving different equilibria.

Section 15: Time Efficiency
Description 15: Analyze the complexity and time efficiency of uncoupled learning rules in reaching equilibria.

Section 16: Discussion
Description 16: Reflect on the potential pitfalls of existing learning rules, such as the type of equilibria achieved and susceptibility to delayed or inexact observations.

Section 17: Connection to Information Theory
Description 17: Explore the connection between the challenges of learning rules and information theory, discussing bounded rationality.

Section 18: Lessons Learned
Description 18: Summarize the key observations from the paper and discuss the implications for future research in uncoupled learning rules.