View source for Potential game

{{Short description|Game class in game theory}}
In [[game theory]], a game is said to be a '''potential game''' if the incentive of all players to change their [[strategy (game theory)|strategy]] can be expressed using a single global function called the '''potential function'''. The concept originated in a 1996 paper by Dov Monderer and [[Lloyd Shapley]].<ref name="MS">
{{cite journal
 | last1 = Monderer | first1 = Dov
 | last2 = Shapley | first2 = Lloyd
 | author2-link = Lloyd Shapley
 | title = Potential Games
 | journal = Games and Economic Behavior
 | volume = 14
 | pages = 124–143
 | date = 1996
 | doi=10.1006/game.1996.0044}}
</ref>

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 [[Payoff matrix|payoffs]] for each player from individually changing one's strategy, other things equal, 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 equilibrium|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.

Potential games can be studied as [[repeated game]]s with state so that every round played has a direct consequence on game's state in the next round.<ref>Marden, J., (2012) State based potential games http://ecee.colorado.edu/marden/files/state-based-games.pdf</ref> This approach has applications in distributed control such as distributed resource allocation, where players without a central correlation mechanism can cooperate to achieve a globally optimal resource distribution.

==Definition==
Let <math>N</math> be the number of players, <math>A</math> the set of action profiles over the action sets <math>A_{i}</math> of each player and <math>u_i:A \to \mathbb{R}</math> be the payoff function for player <math>1\le i\le N</math>.
 
Given a game <math>G=(N,A=A_{1}\times\ldots\times A_{N}, u: A \rightarrow \reals^N) </math>, we say that <math>G</math> is a '''potential game''' with an exact (weighted, ordinal, generalized ordinal, best response) '''potential function''' if <math>\Phi: A \rightarrow \reals</math> is an exact (weighted, ordinal, generalized ordinal, best response, respectively) potential function for <math>G</math>. Here, <math>\Phi</math> is called

* an '''exact potential function''' if   <math> \forall i, \forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}</math>,
::<math> \Phi(a'_{i},a_{-i})-\Phi(a''_{i},a_{-i}) = u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})</math>

::That is: when player <math>i</math> switches from action <math>a'</math> to action <math>a''</math>,  the change in the potential <math>\Phi</math> equals the change in the utility of that player.

* a '''weighted potential function''' if there is a vector <math>w \in \reals_{++}^N</math> such that <math> \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}</math>,
::<math> \Phi(a'_{i},a_{-i})-\Phi(a''_{i},a_{-i}) = w_{i}(u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i}))</math> That is: when a player switches action,  the change in <math>\Phi</math> equals the change in the player's utility, times a positive player-specific weight. Every exact PF is a weighted PF with ''w<sub>i</sub>''=1 for all ''i''.

* an '''ordinal potential function''' if    <math> \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}</math>,
::<math> 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</math> That is: when a player switches action,  the ''sign'' of the change in <math>\Phi</math> equals the ''sign'' of the change in the player's utility, whereas the magnitude of change may differ. Every weighted PF is an ordinal PF.

