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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 8 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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

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. 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. 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 N be the number of players, A the set of action profiles over the action sets A_{i} of each player and u_i:A \to \mathbb{R} be the payoff function for player 1\le i\le N . Given a game G=(N,A=A_{1}\times\ldots\times A_{N}, u: A \rightarrow \reals^N) , we say that G is a potential game with an exact (weighted, ordinal, generalized ordinal, best response) potential function if \Phi: A \rightarrow \reals is an exact (weighted, ordinal, generalized ordinal, best response, respectively) potential function for G . We define these notions below. \Phi is called an exact potential function if \forall i, \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 \Phi equals the change in the utility of that player. \Phi is called a weighted potential function if there is a vector w \in \reals_{++}^N such that \forall i,\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})) That is: when a player switches action, the change in \Phi equals the change in the player's utility, times a positive player-specific weight. Every exact PF is a weighted PF with w i =1 for all i. \Phi is called an ordinal potential function if \forall i,\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 That is: when a player switches action, the sign of the change in \Phi 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. \Phi is called a generalized ordinal potential function if \forall i, \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 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. \Phi is called a best-response potential function if \forall i\in N,\ \forall {a_{-i}\in A_{-i}} , \arg\max_{a_i\in A_i} u_i(a_i,a_{-i}) =\arg\max_{a_i\in A_i} \Phi(a_i,a_{-i}) .

That is: for each player i, maximizing the common potential function leads to the same outcome as maximizing his own utility. \Phi is called a pseudo-potential function if \forall i\in N,\ \forall {a_{-i}\in A_{-i}} , \arg\max_{a_i\in A_i} u_i(a_i,a_{-i}) \supseteq \arg\max_{a_i\in A_i} \Phi(a_i,a_{-i}) . That is: for each player i, maximizing the common potential function leads to some best response.

Note that while there are N 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 , where is players i's action, 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 .

If player 1 moves from −1 to +1, the payoff difference is . The change in potential is . The solution for player 2 is equivalent.

Using numerical values , , , this example transforms into a simple battle of the sexes, as shown in Figure 2. The game has two pure Nash equilibria, and . These are also the local maxima of the potential function (Figure 3).

The only stochastically stable equilibrium is , the global maximum of the potential function. A 2-player, 2-action 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)]

See also

Congestion game Econophysics A characterization of ordinal potential games.

Lecture notes of Yishay Mansour about Potential and congestion games Section 19 in: Non technical exposition by Huw Dixon of the inevitability of collusion Chapter 8, Donut world and the duopoly archipelago, Surfing Economics.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1363191768 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

7 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.