Game theory

Uses your system voice; voice and rate in settings.

Snapshot

≈ 19 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.

Game theory is the field of applied mathematics that models interactions between multiple agents as "games" of strategy between "players". It is a scientific method of describing, predicting, evaluating, and selecting choices (or "actions"), often with the view of maximising utility outcomes (or "payoffs") for one or more players.

Game theory has applications in the natural, formal and social sciences, including biology, computer science, economics, law, logic, political science, systems science, and philosophy. Subfields of game theory include algorithmic game theory, behavioral game theory, combinatorial game theory, evolutionary game theory, and quantum game theory.

In 1994, the Nobel Prize in economics was awarded to the mathematician John Nash, the philosopher John Harsanyi, and the economist Reinhard Selten for their pioneering work in game theory. Since then, game theorists who were awarded the Nobel include Thomas Schelling and Robert Aumann (2005), Leonid Hurwicz, Eric Maskin, and Roger Myerson (2007), Alvin E. Roth and Lloyd S. Shapley (2012), Jean Tirole (2014), and Paul Milgrom and Robert B. Wilson (2020).

Game theory is the field of applied mathematics that models interactions between multiple agents as "games" of strategy between "players". It is a scientific method of describing, predicting, evaluating, and selecting choices (or "actions"), often with the view of maximising utility outcomes (or "payoffs") for one or more players.

Game theory has applications in the natural, formal and social sciences, including biology, computer science, economics, law, logic, political science, systems science, and philosophy. Subfields of game theory include algorithmic game theory, behavioral game theory, combinatorial game theory, evolutionary game theory, and quantum game theory.

In 1994, the Nobel Prize in economics was awarded to the mathematician John Nash, the philosopher John Harsanyi, and the economist Reinhard Selten for their pioneering work in game theory. Since then, game theorists who were awarded the Nobel include Thomas Schelling and Robert Aumann (2005), Leonid Hurwicz, Eric Maskin, and Roger Myerson (2007), Alvin E. Roth and Lloyd S. Shapley (2012), Jean Tirole (2014), and Paul Milgrom and Robert B. Wilson (2020). u(x)=\sum_{z\in Z}x(z)u(z) \qquad \forall x\in X . Alternatively, consider \lambda\in[0,1] , such that the \lambda -mixture of x and y , denoted x\lambda y , can be defined such that x\lambda y=\lambda x+(1-\lambda)y . (Note that x\lambda y\in X .) Thus, the vNM utility function can be defined in the following way: u(x\lambda y)=\lambda u(x)+(1-\lambda)u(y) \qquad \forall ~~ x,y \in X,~ \lambda \in [0,1] For any given game, a strategy profile (or strategy combination) is a combination of strategies, such that each player gets one strategy.

For example, in a 3-player game where the action set \mathcal{A} is such that \forall i, \mathcal{A}_i = \{A,B\} , a valid strategy profile might be s = ((1,0),(1,0),(0,1)) , indicating that players 1 and 2 choose A, and player 3 chooses B. An equilibrium is a stable state in which either one outcome occurs or a set of outcomes occur with known probability. A Nash equilibrium is a particular type of equilibrium strategy profile where every player is best responding to the strategies of the others.

In such a setting, no player has an incentive to unilaterally deviate from their choice. John Forbes Nash proved that at least one such equilibrium exists in any finite non-cooperative game. \Gamma = \begin{bmatrix} (u_1(r_1,c_1),u_2(r_1,c_1)) & (u_1(r_1,c_2),u_2(r_1,c_2)) & \cdots & (u_1(r_1,c_n),u_2(r_1,c_n)) \\ (u_1(r_2,c_1),u_2(r_2,c_1)) & (u_1(r_2,c_2),u_2(r_2,c_2)) & \cdots & (u_1(r_2,c_n),u_2(r_2,c_n)) \\ \vdots & \vdots & \ddots & \vdots \\ (u_1(r_m,c_1),u_2(r_m,c_1)) & (u_1(r_m,c_2),u_2(r_m,c_2)) & \cdots & (u_1(r_m,c_n),u_2(r_m,c_n)) \end{bmatrix} where the set of actions (or action set) A available to each player are, respectively, A_1 = \{r_i \mid 1 \leq i \leq m\} and A_2 = \{c_j \mid 1 \leq j \leq n\} .