* a '''generalized ordinal potential function''' if <math>\forall i, \forall {a_{-i}\in A_{-i}},\  \forall {a'_{i},\ a''_{i}\in A_{i}}</math>,
::<math> 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 </math> That is: when a player switches action, if the player's utility increases, then the potential increases (but the opposite is not necessarily true). Every ordinal PF is a generalized-ordinal PF.

*a '''best-response potential function''' if  <math>\forall i\in N,\ \forall {a_{-i}\in A_{-i}}</math>,
::<math>b_i(a_{-i})=\arg\max_{a_i\in A_i} \Phi(a_i,a_{-i})</math> where <math>b_i(a_{-i})</math> is the best action for player <math>i</math> given <math>a_{-i}</math>.

Note that while there are <math>N</math> utility functions, one for each player, there is only one potential function. Thus, through the lens of potential functions, the players become interchangeable (in the sense of one of the definitions above). Because of this ''symmetry'' of the game, decentralized algorithms based on the shared potential function often lead to convergence (in some of sense) to a Nash equilibria.

==A simple example==

In ''a'' 2-player, 2-action game with externalities, individual players' payoffs are given by the function {{math|''u''<sub>''i''</sub>(''a''<sub>''i''</sub>, ''a''<sub>''j''</sub>) {{=}} ''b''<sub>''i''</sub> ''a''<sub>''i''</sub> + ''w'' ''a''<sub>''i''</sub> ''a''<sub>''j''</sub>}}, where {{math|''a''<sub>''i''</sub>}} is players i's action, {{math|''a''<sub>''j''</sub>}} is the opponent's action, and ''w'' is ''a'' positive [[externality]] from choosing the same action. The action choices are +1 and &minus;1, as seen in the [[payoff matrix]] in Figure 1.

This game has ''a'' potential function {{math|P(''a''<sub>1</sub>, ''a''<sub>2</sub>) {{=}} ''b''<sub>1</sub> ''a''<sub>1</sub> + ''b''<sub>2</sub> ''a''<sub>2</sub> + ''w'' ''a''<sub>1</sub> ''a''<sub>2</sub>}}.

If player 1 moves from &minus;1 to +1, the payoff difference is {{math|1=Δ''u''<sub>1</sub> = ''u''<sub>1</sub>(+1, ''a''<sub>2</sub>) – ''u''<sub>1</sub>(–1, ''a''<sub>2</sub>) {{=}} 2 ''b''<sub>1</sub> + 2 ''w'' ''a''<sub>2</sub>}}.

The change in potential is {{math|1=ΔP = P(+1, ''a''<sub>2</sub>) – P(–1, ''a''<sub>2</sub>) {{=}} (''b''<sub>1</sub> + ''b''<sub>2</sub> ''a''<sub>2</sub> + ''w'' ''a''<sub>2</sub>) – (–''b''<sub>1</sub> + ''b''<sub>2</sub> ''a''<sub>2</sub> – ''w'' ''a''<sub>2</sub>) {{=}} 2 ''b''<sub>1</sub> + 2 ''w'' ''a''<sub>2</sub> = Δ''u''<sub>1</sub>}}.

The solution for player 2 is equivalent. Using numerical values {{math|1=''b''<sub>1</sub>&nbsp;=&nbsp;2}}, {{math|1=''b''<sub>2</sub>&nbsp;=&nbsp;&minus;1}}, {{math|1=''w''&nbsp;=&nbsp;3}}, this example transforms into ''a'' simple [[battle of the sexes (game theory)|battle of the sexes]], as shown in Figure 2. The game has two pure Nash equilibria, {{math|1=(+1,&nbsp;+1)}} and {{math|1=(&minus;1,&nbsp;&minus;1)}}. These are also the local maxima of the potential function (Figure 3). The only [[stochastically stable equilibrium]] is {{math|1=(+1,&nbsp;+1)}}, the global maximum of the potential function.

{| style="margin-left: auto; margin-right: auto; border: none;"
|- style="vertical-align:top;"
| width=40% |
{{Payoff matrix | Name = Fig. 1: Potential game example
        | 2L = +1                                                   | 2R = –1                                                   |
1U = +1 | UL = <small>{{math|+''b''<sub>1</sub>+''w'', +''b''<sub>2</sub>+''w''}}</small> | UR = <small>{{math|+''b''<sub>1</sub>–''w'', –''b''<sub>2</sub>–''w''}}</small> |
1D = –1 | DL = <small>{{math|–''b''<sub>1</sub>–''w'', +''b''<sub>2</sub>–''w''}}</small> | DR = <small>{{math|–''b''<sub>1</sub>+''w'', –''b''<sub>2</sub>+''w''}}</small> }}
| width=30% |
{{Payoff matrix | Name = Fig. 2: Battle of the sexes<br/>(payoffs)
                | 2L = +1         | 2R = –1         |
1U = +1         | UL = 5, 2       | UR = –1, –2     |
1D = –1         | DL = –5, –4     | DR = 1, 4       }}
| width=30% |
{{Payoff matrix | Name = Fig. 3: Battle of the sexes<br/>(potentials)
                | 2L = +1         | 2R = –1         |
1U = +1         | UL = '''4'''    | UR = '''0'''    |
1D = –1         | DL = '''–6'''   | DR = '''2'''    }}
|}

A 2-player, 2-action game cannot be ''a'' potential game unless
:<math>
[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)] 
</math>

== Potential games and congestion games ==
Exact potential games are equivalent to [[congestion game]]s: Rosenthal<ref name=":1">{{citation |last=Rosenthal |first=Robert W. |title=A class of games possessing pure-strategy Nash equilibria |journal=International Journal of Game Theory |volume=2 |pages=65–67 |year=1973 |doi=10.1007/BF01737559 |mr=0319584|s2cid=121904640 }}.</ref> proved that every [[congestion game]] has an exact potential; Monderer and Shapley<ref name="MS" /> proved the opposite direction: every game with an exact potential function is a [[congestion game]].

