Potential game

In game theory, a game is said to be a potential game if the incentive of all players to change their strategy can be expressed using a single global function called the potential function. Robert W. Rosenthal created the concept of a congestion game in 1973. Dov Monderer and Lloyd Shapley ^[1] created the concept of a potential game and proved that every congestion game is a potential game.

The properties of several types of potential games have since been studied. Games can be either ordinal or cardinal potential games. In cardinal games, the difference in individual payoffs for each player from individually changing one's strategy ceteris paribus has to have the same value as the difference in values for the potential function. In ordinal games, only the signs of the differences have to be the same.

The potential function is a useful tool to analyze equilibrium properties of games, since the incentives of all players are mapped into one function, and the set of pure Nash equilibria can be found by locating the local optima of the potential function. Convergence and finite-time convergence of an iterated game towards a Nash equilibrium can also be understood by studying the potential function.

Definition

We will define some notation required for the definition. Let $N$ be the number of players, $A$ the set of action profiles over the action sets $A_{i}$ of each player and $u$ be the payoff function.

A game $G=(N,A=A_{{1}}\times \ldots \times A_{{N}},u:A\rightarrow \mathbb{R} ^{N})$ is:

an exact potential game if there is a function $\Phi :A\rightarrow \mathbb{R}$ such that $\forall {a_{{-i}}\in A_{{-i}}},\ \forall {a'_{{i}},\ a''_{{i}}\in A_{{i}}}$ ,

\Phi (a'_{{i}},a_{{-i}})-\Phi (a''_{{i}},a_{{-i}})=u_{{i}}(a'_{{i}},a_{{-i}})-u_{{i}}(a''_{{i}},a_{{-i}})

That is: when player

i

switches from action

a'

to action

a''

, the change in the potential equals the change in the utility of that player.

a weighted potential game if there is a function $\Phi :A\rightarrow \mathbb{R}$ and a vector $w\in \mathbb{R} _{{++}}^{N}$ such that $\forall {a_{{-i}}\in A_{{-i}}},\ \forall {a'_{{i}},\ a''_{{i}}\in A_{{i}}}$ ,

\Phi (a'_{{i}},a_{{-i}})-\Phi (a''_{{i}},a_{{-i}})=w_{{i}}(u_{{i}}(a'_{{i}},a_{{-i}})-u_{{i}}(a''_{{i}},a_{{-i}}))

an ordinal potential game if there is a function $\Phi :A\rightarrow \mathbb{R}$ such that $\forall {a_{{-i}}\in A_{{-i}}},\ \forall {a'_{{i}},\ a''_{{i}}\in A_{{i}}}$ ,

u_{{i}}(a'_{{i}},a_{{-i}})-u_{{i}}(a''_{{i}},a_{{-i}})>0\Leftrightarrow \Phi (a'_{{i}},a_{{-i}})-\Phi (a''_{{i}},a_{{-i}})>0

a generalized ordinal potential game if there is a function $\Phi :A\rightarrow \mathbb{R}$ such that $\forall {a_{{-i}}\in A_{{-i}}},\ \forall {a'_{{i}},\ a''_{{i}}\in A_{{i}}}$ ,

u_{{i}}(a'_{{i}},a_{{-i}})-u_{{i}}(a''_{{i}},a_{{-i}})>0\Rightarrow \Phi (a'_{{i}},a_{{-i}})-\Phi (a''_{{i}},a_{{-i}})>0

a best-response potential game if there is a function $\Phi :A\rightarrow \mathbb{R}$ such that $\forall i\in N,\ \forall {a_{{-i}}\in A_{{-i}}}$ ,

b_{i}(a_{{-i}})=\arg \max _{{a_{i}\in A_{i}}}\Phi (a_{i},a_{{-i}})

where $b_{i}(a_{{-i}})$ is the best payoff for player $i$ given $a_{{-i}}$ .

A simple example

	+1	–1
+1	+b₁+w, +b₂+w	+b₁–w, –b₂–w
–1	–b₁–w, +b₂–w	–b₁+w, –b₂+w
Fig. 1: Potential game example

In a 2-player, 2-strategy game with externalities, individual players' payoffs are given by the function u_i(s_i, s_j) = b_i s_i + w s_i s_j, where s_i is players i's strategy, s_j is the opponent's strategy, and w is a positive externality from choosing the same strategy. The strategy choices are +1 and −1, as seen in the payoff matrix in Figure 1.

This game has a potential function P(s₁, s₂) = b₁ s₁ + b₂ s₂ + w s₁ s₂.

If player 1 moves from −1 to +1, the payoff difference is Δu₁ = u₁(+1, s₂) – u₁(–1, s₂) = 2 b₁ + 2 w s₂.

The change in potential is ΔP = P(+1, s₂) – P(–1, s₂) = (b₁ + b₂ s₂ + w s₂) – (–b₁ + b₂ s₂ – w s₂) = 2 b₁ + 2 w s₂ = Δu₁.

The solution for player 2 is equivalent. Using numerical values b₁ = 2, b₂ = −1, w = 3, this example transforms into a simple battle of the sexes, as shown in Figure 2. The game has two pure Nash equilibria, (+1, +1) and (−1, −1). These are also the local maxima of the potential function (Figure 3). The only stochastically stable equilibrium is (+1, +1), the global maximum of the potential function.

	+1	–1
+1	5, 2	–1, –2
–1	–5, –4	1, 4
Fig. 2: Battle of the sexes (payoffs)

	+1	–1
+1	4	0
–1	–6	2
Fig. 3: Battle of the sexes (potentials)

A 2-player, 2-strategy game cannot be a potential game unless

[u_{{1}}(+1,-1)+u_{1}(-1,+1)]-[u_{1}(+1,+1)+u_{1}(-1,-1)]=[u_{{2}}(+1,-1)+u_{2}(-1,+1)]-[u_{2}(+1,+1)+u_{2}(-1,-1)]

Equilibrium selection

The existence of pure strategy Nash equilibrium is guaranteed in potential games, and multiple Nash equilibria may exist. Learning algorithms such as "best response" and "better response" can only guarantee that the iterative learning process can converge to one of the Nash equilibria (if multiple). Equilibrium selective learning algorithms aim to design a strategy where convergence to the best Nash equilibrium, with respect to the potential function, is guaranteed. In,^[2] the authors propose an equilibrium selective algorithm named MaxLogit, which provably converges to the best Nash equilibrium at the fastest speed in its class, using mixing rate analysis of induced Markovian chains. In a special case where every player shares the same objective function (hence the potential function), and possibly the same action set, the problem is equivalent to distributed combinatorial optimization which arises in many engineering applications. Equilibrium selective learning algorithms such as MaxLogit can be used in such combinatorial optimizations, even in a distributed fashion.

Bounded rational models

A logit equilibrium, the Gibbs measure from statistical mechanics, was shown to be the equilibrium of a finite-player potential game,^[3] where players are assumed to be bounded-rational in one of two ways. Dynamically, players follow the gradient of the potential on pure strategy space, perturbed by a random variable (motivated by the inherent behavior strategy randomness used to justify a classical mixed-strategy Nash equilibrium). Alternately, a static notion of equilibrium can be used, based on agents arbitraging information out of the system to adapt and improve, as gauged by (Shannon) information entropy. The dynamics are a variation of those that result in a quantal response equilibrium,^[4] the difference being instantaneous utility functions are used instead of expected values of utilities to accommodate markets with repeatedly interacting agents.^[4]

For a finite number of agents, both result in the same Gibbs equilibrium measure, where the potential exactly corresponds to the negative of the "energy" in physics. In the context of maximization of information entropy, "conservation of potential" is a constraint on the value of the mean potential, which enforces the degree of non-rational behavior by determining its Lagrange multiplier. This Lagrange multiplier is inverse-temperature, and is inversely proportional to the square of the coefficient of the non-rational Gaussian white noise in the drift-diffusion dynamical model (fluctuation-dissipation theorem). There are some important corollaries to these facts:

even a single player is complex in the sense that their endogenous randomness results in their motion being that for an irreversible dissipative system (convective), which converges to a steady-state Gibbs equilibrium (the concept of equilibrium is qualitatively irreversible, otherwise agents would pass right through it as though it were any other point),
any model in economics that uses, a-priori, a Gibbsian-derived model (standard or mean-field interacting particle systems, such as Curie-Weiss) from statistical mechanics, has a potential (the negative of the Hamiltonian/energy of the a-priori model) and can thus be interpreted in the context of a bounded-rational potential game, and
as a potential refines the Nash equilibriums (eliminates local maximums that aren't global maximums), statistical mechanics can refine the potential by singling out multiple global maximums via symmetry breaking (much as minimum free-energy "all up" or "all down" can be selected in a ferromagnet).

This model satisfies the (Bohr) Correspondence Principle for any finite number or infinite number of players, since the Gibbs measure yields the (refined) Nash equilibrium in the limit of zero-temperature perfect rational dynamics; i.e., this model has a limiting classical behavior.

Phase transitions never occur for a finite number of players, but can occur in the infinite-player games, with spontaneous symmetry breaking and multiple equilibriums below a critical "temperature" (degree of non-rational behavior). For high enough non-rational behavior, i.e., high "temperature", there will always be a unique equilibrium state (e.g., Dobrushin uniqueness theorem). These phase transitions give rise to the emergence of self-organized patterns (i.e., phases) which, for example, correspond to different macroscopic buying/selling patterns of agents in a particular Cournot competition.^[3]

An economic interpretation of other parameters in the Gibbs formalism, such as "entropy", "magnetization", "susceptibility", etc., as well as scaling interactions (local,^[5] power-law decay, global competition or collusion, mixtures of local/global coopetition^[6] ), are explained in ^[3] as well as in an application to a speculative and hedging model.^[7]

In this speculative and hedging model, two interdependent markets are examined, with bounded rationality assumptions. The existence of multiple equilibriums is shown to be dependent on certain parameters in the model; i.e., equilibrium(s) depend on the phase of the model - giving a different perspective to the Sonnenschein–Mantel–Debreu theorem.

This model has also been used to prove the "inevitability of collusion" result of Huw Dixon in a case for which the neoclassical version of the model does not predict collusion.,^[8]^[9] Here, a Cournot model of a Veblen good is seen to correspond to an "aligning" potential (the term "ferromagnetic" is used in statistical mechanics). The preference for collusion is due to positivity of certain correlation functions, which is shown using cluster expansion techniques for continuous spin models.

Other models assume an agent has the ability to compute their instantaneous expected payoff by conditionally averaging out other agents' distributions. This results in a mean-field-type model for which the equilibrium is obtained by finding fixed points.^[4] The Quantal response equilibrium is the simplification of the Gibbs measure to a mean field model in the case of potential games, and generalizes to games without a potential.

References

↑ Monderer, Dov; Shapley, Lloyd (1996). "Potential Games". Games and Economic Behavior. 14: 124–143. doi:10.1006/game.1996.0044.
↑ Song, Yang; Wong, Starsky H.Y.; Lee, Kwang-Won (2011). "Optimal gateway selection in multi-domain wireless networks: a potential game perspective". Proceedings of the 17th Annual International Conference on Mobile Computing and Networking. MobiCom '11. ISBN 978-1-4503-0492-4.
1 2 3 Campbell, Michael J. (2005). "A Gibbsian approach to potential game theory (draft)". arXiv:cond-mat/0502112v2.
1 2 3 Anderson, Simon; Goeree, Jacob; Holt, Charles (2004). "Noisy Directional Learning and the Logit Equilibrium" (PDF). Scandinavian Journal of Economics. 106: 581–602. doi:10.1111/j.0347-0520.2004.00378.x.
↑ Pinkse, Joris; Slade, Margaret E.; Brett, Craig (2002). "Spatial Price Competition: A Semiparametric Approach" (PDF). Econometrica. 70 (3): 1111–1153. doi:10.1111/1468-0262.00320.
↑ Carfi, David (2015). A model for coopetitive games.
↑ Carfi, David; Campbell, Michael J. (2015). "Bounded Rational Speculative and Hedging Interaction Model in Oil and U.S. Dollar Markets". Journal of Mathematical Economics and Finance. ASERS. 1 (1): 4–23. doi:10.14505/jmef.01.
↑ Dixon, Huw (2000). "keeping up with the Joneses: competition and the evolution of collusion". Journal of Economic Behaviour and Organization. 43: 223–238.
↑ Campbell, Michael J. (2016). "Inevitability of Collusion in a Coopetitive Bounded Rational Cournot Model with Increasing Demand". Journal of Mathematical Economics and Finance. ASERS. 2 (1): 7–19.

External links

Lecture notes of Yishay Mansour about Potential and congestion games
Section 19 in: Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
Non technical exposition by Huw Dixon of the inevitability of collusion Chapter 8, Donut world and the duopoly archipelago,Surfing Economics.

Topics in game theory

Definitions	Normal-form game Extensive-form game Escalation of commitment Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined game Potential game

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem Rendezvous problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey

See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons Tyranny of small decisions

Microeconomics

Major topics	Aggregation Bilateral monopoly Budget Consumer Convexity and non-convexity Cost Cost–benefit analysis Deadweight loss Distribution Duopoly Economies of scale Economies of scope Elasticity Equilibria Exchange Expected utility Externality Firms General equilibrium Household Income–consumption curve Information Indifference curve Intertemporal choice Marginal cost Market failure Market structure Monopoly Monopsony Oligopoly Preferences Production Profit Public goods Returns to scale Risk aversion Scarcity Shortage Social choice Sunk costs Supply & demand Surplus Uncertainty Utility Welfare

Subfields	Behavioral Business Computational Statistical decision theory Econometrics Experimental Game theory Industrial organization Labor Managerial Mathematical economics Microfoundations of macroeconomics Operations research Optimization

This article is issued from Wikipedia - version of the 12/5/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.