An alternative approach is to use two separate matrices: M_r for the row player and M_c for the column player, defined as follows: (M_r)_{ij} = u_1(r_i,c_j) \qquad (M_c)_{ij} = u_2(r_i,c_j) \sigma \in [0,1]_{\mathbb{R}}^ , with \sum_{i=1}^ \sigma_i=1 . Given an action set \mathcal{A} , the set of valid strategies (also known as the strategic profile or strategic set) is denoted as \Delta\mathcal{A} so that: \Delta\mathcal{A} = \left\{ \sigma \in [0,1]_{\mathbb{R}}^ \left| \sum_{i=1}^ \sigma_i = 1 \right. \right\} In order to calculate expected utility for a given action set, u_i(\sigma_1,\sigma_2) = \sum_{a_1 \in \mathcal{A}_1} \sum_{a_2 \in \mathcal{A}_2} \sigma_1(a_1)\sigma_2(a_2)u_i(a_1,a_2) In mathematical optimisation, assuming complete information, a normal-form game can also be defined as follows: Let I be a set of agents, \mathcal{I}:=\{1,2,\ldots,N\} .

Each agent i \in \mathcal{I} chooses its decision variable (i.e., its strategy or action) x_i from its local decision set. Let Ω be a decision set, such that the local decision set \Omega_i \subseteq \mathbb{R}^{n_i} , and \Omega=\Omega_1\times\cdots\times\Omega_N\subseteq\mathbb{R}^n is the overall decision space, and n=\sum_{i\in\mathcal{I}}n_i . Let x:=\begin{pmatrix} x_1\\ \vdots\\ x_N \end{pmatrix} =\operatorname{col}((x_i)_{i\in\mathcal{I}}) \in\Omega denote the stacked vector of all agent decisions.

Thus, the game, \mathcal{G}=(\mathcal{I},(J_i)_{i\in\mathcal{I}},\mathcal{X}) , is then defined such that the goal of each agent i\in\mathcal{I} is to minimize its objective function J_i(x_i,x_{-i}) , which depends on both the local variable x_i and the decision variables of the other agents, x_{-i}:=\operatorname{col}((x_j)_{j\in\mathcal{I}\setminus\{i\}}) . A finite set of players \mathcal{N} with |\mathcal{N}| = N . A tree G = (V, E, x^0) where: V is the set of vertices, E is the set of edges, and x^0 \in V is the root of the tree.

A partition (V_i)_{i \in \mathcal{N}} of the non-terminal vertices, assigning each decision node to a player. A set O of possible outcomes. A function u mapping each terminal node (leaf) of G to an element of O . A strategy for a player is a mapping from each information set to a probability distribution over the available actions at that set.

Given a game in extensive form (\mathcal{N}, G, (V_i)_{i \in \mathcal{N}}, O, u) , the set of information sets \mathcal{V}_i for player i \in \mathcal{N} is defined as a partition of V_i , such that each element of \mathcal{V}_i denotes a set of nodes at which the player cannot distinguish their exact location when choosing an action. Thus, every information set contains vertices for a single player, who has the move at that information set, and all vertices in an information set must have the same number of successors (with the same action labels).

Games of incomplete information can be reduced, within extensive form representations, to games of imperfect information by introducing "moves by nature", that is, by characterising nature as a "player 0". Information sets belonging to nature \mathcal{V}_0 are known as "singletons", with moves of nature regarded as behavior strategies, that is, strategies that map from information sets to probability distributions over feasible actions.

