Potential game
   HOME

TheInfoList



OR:

In
game theory Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
, a game is said to be a potential game if the incentive of all players to change their
strategy Strategy (from Greek στρατηγία ''stratēgia'', "art of troop leader; office of general, command, generalship") is a general plan to achieve one or more long-term or overall goals under conditions of uncertainty. In the sense of the "art ...
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 Lloyd Stowell Shapley (; June 2, 1923 – March 12, 2016) was an American mathematician and Nobel Prize-winning economist. He contributed to the fields of mathematical economics and especially game theory. Shapley is generally considered one of ...
. 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 In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
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 In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game (called a stage game). The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a p ...
with state so that every round played has a direct consequence on game's state in the next round. Marden, J., (2012) State based potential games http://ecee.colorado.edu/marden/files/state-based-games.pdf 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 N be the number of players, A the set of action profiles over the action sets A_ of each player and u be the payoff function. A game G=(N,A=A_\times\ldots\times A_, u: A \rightarrow \reals^N) is: * an exact potential game if there is a function \Phi: A \rightarrow \reals such that \forall i, \forall ,\ \forall , :: \Phi(a'_,a_)-\Phi(a''_,a_) = u_(a'_,a_)-u_(a''_,a_) ::That is: when player i switches from action a' to action a'', the change in the potential equals the change in the utility of that player. * a weighted potential game if there is a function \Phi: A \rightarrow \reals and a vector w \in \reals_^N such that \forall i,\forall ,\ \forall , :: \Phi(a'_,a_)-\Phi(a''_,a_) = w_(u_(a'_,a_)-u_(a''_,a_)) * an ordinal potential game if there is a function \Phi: A \rightarrow \reals such that \forall i,\forall ,\ \forall , :: u_(a'_,a_)-u_(a''_,a_)>0 \Leftrightarrow \Phi(a'_,a_)-\Phi(a''_,a_)>0 * a generalized ordinal potential game if there is a function \Phi: A \rightarrow \reals such that \forall i, \forall ,\ \forall , :: u_(a'_,a_)-u_(a''_,a_)>0 \Rightarrow \Phi(a'_,a_)-\Phi(a''_,a_) >0 *a best-response potential game if there is a function \Phi: A \rightarrow \reals such that \forall i\in N,\ \forall , ::b_i(a_)=\arg\max_ \Phi(a_i,a_) where b_i(a_) is the best action for player i given a_.


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 In economics, an externality or external cost is an indirect cost or benefit to an uninvolved third party that arises as an effect of another party's (or parties') activity. Externalities can be considered as unpriced goods involved in either co ...
from choosing the same action. The action choices are +1 and −1, as seen in the
payoff matrix In game theory, normal form is a description of a ''game''. Unlike extensive form, normal-form representations are not graphical ''per se'', but rather represent the game by way of a matrix. While this approach can be of greater use in identifying ...
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 In game theory, a stochastically stable equilibrium is a solution concept, refinement of the evolutionarily stable state in evolutionary game theory, proposed by Dean Foster and Peyton Young. An evolutionary stable state S is also stochastically s ...
is , the global maximum of the potential function. A 2-player, 2-action game cannot be ''a'' potential game unless : _(+1,-1)+u_1(-1,+1) _1(+1,+1)+u_1(-1,-1)= _(+1,-1)+u_2(-1,+1) _2(+1,+1)+u_2(-1,-1)


See also

*
Congestion game Congestion games are a class of games in game theory first proposed by American economist Robert W. Rosenthal in 1973. In a congestion game the payoff of each player depends on the resources it chooses and the number of players choosing the same re ...
*
Econophysics Econophysics is a Heterodox economics, heterodox interdisciplinary research field, applying theories and methods originally developed by physicists in order to solve problems in economics, usually those including uncertainty or stochastic processes ...


References


External links

* Lecture notes of Yishay Mansour abou
Potential and congestion games
* Section 19 in: * Non technical exposition by Huw Dixon of the inevitability of collusio
Chapter 8, Donut world and the duopoly archipelago
{{microeconomics Game theory game classes