# 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. The concept originated in a 1996 paper by Dov Monderer and Lloyd Shapley.[1]

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, 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 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 games with state so that every round played has a direct consequence on game's state in the next round.[2] 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

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 i,\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 i,\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 i,\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 i,\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}}$.

## A simple example

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

This game has a potential function P(a1, a2) = b1 a1 + b2 a2 + w a1 a2.

If player 1 moves from −1 to +1, the payoff difference is Δu1 = u1(+1, a2) – u1(–1, a2) = 2 b1 + 2 w a2.

The change in potential is ΔP = P(+1, a2) – P(–1, a2) = (b1 + b2 a2 + w a2) – (–b1 + b2 a2w a2) = 2 b1 + 2 w a2 = Δu1.

The solution for player 2 is equivalent. Using numerical values b1 = 2, b2 = −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 +b1+w, +b2+w +b1–w, –b2–w –1 –b1–w, +b2–w –b1+w, –b2+w Fig. 1: Potential game example
 +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-action 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)]}$