Potential game

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

A game ${\displaystyle 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 ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ such that ${\displaystyle \forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$,

${\displaystyle \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 ${\displaystyle i}$ switches from action ${\displaystyle a'}$ to action ${\displaystyle a''}$, the change in the potential equals the change in the utility of that player.

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

${\displaystyle \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 ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ such that ${\displaystyle \forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$,

${\displaystyle 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 ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ such that ${\displaystyle \forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$,

${\displaystyle 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 ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ such that ${\displaystyle \forall i\in N,\ \forall {a_{-i}\in A_{-i}}}$,

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

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

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.

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

${\displaystyle [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)]}$

• Congestion game
• Econophysics

• 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.