Formally, a characteristic function is a function v : 2^N \to \mathbb{R} from the set of all possible coalitions of players to a set of payments, and also satisfies v( \emptyset ) = 0 . The function describes how much collective payoff a set of players can gain by forming a coalition. \sigma_r^*(i) > 0 \quad \Rightarrow \quad (A\sigma_c^{\mathsf T})_i = \max_{k \in \mathcal{A}_1}(A\sigma_c^{\mathsf T})_k \qquad \forall i \in \mathcal{A}_1 where the term (A\sigma_c^{\mathsf T})_i represents the utility for the row player when playing their i^{\mathrm{th}} action. \max_{x \in \mathcal{A}_1} xMy^{\mathsf T} = \max_{i \leq m} (My^{\mathsf T})_i = \min \left\{ v \in \mathbb{R} \mid My^{\mathsf T} \leq 1v \right\} .

The min-max strategy y for the column player is the solution to the following optimisation problem (referred to as a linear program), where v is the min-max value of the game: \begin{array}{ll} \displaystyle \min_{y,v} & v \\ \text{subject to} & My^{\mathsf T} \leq 1v \\ & y \in \mathcal{A}_2 \end{array} The corresponding max-min strategy x for the row player solves the following linear program, where u is the max-min value of the game: \begin{array}{ll} \displaystyle \max_{x,u} & u \\ \text{subject to} & xM \geq 1u \\ & x \in \mathcal{A}_1 \end{array} The minimax theorem states that, for all constant-sum games, if there exist: optimal values of u and the max-min strategy x, optimal values of v and the min-max strategy y, then, u=v . In less formal terms, it holds that optimal strategies exist that minimize potential losses in every constant-sum game. Formally stated, in an N-player normal form game, a Nash equilibrium is defined as a strategy profile \tilde{s} = (\tilde{s}_1, \tilde{s}_2, \ldots, \tilde{s}_N) such that: u_i(\tilde{s}) = \max_{\tilde{s}_i \in \Delta(A_i)} u_i(\tilde{s}_i, \tilde{s}_{-i}) \quad \forall i The Nash existence theorem states that every finite N-player normal form game has at least one Nash equilibrium in mixed strategies.

At the same time, it is also known that every finite game with perfect information has a Nash equilibrium in pure strategies. Formally, using graph theory, a vNM set can be defined as follows.

Let D denote a simple directed graph, D=(X,\Delta) , where X is a set and \Delta\subseteq X\times X . D is irreflexive if and only if (x,x)\notin\Delta for any x\in X . (In contrast, it is symmetric if and only if (y,x)\in\Delta whenever (x,y)\in\Delta for any x,y\in X ). A vNM-stable set of an irreflexive simple digraph, (X,\Delta) , is a set S\subseteq X , such that the following conditions hold: internal stability, i.e., [(x,y)\notin\Delta\text{ for any }x,y\in S] , and external stability, i.e., [\text{for any }z\in X\setminus S,\text{ there exists }x\in S\text{ such that }(x,z)\in\Delta] .

Ultimatum

The ultimatum game is a game that has become a popular instrument of economic experiments. An early description is by Nobel laureate John Harsanyi in 1961. One player, the proposer, is endowed with a sum of money.

The proposer is tasked with splitting it with another player, the responder (who knows what the total sum is). Once the proposer communicates his decision, the responder may accept it or reject it. If the responder accepts, the money is split per the proposal; if the responder rejects, both players receive nothing.

Both players know in advance the consequences of the responder accepting or rejecting the offer. The game demonstrates how social acceptance, fairness, and generosity influence the players decisions.

Trust game

The Trust Game is an experiment designed to measure trust in economic decisions. It is also called "the investment game" and is designed to investigate trust and demonstrate its importance rather than "rationality" of self-interest. The game was designed by Berg Joyce, John Dickhaut and Kevin McCabe in 1995.

In the game, one player (the investor) is given a sum of money and must decide how much of it to give to another player (the trustee). The amount given is then tripled by the experimenter. The trustee then decides how much of the tripled amount to return to the investor.

If the trustee is completely self-interested, then they would return nothing. However, experiments have shown that this isn't the expected behavior of the trustee.

