Potential game

A game in game theory is considered a potential game if the incentive of all players to change their strategy can be expressed in one global function, the potential function. The concept was proposed by Dov Monderer and Lloyd Shapley. 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 simply locating the local optima of the potential function.

Definition

Formally, let N be the number of players, A the set of action profiles over the action sets $A\_\{i\}$ of each player and u the payoff function. Then, a game $G=(N,A=A\_\{1\}\; imes...\; imes\; A\_\{N\},\; u:\; A\; ightarrow\; eals^N)$ is a (cardinal) potential game if there is an exact potential function $Phi:\; A\; ightarrow\; eals$ such that:$forall\_\{ain\; A\}\; forall\_\{a\_\{i\},b\_\{i\}in\; A\_\{i\; Phi(b\_\{i\},a\_\{-i\})-Phi(a\_\{i\},a\_\{-i\})\; =\; u\_\{i\}(b\_\{i\},a\_\{-i\})-u\_\{i\}(a\_\{i\},a\_\{-i\})$

A game $G=(N,A=A\_\{1\}\; imes...\; imes\; A\_\{N\},\; u:\; A\; ightarrow\; eals^N)$ is an general (ordinal) potential game if there is an ordinal potential function $Phi:\; A\; ightarrow\; eals$ such that:$forall\_\{ain\; A\}\; forall\_\{a\_\{i\},b\_\{i\}in\; A\_\{i\; sgn(Phi(b\_\{i\},a\_\{-i\})-Phi(a\_\{i\},a\_\{-i\}))\; =\; sgn(u\_\{i\}(b\_\{i\},a\_\{-i\})-u\_\{i\}(a\_\{i\},a\_\{-i\}))$where sgn denotes the Sign function.

A simple example

Payoff matrix | Name = Fig. 1: Potential game example
2L = +1 | 2R = –1
1U = +1 | UL = nowrap|+b₁+w, +b₂+w | UR = nowrap|+b₁–w, –b₂–w
1D = –1 | DL = nowrap|–b₁–w, +b₂–w | DR = nowrap|–b₁+w, –b₂+w In a 2-player, 2-strategy game with externalities, individual players' payoffs are given by the function nowrap|u_i(s_i, s_j) = nowrap|b_i s_i + w s_i s_j, where s_i is players i's strategy, nowrap|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 nowrap|P(s₁, s₂) = nowrap|b₁ s₁ + b₂ s₂ + w s₁ s₂.

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

The change in potential is ΔP = nowrap|P(+1, s₂) – P(–1, s₂) = nowrap|(b₁ + b₂ s₂ + w s₂) – (–b₁ + b₂ s₂ – w s₂) = nowrap|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.

References

* Dov Monderer and Lloyd S. Shapley: "Potential Games", "Games and Economic Behavior" 14, pp. 124–143 (1996).
* Emile Aarts and Jan Korst: "Simulated Annealing and Boltzmann Machines", John Wiley & Sons (1989) ISBN 0471921467

External links

* Lecture notes of Yishay Mansour about [http://www.math.tau.ac.il/~mansour/course_games/scribe/lecture6.pdf Potential and congestion games]