== Potential games and improvement paths ==
An '''improvement path''' (also called '''Nash dynamics''') is a sequence of strategy-vectors, in which each vector is attained from the previous vector by a single player switching his strategy to a strategy that strictly increases his utility. If a game has a generalized-ordinal-potential function <math>\Phi</math>, then <math>\Phi</math> is strictly increasing in every improvement path, so every improvement path is acyclic. If, in addition, the game has finitely many strategies, then every improvement path must be finite. This property is called the '''finite  improvement property (FIP)'''. We have just proved that every finite generalized-ordinal-potential game has the FIP. The opposite is also true: every finite game has the FIP has a generalized-ordinal-potential function.<ref name=":2">{{Cite journal |last=Milchtaich |first=Igal |date=1996-03-01 |title=Congestion Games with Player-Specific Payoff Functions |url=https://www.sciencedirect.com/science/article/pii/S0899825696900275 |journal=Games and Economic Behavior |language=en |volume=13 |issue=1 |pages=111–124 |doi=10.1006/game.1996.0027 |issn=0899-8256}}</ref>{{Clarify|reason=The text says "Indeed, for a game that possesses the FIP, the integer-valued function that assigns to a strategy-tuple s the number of strategy-tuples which are the initial point of an improvement path with the terminal point s is easily seen to be a generalized ordinal potential." I did not understand why this function is a generalized-ordinal-potential.|date=June 2023}} The terminal state in every finite improvement path is a Nash equilibrium, so FIP implies the existence of a pure-strategy Nash equilibrium. Moreover, it implies that a Nash equilibrium can be computed by a distributed process, in which each agent only has to improve his own strategy.

A '''best-response path''' is a special case of an improvement path, in which each vector is attained from the previous vector by a single player switching his strategy to a best-response strategy. The property that every best-response path is finite is called the '''finite best-response property (FBRP)'''. FBRP is weaker than FIP, and it still implies the existence of a pure-strategy Nash equilibrium. It also implies that a Nash equilibrium can be computed by a distributed process, but the computational burden on the agents is higher than with FIP, since they have to compute a best-response.

An even weaker property is '''weak-acyclicity (WA)'''.<ref>{{Cite journal |last=Young |first=H. Peyton |date=1993 |title=The Evolution of Conventions |url=https://www.jstor.org/stable/2951778 |journal=Econometrica |volume=61 |issue=1 |pages=57–84 |doi=10.2307/2951778 |jstor=2951778 |issn=0012-9682}}</ref> It means that, for any initial strategy-vector, ''there exists'' a finite best-response path starting at that vector. Weak-acyclicity is not sufficient for existence of a potential function (since some improvement-paths may be cyclic), but it is sufficient for the existence of pure-strategy Nash equilibrium. It implies that a Nash equilibrium can be computed [[Almost surely|almost-surely]] by a stochastic distributed process, in which at each point, a player is chosen at random, and this player chooses a best-strategy at random.<ref name=":2" />

==See also==
* [[Congestion game]]
* [[Econophysics#Basic tools|Econophysics]]
* A characterization of ordinal potential games.<ref>{{Cite journal |last1=Voorneveld |first1=Mark |last2=Norde |first2=Henk |date=1997-05-01 |title=A Characterization of Ordinal Potential Games |url=https://www.sciencedirect.com/science/article/pii/S0899825697905546 |journal=Games and Economic Behavior |language=en |volume=19 |issue=2 |pages=235–242 |doi=10.1006/game.1997.0554 |s2cid=122795041 |issn=0899-8256}}</ref>

==References==
{{Reflist}}

==External links==
* Lecture notes of Yishay Mansour about [http://www.math.tau.ac.il/~mansour/course_games/scribe/lecture6.pdf Potential and congestion games]
* Section 19 in: {{Cite Algorithmic Game Theory 2007}}
* Non technical exposition by Huw Dixon of the inevitability of collusion [http://www.huwdixon.org/SurfingEconomics/chapter8.pdf Chapter 8, Donut world and the duopoly archipelago], [http://www.huwdixon.org/SurfingEconomics/index.html Surfing Economics].

{{game theory}}
{{microeconomics}}

[[Category:Game theory game classes]]