The outcome instead suggests that people are willing to place trust, by risking some amount of money, in the belief that there will be reciprocity. x=(x_1, \ldots, x_n) represents the overall distribution of strategies in the population, f_i(x) is the fitness, or expected utility of strategy i , and \phi(x) is the average population fitness or utility (given by the weighted average of the fitness of the n types in the population). In the social sciences, such models are also used to represent strategic adjustment by players who play a game many times within their lifetime and, consciously or unconsciously, occasionally adjust their strategies.

Frequency-dependent selection thus occurs because the expected payoff to a Hawk or a Dove depends on the frequency of Hawks and Doves in the population. A Hawk in a population of Doves does well, but a Hawk in a population of Hawks does poorly. A population of all Doves is unstable to invasion by Hawks, and similarly a population of all Hawks is unstable to invasion by Doves.

These two possible equilibria are therefore unstable, and the ESS is a mixed strategy Nash equilibrium, consisting of a mixed population of both Hawks and Doves, the proportion of which is determined by assuming that the expected payoff to a Hawk in a mixed population of Hawks and Doves is the same as the expected payoff to a Dove, such that: p=\frac{E_{H D}-E_{D D}}{\left(E_{H D}-E_{D D}\right)+\left(E_{D H}-E_{H H}\right)} , where p is the frequency of hawks.

Mean field game theory

Mean field game theory is the study of strategic decision making in very large populations of small interacting agents. This class of problems was considered in the economics literature by Boyan Jovanovic and Robert W. Rosenthal, in the engineering literature by Peter E. Caines, and by mathematicians Pierre-Louis Lions and Jean-Michel Lasry.

Differential games

Differential games such as the continuous pursuit and evasion game are continuous games where the evolution of the players' state variables is governed by differential equations. The problem of finding an optimal strategy in a differential game is closely related to the optimal control theory.

In particular, there are two types of strategies: the open-loop strategies are found using the Pontryagin maximum principle while the closed-loop strategies are found using Bellman's Dynamic Programming method. A particular case of differential games are the games with a random time horizon.

In such games, the terminal time is a random variable with a given probability distribution function. Therefore, the players maximize the mathematical expectation of the cost function. It was shown that the modified optimization problem can be reformulated as a discounted differential game over an infinite time interval.

Political science

The application of game theory to political science is focused in the overlapping areas of fair division, political economy, public choice, law and economics, war bargaining, strategic warfare, positive political theory, democratic peace theory, and social choice theory. In each of these areas, researchers have developed game-theoretic models in which the players are often voters, states, special interest groups, and politicians.

Early examples of game theory applied to political science are provided by Anthony Downs. In his 1957 book An Economic Theory of Democracy, he applies the Hotelling firm location model to the political process. In the Downsian model, political candidates commit to ideologies on a one-dimensional policy space.

Downs first shows how the political candidates will converge to the ideology preferred by the median voter if voters are fully informed, but then argues that voters choose to remain rationally ignorant which allows for candidate divergence. Game theory was applied in 1962 to the Cuban Missile Crisis during the presidency of John F. Kennedy.

Philosophy

Game theory has been put to several uses in philosophy. Responding to two papers by , used game theory to develop a philosophical account of convention. In so doing, he provided the first analysis of common knowledge and employed it in analyzing play in coordination games.

In addition, he first suggested that one can understand meaning in terms of signaling games. This later suggestion has been pursued by several philosophers since Lewis.

Following game-theoretic account of conventions, Edna Ullmann-Margalit (1977) and Bicchieri (2006) have developed theories of social norms that define them as Nash equilibria that result from transforming a mixed-motive game into a coordination game. Game theory has also challenged philosophers to think in terms of interactive epistemology: what it means for a collective to have common beliefs or knowledge, and what are the consequences of this knowledge for the social outcomes resulting from the interactions of agents.

Philosophers who have worked in this area include Bicchieri (1989, 1993), Skyrms (1990), and Stalnaker (1999). The synthesis of game theory with ethics was championed by R. B. Braithwaite. The hope was that rigorous mathematical analysis of game theory might help formalize the more imprecise philosophical discussions.

However, this expectation was only materialized to a limited extent. In ethics, some (most notably David Gauthier, Gregory Kavka, and Jean Hampton) authors have attempted to pursue Thomas Hobbes' project of deriving morality from self-interest.

