Potential game

Last updated

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]

Game theory is the study of mathematical models of strategic interaction between rational decision-makers. It has applications in all fields of social science, as well as in logic and computer science. Originally, it addressed zero-sum games, in which one person's gains result in losses for the other participants. Today, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers.

In game theory, a player's strategy is any of the options which he or she chooses in a setting where the outcome depends not only on their own actions but on the actions of others. A player's strategy will determine the action which the player will take at any stage of the game.

Lloyd Stowell Shapley 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 most important contributors to the development of game theory since the work of von Neumann and Morgenstern. With Alvin E. Roth, Shapley won the 2012 Nobel Memorial Prize in Economic Sciences "for the theory of stable allocations and the practice of market design."

Contents

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.

In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only their own strategy.

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 {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 {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 {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 {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-strategy game with externalities, individual players' payoffs are given by the function ui(si, sj) = bisi + wsisj, where si is players i's strategy, 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.

In economics, an externality is the cost or benefit that affects a party who did not choose to incur that cost or benefit. Externalities often occur when a product or service’s price equilibrium cannot reflect the true costs and benefits of that product or service. This causes the externality competitive equilibrium to not be a Pareto optimality.

This game has a potential function P(s1, s2) = b1s1 + b2s2 + ws1s2.

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

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

In game theory, battle of the sexes (BoS) is a two-player coordination game. Imagine a couple that agreed to meet this evening, but cannot recall if they will be attending the opera or a football game. The husband would prefer to go to the football game. The wife would rather go to the opera. Both would prefer to go to the same place rather than different ones. If they cannot communicate, where should they go?

In game theory, a stochastically stable equilibrium is a 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 stable if under vanishing noise the probability that the population is in the vicinity of state S does not go to zero.

 +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-strategy 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)]}$

Related Research Articles

The proof of Gödel's completeness theorem given by Kurt Gödel in his doctoral dissertation of 1929 is not easy to read today; it uses concepts and formalism that are no longer used and terminology that is often obscure. The version given below attempts to represent all the steps in the proof and all the important ideas faithfully, while restating the proof in the modern language of mathematical logic. This outline should not be considered a rigorous proof of the theorem.

In set theory, the axiom schema of replacement is a schema of axioms in Zermelo–Fraenkel set theory (ZF) that asserts that the image of any set under any definable mapping is also a set. It is necessary for the construction of certain infinite sets in ZF.

In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.

In mathematical analysis, a function of bounded variation, also known as BV function, is a real-valued function whose total variation is bounded (finite): the graph of a function having this property is well behaved in a precise sense. For a continuous function of a single variable, being of bounded variation means that the distance along the direction of the y-axis, neglecting the contribution of motion along x-axis, traveled by a point moving along the graph has a finite value. For a continuous function of several variables, the meaning of the definition is the same, except for the fact that the continuous path to be considered cannot be the whole graph of the given function, but can be every intersection of the graph itself with a hyperplane parallel to a fixed x-axis and to the y-axis.

A formula of the predicate calculus is in prenex normal form if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix.

In game theory, a cooperative game is a game with competition between groups of players ("coalitions") due to the possibility of external enforcement of cooperative behavior. Those are opposed to non-cooperative games in which there is either no possibility to forge alliances or all agreements need to be self-enforcing.

Mechanism design is a field in economics and game theory that takes an engineering approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts at the end of the game, then goes backwards, it is also called reverse game theory. It has broad applications, from economics and politics to networked-systems.

Game theory is the branch of mathematics in which games are studied: that is, models describing human behaviour. This is a glossary of some terms of the subject.

The Kripke–Platek set theory with urelements (KPU) is an axiom system for set theory with urelements, based on the traditional (urelement-free) Kripke–Platek set theory. It is considerably weaker than the (relatively) familiar system ZFU. The purpose of allowing urelements is to allow large or high-complexity objects to be included in the theory's transitive models without disrupting the usual well-ordering and recursion-theoretic properties of the constructible universe; KP is so weak that this is hard to do by traditional means.

In game theory, a Bayesian game is a game in which the players have incomplete information about the other players. For example, a player may not know the exact payoff functions of the other players, but instead have beliefs about these payoff functions. These beliefs are represented by a probability distribution over the possible payoff functions.

Independence-friendly logic, proposed by Jaakko Hintikka and Gabriel Sandu in 1989, is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form and . The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of IF sentences can characterize the same classes of structures as existential second-order logic. For example, it can express branching quantifier sentences, such as the formula which expresses infinity in the empty signature; this cannot be done in FOL. Therefore, first-order logic cannot, in general, express this pattern of dependency, in which depends only on and , and depends only on and . IF logic is more general than branching quantifiers, for example in that it can express dependencies that are not transitive, such as in the quantifier prefix .

In game theory, a symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If one can change the identities of the players without changing the payoff to the strategies, then a game is symmetric. Symmetry can come in different varieties. Ordinally symmetric games are games that are symmetric with respect to the ordinal structure of the payoffs. A game is quantitatively symmetric if and only if it is symmetric with respect to the exact payoffs. A partnership game is a symmetric game where both players receive identical payoffs for any strategy set. That is, the payoff for playing strategy a against strategy b receives the same payoff as playing strategy b against strategy a.

In game theory, a correlated equilibrium is a solution concept that is more general than the well known Nash equilibrium. It was first discussed by mathematician Robert Aumann in 1974. The idea is that each player chooses their action according to their observation of the value of the same public signal. A strategy assigns an action to every possible observation a player can make. If no player would want to deviate from the recommended strategy, the distribution is called a correlated equilibrium.

In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics.

In mathematics and theoretical physics, an invariant differential operator is a kind of mathematical map from some objects to an object of similar type. These objects are typically functions on , functions on a manifold, vector valued functions, vector fields, or, more generally, sections of a vector bundle.

In applied mathematics, discontinuous Galerkin methods form a class of numerical methods for solving differential equations. They combine features of the finite element and the finite volume framework and have been successfully applied to hyperbolic, elliptic, parabolic and mixed form problems arising from a wide range of applications. DG methods have in particular received considerable interest for problems with a dominant first-order part, e.g. in electrodynamics, fluid mechanics and plasma physics.

In the mathematical analysis, and especially in real and harmonic analysis, a Birnbaum–Orlicz space is a type of function space which generalizes the Lp spaces. Like the Lp spaces, they are Banach spaces. The spaces are named for Władysław Orlicz and Zygmunt William Birnbaum, who first defined them in 1931.

In computability theory, a semicomputable function is a partial function that can be approximated either from above or from below by a computable function.

Congestion games are a class of games in game theory first proposed by Rosenthal in 1973. In a Congestion game we define players and resources, where the payoff of each player depends on the resources it chooses and the number of players choosing the same resource. Congestion games are a special case of potential games. Rosenthal proved that any congestion game is a potential game and Monderer and Shapley (1996) proved the converse: for any potential game, there is a congestion game with the same potential function.

In game theory, an aggregative game is a game in which every player’s payoff is a function of the player’s own strategy and the aggregate of all players’ strategies. The concept was first proposed by Nobel laureate Reinhard Selten in 1970 who considered the case where the aggregate is the sum of the players' strategies.

References

1. Monderer, Dov; Shapley, Lloyd (1996). "Potential Games". Games and Economic Behavior. 14: 124–143. doi:10.1006/game.1996.0044.

Vijay Virkumar Vazirani is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine.

Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.

Timothy Avelin Roughgarden is a professor of Computer Science at Columbia University. Roughgarden received his Ph.D. at Cornell University in 2002, under the supervision of Éva Tardos.