Potential game

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|+b1+w, +b2+w | UR = nowrap|+b1–w, –b2–w
1D = –1 | DL = nowrap|–b1–w, +b2–w | DR = nowrap|–b1+w, –b2+w In a 2-player, 2-strategy game with externalities, individual players' payoffs are given by the function nowrap|ui(si, sj) = nowrap|bi si + w si sj, where si is players i's strategy, nowrap|sj 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(s1, s2) = nowrap|b1 s1 + b2 s2 + w s1 s2.

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

The change in potential is ΔP = nowrap|P(+1, s2) – P(–1, s2) = nowrap|(b1 + b2 s2 + w s2) – (–b1 + b2 s2 – w s2) = nowrap|2 b1 + 2 w s2 = Δ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.

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]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Game theory — is a branch of applied mathematics that is used in the social sciences (most notably economics), biology, engineering, political science, computer science (mainly for artificial intelligence), and philosophy. Game theory attempts to… …   Wikipedia

  • Game mechanics — are constructs of rules intended to produce an enjoyable game or gameplay. All games use mechanics; however, theories and styles differ as to their ultimate importance to the game. In general, the process and study of game design are efforts to… …   Wikipedia

  • Game artificial intelligence — refers to techniques used in computer and video games to produce the illusion of intelligence in the behavior of non player characters (NPCs). The techniques used typically draw upon existing methods from the academic field of artificial… …   Wikipedia

  • Game backup device — is a device for storing or backuping ROM information to a computer file format or ROM image. This article discusses ROM Dumper for video games. It s also called game copier or ROM dumper. Video game companies considered these devices as a tool… …   Wikipedia

  • Game engine — A game engine is a system designed for the creation and development of video games. There are many game engines that are designed to work on video game consoles and personal computers. The core functionality typically provided by a game engine… …   Wikipedia

  • Potential Breakup Song — Infobox Single Name = Potential Breakup Song Artist = Aly AJ from Album = Insomniatic B side = Careful With Words (UK) Released = flagicon|Canada May 2007 flagicon|US June 26 2007 [ [http://fmqb.com/Article.asp?id=69239#2007 6/26 Mainstream] .… …   Wikipedia

  • Potential superpowers — The present day governments that have been claimed to become (or to remain) superpowers during the 21st century. The list of governments.   United States of America …   Wikipedia

  • Game Boy Player — Infobox CVG system title = Game Boy Player logo = caption=Game Boy Player usage sample: Controller and GBA are equivalent, GBA SP is recognized as another player manufacturer = Nintendo type = Accessory generation = Sixth generation lifespan = JP …   Wikipedia

  • Game design — This article is about video game design, and does not deal with the design of other forms of game, such as board games and card games …   Wikipedia

  • Game of the Century (college football) — The phrase Game of the Century is a superlative that has been applied to several college football contests played in the 20th century, the first full century of college football in the United States. It is a subjective term applied by… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”