Since games like the prisoner's dilemma present an apparent conflict between morality and self-interest, explaining why cooperation is required by self-interest is an important component of this project. This general strategy is a component of the general social contract view in political philosophy (for examples, see and ).

Other authors have attempted to use evolutionary game theory in order to explain the emergence of human attitudes about morality and corresponding animal behaviors. These authors look at several games including the prisoner's dilemma, stag hunt, and the Nash bargaining game as providing an explanation for the emergence of attitudes about morality (see, e.g., and ).

Several logical theories have a basis in game semantics.

Epidemiology

Since the decision to take a vaccine for a particular disease is often made by individuals, who may consider a range of factors and parameters in making this decision (such as the incidence and prevalence of the disease, perceived and real risks associated with contracting the disease, mortality rate, perceived and real risks associated with vaccination, and financial cost of vaccination), game theory has been used to model and predict vaccination uptake in a society.

History

Discussions on the mathematics of games began long before the rise of modern, mathematical game theory. Game-theoretic arguments in philosophy can be found as far back as Plato. Cardano wrote on games of chance in Liber de ludo aleae (Book on Games of Chance), written around 1564 but published posthumously in 16631.

Influenced by the work of Fermat and Pascal on the problem of points, Huygens developed the concept of expectation on reasoning about the structure of games of chance, publishing his gambling calculus in De ratiociniis in ludo aleæ (On Reasoning in Games of Chance) in 1657. In 1713, a letter attributed to Charles Waldegrave, an active Jacobite and uncle to British diplomat James Waldegrave, analyzed a game called "le her".

Waldegrave provided a minimax mixed strategy solution to a two-person version of the card game, and the problem is now known as the Waldegrave problem. In 1838, Antoine Augustin Cournot provided a model of competition in oligopolies.

Though he did not refer to it as such, he presented a solution that is the Nash equilibrium of the game in his (Researches into the Mathematical Principles of the Theory of Wealth). In 1883, Joseph Bertrand critiqued Cournot's model as unrealistic, providing an alternative model of price competition which would later be formalized by Francis Ysidro Edgeworth.

In 1913, Ernst Zermelo published (On an Application of Set Theory to the Theory of the Game of Chess), which proved that the optimal chess strategy is strictly determined. In his 1938 book and earlier notes, Émile Borel proved a minimax theorem for two-person zero-sum matrix games only when the pay-off matrix is symmetric and provided a solution to a non-trivial infinite game (known in English as Blotto game).

Borel conjectured the non-existence of mixed-strategy equilibria in finite two-person zero-sum games, a conjecture that was proved false by von Neumann.

Further reading

, (2002 edition) . A modern introduction at the graduate level. Consistent treatment of game types usually claimed by different applied fields, e.g. Markov decision processes.

Textbooks and general literature

, Description. . Suitable for undergraduate and business students. . Suitable for upper-level undergraduates. .

Suitable for advanced undergraduates. Published in Europe as . . Presents game theory in formal way suitable for graduate level.

Joseph E. Harrington (2008) Games, strategies, and decision making, Worth, . Textbook suitable for undergraduates in applied fields; numerous examples, fewer formalisms in concept presentation. Michael Maschler; Eilon Solan; Shmuel Zamir (2013), Game Theory, Cambridge University Press, .

Undergraduate textbook. . Suitable for a general audience. . A leading textbook at the advanced undergraduate level. .

Reprinted edition:

Other material

Allan Gibbard, "Manipulation of voting schemes: a general result", Econometrica, Vol. 41, No. 4 (1973), pp. 587–601. . A layman's introduction. .

Al Roth: History of Game Theory Page, David Levine: Game Theory. Papers, Lecture Notes (CC BY 2.0) McKelvey, Richard D., McLennan, Andrew M., and Turocy, Theodore L. (2007) Gambit: Software Tools for Game Theory. Benjamin Polak: Open Course on Game Theory at Yale Yu-Chi Ho: What is Mathematical Game Theory

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

References

  1. ↩Wikipedia “Game theory” revision 1378775011 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL