Game theory

Representation of games

Non-cooperative games can be broadly represented in two forms. Generally, normal form is used to represent non-cooperative simultaneous games, and extensive form is used to represent non-cooperative sequential ones. Alternative representations also exist, for example, characteristic function form is used to represent cooperative games.

Every extensive-form game has an equivalent normal-form game, however, the transformation to normal form may result in an exponential blowup in the size of the representation, making it computationally impractical.

Normal form

The normal form (or strategic form) game is usually represented by a matrix which shows the players, strategies, and payoffs. In linear algebra notation, a two-player normal-form game can be mapped by a matrix. A general matrix mapping rows (actions of the first player) and columns (actions of the second player) to pairs of payoff values can be represented as follows:

$${\displaystyle \mathrm{\Gamma }=\left[\begin{array}{cccc}(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))\\ ⋮& ⋮& \ddots & ⋮\\ (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{array}\right]}$$

where the set of actions (or action set) ${\displaystyle A}$ available to each player are, respectively, ${\displaystyle A_1=\{r_i\mid 1\le i\le m\}}$ and ${\displaystyle A_2=\{c_j\mid 1\le j\le n\}}$.

An alternative approach is to use two separate matrices: ${\displaystyle M_r}$ for the row player and ${\displaystyle M_c}$ for the column player, defined as follows:

$${\displaystyle (M_r{)}_{ij}=u_1(r_i,c_j)(M_c{)}_{ij}=u_2(r_i,c_j)}$$

Prisoner's dilemma

The most popular example of a normal-form game is Prisoner's dilemma. In the dilemma, there are two players who are both accomplices to a crime. Both have been arrested and imprisoned, and they cannot communicate with each other, nor do they know what the other prisoner is doing. The police do not have sufficient evidence for a conviction, but the prisoners do not know this. Instead, they tell each prisoner that, if they confess to their crimes, they will get a lighter sentence. Each player may thus either inform on themselves and the other player, or they may remain silent. If neither confess, neither will go to jail; if both confess, they will get an ordinary sentence; however, if one confesses and the other does not, the confessor will get a short sentence while the denier will get a long one.

Despite the best possible outcome being the situation in which both parties refuse to confess, the dominant strategy for each individual player, no matter what a suspect believes his partner is going to do, is in fact to betray the other, which aligns with the sure-thing principle. The utility of this illustration is that it demonstrates the conflict between the pursuit of individual, selfish goals and the common good of both parties, representing an issue present in a variety of public goods problems.

Formal definition

Formally, an ${\displaystyle N}$-player normal form game comprises:

• A finite set of ${\displaystyle N}$ players.
• An action set for the players: ${\displaystyle \{A_1,A_2,\dots ,A_N\}}$.
• A set of payoff functions for the player that maps action sets to ${\displaystyle \mathbb{R}}$: ${\displaystyle u_i:A_1\times A_2\times \cdots \times A_N\to \mathbb{R}}$.

A strategy ${\displaystyle \sigma }$ for a player with action set ${\displaystyle A}$ is a probability distribution over the elements of ${\displaystyle A}$, such that:

${\displaystyle \sigma \in [0,1{]}_{\mathbb{R}}^{|A|}}$, with ${\displaystyle \sum _{i=1}^{|A|}{\sigma }_i=1}$.

Given an action set ${\displaystyle \mathcal{A}}$, the set of valid strategies (also known as the strategic profile or strategic set) is denoted as ${\displaystyle \mathrm{\Delta }\mathcal{A}}$ so that:

$${\displaystyle \mathrm{\Delta }\mathcal{A}=\left\{\sigma \in [0,1{]}_{\mathbb{R}}^{|\mathcal{A}|}|\sum _{i=1}^{|\mathcal{A}|}{\sigma }_i=1\right\}}$$

In order to calculate expected utility for a given action set,

$${\displaystyle 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, ${\displaystyle \mathcal{I}:=\{1,2,\dots ,N\}}$.
• Each agent ${\displaystyle i\in \mathcal{I}}$ chooses its decision variable (i.e., its strategy or action) ${\displaystyle x_i}$ from its local decision set.
• Let Ω be a decision set, such that the local decision set ${\displaystyle {\mathrm{\Omega }}_i\subseteq {\mathbb{R}}^{n_i}}$, and ${\displaystyle \mathrm{\Omega }={\mathrm{\Omega }}_1\times \cdots \times {\mathrm{\Omega }}_N\subseteq {\mathbb{R}}^n}$ is the overall decision space, and ${\displaystyle n=\sum _{i\in \mathcal{I}}{n}_i}$.
• Let ${\displaystyle x:=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_N\end{array}\right)=\mathrm{col}((x_i{)}_{i\in \mathcal{I}})\in \mathrm{\Omega }}$ denote the stacked vector of all agent decisions.

Thus, the game, ${\displaystyle \mathcal{G}=(\mathcal{I},(J_i{)}_{i\in \mathcal{I}},\mathcal{X})}$, is then defined such that the goal of each agent ${\displaystyle i\in \mathcal{I}}$ is to minimize its objective function ${\displaystyle J_i(x_i,x_{-i})}$, which depends on both the local variable ${\displaystyle x_i}$ and the decision variables of the other agents, ${\displaystyle x_{-i}:=\mathrm{col}((x_j{)}_{j\in \mathcal{I}\setminus \{i\}})}$.

Extensive form

Extensive form games can be visualized using game trees. Within a tree, each vertex (or node) represents a point of choice for a player; the lines out of the vertex represent a possible action for that player; information sets are represented by dashed lines; and the payoffs are specified at the bottom of the tree, that is, being represented as the terminal nodes. The extensive form can be viewed as a multi-player generalization of a decision tree.

Solving an extensive form game (that is, finding its Nash equilibrium) involves the use of backwards induction, which involves the analysis of the tree from the end nodes to the root, removing or "pruning" dominated strategies at each information set.

Battle of the sexes

The "battle of the sexes" game involves two players of different sexes, arbitrarily chosen, each with a different set of preferences.

Formal definition

Formally, an ${\displaystyle N}$-player extensive form game with complete information is characterised by:

• A finite set of players ${\displaystyle \mathcal{N}}$ with ${\displaystyle |\mathcal{N}|=N}$.
• A tree ${\displaystyle G=(V,E,x^0)}$ where:
  • ${\displaystyle V}$ is the set of vertices,
  • ${\displaystyle E}$ is the set of edges, and
  • ${\displaystyle x^0\in V}$ is the root of the tree.
• A partition ${\displaystyle (V_i{)}_{i\in \mathcal{N}}}$ of the non-terminal vertices, assigning each decision node to a player.
• A set ${\displaystyle O}$ of possible outcomes.
• A function ${\displaystyle u}$ mapping each terminal node (leaf) of ${\displaystyle G}$ to an element of ${\displaystyle 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 ${\displaystyle (\mathcal{N},G,(V_i{)}_{i\in \mathcal{N}},O,u)}$, the set of information sets ${\displaystyle {\mathcal{V}}_i}$ for player ${\displaystyle i\in \mathcal{N}}$ is defined as a partition of ${\displaystyle V_i}$, such that each element of ${\displaystyle {\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 ${\displaystyle {\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.

Characteristic function form

In cooperative game theory the characteristic function lists the payoff of each coalition. The origin of this formulation is in John von Neumann and Oskar Morgenstern's book.

Formally, a characteristic function is a function ${\displaystyle v:2^N\to \mathbb{R}}$ from the set of all possible coalitions of players to a set of payments, and also satisfies ${\displaystyle v(\mathrm{\varnothing })=0}$. The function describes how much collective payoff a set of players can gain by forming a coalition.

Alternative game representations

Alternative game representation forms are used for some subclasses of games or adjusted to the needs of interdisciplinary research. In addition to classical game representations, some of the alternative representations also encode time related aspects.

Equilibria

Best response

In an N-player normal form game, a strategy ${\displaystyle s^{\ast }}$ for player i is a best response to some incomplete strategy profile ${\displaystyle s_{-i}}$, representing the strategies chosen by all players except player i, if and only if:

${\displaystyle u_i(s^{\ast },s_{-i})\ge u_i(s,s_{-i})\mathrm{\forall }s\in \mathrm{\Delta }({\mathcal{A}}_i).}$

That is, ${\displaystyle s^{\ast }}$ gives player i the highest possible payoff, given the strategies chosen by the other players.

The action set that a strategy σ plays with non zero probability is referred to as the support of σ. A mixed strategy is a best response if and only if every pure strategy within its support is itself a best response. For example, for a two-player game ${\displaystyle (A,B)\in {\left({\mathbb{R}}^{m\times n}\right)}^2}$, a strategy ${\displaystyle {\sigma }_r^{\ast }}$ of the row player is a best response to a strategy ${\displaystyle {\sigma }_c}$ of the column player if and only if:

$${\displaystyle {\sigma }_r^{\ast }(i)>0\Rightarrow (A{\sigma }_c^{\mathsf{T}}{)}_i=\underset{k\in {\mathcal{A}}_1}{max}(A{\sigma }_c^{\mathsf{T}}{)}_k\mathrm{\forall }i\in {\mathcal{A}}_1}$$

where the term ${\displaystyle (A{\sigma }_c^{\mathsf{T}}{)}_i}$ represents the utility for the row player when playing their ${\displaystyle i^{\mathrm{t}\mathrm{h}}}$ action.

Minimax

Given a zero-sum game defined by a payoff matrix ${\displaystyle M\in {\mathbb{R}}^{m\times n}}$ and a strategy ${\displaystyle y\in {\mathbb{R}}^n}$ for the column player, the row player seeks a best response strategy ${\displaystyle x\in {\mathbb{R}}^m}$ that maximises their expected payoff: ${\displaystyle \underset{x\in {\mathcal{A}}_1}{max}xM{y}^{\mathsf{T}}}$. This corresponds to choosing the rows of ${\displaystyle M}$ that yields the highest expected value under the strategy ${\displaystyle y}$, i.e.,${\displaystyle \underset{i\le m}{max}(M{y}^{\mathsf{T}}{)}_i}$. The column player, by selecting ${\displaystyle y}$, can influence the upper bound ${\displaystyle v}$ of this maximum. Since the game is zero-sum, the column player will aim to choose ${\displaystyle y}$ to make this upper bound ${\displaystyle v}$ as small as possible. Hence:

$${\displaystyle \underset{x\in {\mathcal{A}}_1}{max}xM{y}^{\mathsf{T}}=\underset{i\le m}{max}(M{y}^{\mathsf{T}}{)}_i=min\left\{v\in \mathbb{R}\mid M{y}^{\mathsf{T}}\le 1v\right\}}$$.

The min-max strategy ${\displaystyle 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:

$${\displaystyle \begin{array}{ll}{\displaystyle \underset{y,v}{min}}& v\\ \text{subject to}& M{y}^{\mathsf{T}}\le 1v\\ & y\in {\mathcal{A}}_2\end{array}}$$

The corresponding max-min strategy ${\displaystyle x}$ for the row player solves the following linear program, where u is the max-min value of the game:

$${\displaystyle \begin{array}{ll}{\displaystyle \underset{x,u}{max}}& u\\ \text{subject to}& xM\ge 1u\\ & x\in {\mathcal{A}}_1\end{array}}$$

The minimax theorem states that, for all constant-sum games, if there exist:

1. optimal values of u and the ''max-min'' strategy x,
2. optimal values of v and the ''min-max'' strategy y,

then, ${\displaystyle u=v}$. In less formal terms, it holds that optimal strategies exist that minimize potential losses in every constant-sum game.

Nash

Formally stated, in an N-player normal form game, a Nash equilibrium is defined as a strategy profile ${\displaystyle \tilde{s}=({\tilde{s}}_1,{\tilde{s}}_2,\dots ,{\tilde{s}}_N)}$ such that:

$${\displaystyle u_i(\tilde{s})=\underset{{\tilde{s}}_i\in \mathrm{\Delta }(A_i)}{max}{u}_i({\tilde{s}}_i,{\tilde{s}}_{-i})\mathrm{\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.

Strict and non-strict

In other words, an act profile is a Nash equilibrium if each player is playing a best response to the joint play of the others, such that no player could have improved her payoff by changing her act while all others kept theirs the same. This is a weak stability concept; no player could gain from such a hypothetical unilateral deviation, but one might be just as well off. If, in addition, any unilateral deviation would have made the deviating player’s payoff strictly worse, it is a strict Nash equilibrium, which is relates to a strong sense of stability.

Pure and mixed strategies

Consider normal form games with a finite number of players, each with a finite number of possible acts. The vector of payoffs for the players is a function of the vector of acts for each player, the act profile. The set of players, the set of acts available for each player and the payoff function jointly define a normal-form game. A mixed strategy, on the other hand, allows each player to choose a probability distribution over pure strategies. In computing the payoff vector resulting from a vector of mixed strategies, a joint probability distribution is formed, such that payoffs are taken to be expected payoffs according to this joint probability distribution.

A mixed Nash equilibrium is analogous to a pure strategy Nash equilibrium in a different game, where players choose between an infinite number of randomizing devices to determine their acts in the original game. There are no strict Nash equilibria in mixed strategies that are not pure strategies, because of the assumption that the act probabilities are independent when forming the joint probability distribution.

Subgame perfect

In repeated games, it is possible to find a subgame perfect Nash equilibrium for subgames within the repeated game. If a game is infinitely repeated with relatively patient players, the folk theorem relates the payoff vector for each player to subgame perfect equilibria.

Correlated

Robert Aumann's correlated equilibrium concept generalises the Nash equilibrium further. Here, the joint probability distribution over player’s acts has no restrictions, and there is no assumption that the act probabilities are independent. Rather, in correlated equilibria, players may condition their behavior on some external random feature of their environment. This kind of solution is called correlated equilibrium because the actions of the players are correlated and not fully independent, even though communication or agreement might still be impossible. Correlated equilibrium solutions thus explain the emergence of cooperation in repeated games, even when cooperation seems irrational.

In a correlated equilibria game, the external random feature can be analogised to a lottery run by a mediator (i.e. the joint probability distribution), who makes recommendations to each player conditional on the observed outcome of the lottery. Players know the structure of the lottery and the joint probability of recommendations, and they can choose to either commit to the lottery or just take an action in the game. If for every action that will be recommended with positive probability, no unilateral deviation does better in the expectation conditional on this act, then the joint probability distribution is a correlated equilibrium.

Correlated equilibria extend mixed Nash equilibria, and strict correlated equilibria extend strict Nash equilibria.

Coarse

A coarse correlated equilibrium further lifts the assumption of players calculating the expectation conditional on the action recommended to them. Analogously, the coarse-correlated equilibrium is like an arbitrator rather than a mediation, such that whereas the player chooses to accept or deviate from a mediator's recommendations, players in a coarse correlated equilibrium game decide whether to leave it to the arbitrator or just choose one of the acts.

Von Neumann–Morgenstern stable set

In cooperative game theory, a Von Neumann–Morgenstern solution, or stable set, is a set of outcomes that does not provide for effective mutual objections, while also containing at least one effective objection against any outcome that does not belong to the set. Von Neumann and Morgenstern's initial interpretation of vNM sets were as standards of behavior, although they can also be interpreted as sets of distinct feasible outcomes, over which games can be defined and played, or, for example, as maximal collections of mutually consistent modes of behaviour occupying niches of a given environment. More generally, vNM solutions can be applied to virtually any type of game, including non-cooperative games.

Formally, using graph theory, a vNM set can be defined as follows. Let D denote a simple directed graph, ${\displaystyle D=(X,\mathrm{\Delta })}$, where ${\displaystyle X}$ is a set and ${\displaystyle \mathrm{\Delta }\subseteq X\times X}$. D is irreflexive if and only if ${\displaystyle (x,x)\notin \mathrm{\Delta }}$ for any ${\displaystyle x\in X}$. (In contrast, it is symmetric if and only if ${\displaystyle (y,x)\in \mathrm{\Delta }}$ whenever ${\displaystyle (x,y)\in \mathrm{\Delta }}$ for any ${\displaystyle x,y\in X}$). A vNM-stable set of an irreflexive simple digraph, ${\displaystyle (X,\mathrm{\Delta })}$, is a set ${\displaystyle S\subseteq X}$, such that the following conditions hold:

1. internal stability, i.e., ${\displaystyle [(x,y)\notin \mathrm{\Delta }\text{ for any }x,y\in S]}$, and
2. external stability, i.e., ${\displaystyle [\text{for any }z\in X\setminus S,\text{ there exists }x\in S\text{ such that }(x,z)\in \mathrm{\Delta }]}$.

Static games

Repeated

In a repeated game, the same base game (or stage game) is played over and over, a learning dynamic, such as fictitious play, is introduced. Under fictitious play, players will inductively form beliefs about the other's likely moves based on past repeated games, and they will correspondingly play the best response to the historical frequency of opponents' play. Fictitious play is modelled by gradient dynamics, that is, a gradual adjustment in direction of increasing utility. On a logarithmic time scale, in the long-run this is essentially the same thing as continuous adjustment in the direction of increasing utility.

One strategy in repeated games is for players to use Bayesian inference using Laplace's rule of succession, such that others’ frequencies of past play are taken as a proxy for probabilities of next play. Via punishment strategies in the repeated game, equilibria may also be sustained that would not be equilibria at all in the stage game. For example, cooperation in the repeated prisoner’s dilemma can be sustained by tit-for-tat or grim trigger strategies. For the entire repeated game, the payoffs of strategies are computed by geometrically discounting the future and summing the infinite series.

Nash bargaining

In bargaining, Nash argued, agents agree on the bargaining outcome that maximizes the product of the differences between their utilities at the disagreement point and the cooperative outcome. This Nash bargaining solution forms a natural agreement point for rational agents in conflict situations in which their bargaining process is unrestricted and free from ethical considerations. The Nash solution is further free of the need to consider interpersonal utility comparisons (i.e. comparisons of the welfare functions of different individuals), as it relies merely on comparisons of differences of intrapersonally determined utility ratios that, normatively, are considered to be uncontroversial.

An alternative solution to the bargaining game is the egalitarian bargaining solution, which selects the bargaining outcome that maximizes the minimum payoffs (surplus utilities) among agents, granting to agents equal utility gains above the disagreement point. The solution is known as egalitarian as it is considered to lead to fairer distributional outcomes. At the same time, however, if agents do not find agreement on more specific criteria of merit and the precise weight of such criteria, then the agents’ gains will depend on their ability to transform resources into utility compared to the ability of other agents to do so. Thus, the egalitarian bargaining solution requires the use of interpersonal utility comparisons, holding that the agents’ utility functions must first be normalized in such a way that utility differences are interpersonally comparable.

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.

Cournot competition

The Cournot competition model involves players choosing quantity of a homogenous product to produce independently and simultaneously, where marginal cost can be different for each firm and the firm's payoff is profit. The production costs are public information and the firm aims to find their profit-maximizing quantity based on what they believe the other firm will produce and behave like monopolies. In this game firms want to produce at the monopoly quantity but there is a high incentive to deviate and produce more, which decreases the market-clearing price. For example, firms may be tempted to deviate from the monopoly quantity if there is a low monopoly quantity and high price, with the aim of increasing production to maximize profit. However this option does not provide the highest payoff, as a firm's ability to maximize profits depends on its market share and the elasticity of the market demand. The Cournot equilibrium is reached when each firm operates on their reaction function with no incentive to deviate, as they have the best response based on the other firms output. Within the game, firms reach the Nash equilibrium when the Cournot equilibrium is achieved.

Bertrand competition

The Bertrand competition assumes homogenous products and a constant marginal cost and players choose the prices. The equilibrium of price competition is where the price is equal to marginal costs, assuming complete information about the competitors' costs. Therefore, the firms have an incentive to deviate from the equilibrium because a homogenous product with a lower price will gain all of the market share, known as a cost advantage.

Dynamic games

Evolutionary

Under traditional game theory (TGT), games face significant limitations in real-world applications, owing to the inapplicability of non-bounded rationality, information asymmetries, and the dynamism of interactions. Originating as a field of mathematical biology, evolutionary game theory (EGT) adopts a more flexible and adaptive approach, aiming to capture factors such as the long-term dynamic adjustments of players and the time of evolution. Evolutionary models typically assume that agents rely on common background knowledge, shared history, focal points, signaling behavior, learning behavior, and/or imitation of past behaviors for equilibrium selection.

Under EGT, the focus is less on equilibria that correspond to a notion of rationality, but instead equilibria that are maintained by evolutionary forces, such that players are not necessarily rational and strategies are accordingly not adjusted according to rational rules. The best-known equilibrium in biology is the evolutionarily stable strategy (ESS), which is equivalent to a Nash equilibrium in TGT. Another distinct concept in EGT is that of replicator dynamics, which model the speed of response to strategy-selection adjustments via differential equations. In general terms, the rate at which the frequency of strategy adoption changes, with respect to time, is directly proportional to the difference between the expected gain and population average gain. More formally, a general replicator equation can be expressed as follows:

${\displaystyle \dot{x_i}=x_i[f_i(x)-\varphi (x)],\varphi (x)=\sum _{j=1}^n{x}_j{f}_j(x)}$

where

• ${\displaystyle x_i}$ is the probability or frequency of a particular pure strategy being adopted in a population,
• ${\displaystyle x=(x_1,\dots ,x_n)}$ represents the overall distribution of strategies in the population,
• ${\displaystyle f_i(x)}$ is the fitness, or expected utility of strategy ${\displaystyle i}$,
• and ${\displaystyle \varphi (x)}$ is the average population fitness or utility (given by the weighted average of the fitness of the ${\displaystyle 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.

Biology

Unlike those in traditional game theory, the payoffs for games in EGT are often interpreted as corresponding to fitness. In addition, offspring generally adopt their parents' "strategies" and parents who play more successful strategies have a greater number of offspring.

In population genetics, EGT provides an explanation for the stability of the approximate 1:1 sex ratios, in light of the evolutionary forces acting on players trying to maximize their number of grandchildren. In animal communication, EGT has also been used to model and explain communicative behaviours by way of signaling games and other communication games. Ethologists have also used the game of chicken to analyze fighting behavior and territoriality.

Frequency-dependent selection and population polymorphism

In EGT, the Hawk-Dove game is a two-player game where the row and column players can choose to either exhibit hawk or dove phenotypes. When one player chooses Hawk and the other Dove, Hawk gets the resource, while Dove retreats before injury. When two Hawks meet, they engage in an escalating fight, seriously risking injury. When two Doves meet, they share the resource.

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:${\displaystyle p=\frac{E_{HD}-E_{DD}}{\left(E_{HD}-E_{DD}\right)+\left(E_{DH}-E_{HH}\right)}}$, where p is the frequency of hawks.

Biological altruism and kin selection

Biological altruism is the situation in which an organism appears to act in a way that benefits other organisms, in particular, those of a group, but is detrimental to itself. EGT explains this phenomena by way of kin selection; Hamilton's rule states that c < b × r where the cost c to the altruist must be less than the benefit b to the recipient multiplied by the coefficient of relatedness r. That is to say, because closely related organisms share many of the same alleles, incidences of altruism increase where the altruistic player can ensure those alleles of its close relative are passed on through survival of the latter's offspring. This behaviour occurs even where it requires the altruist to forgo the option of having offspring itself, because the same number of alleles are passed on.

Stackelberg game

The Stackelberg game, also known as the leader-follower game, is a dynamic form of game where players of differing power participate in a sequential order over time, assuming that all players have perfect information, but they do not know the next moves of other participants. In a Stackelberg game, leaders (e.g., producers with high market power) make the first move, and followers (e.g. consumers) select actions based on the leaders’ decisions.

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.

Games of computation

Game theory is widely applied in the computational and formal sciences, including in artificial intelligence (e.g. autonomous agents, machine learning, robotics), computer networking (e.g. blockchain, cybersecurity), and the digital economy (e.g. advertising auctions, surge pricing, matching markets). It is used as a basis for the modelling, analysis and development of communication protocols, interactive computations, and multi-agent systems.

Algorithmic

Algorithmic game theory (AGT), and within it algorithmic mechanism design, combine computational algorithm design and analysis of complex systems with classical methods of game theory. AGT is widely used in the development of online games, e-commerce markets, computational auctions, peer-to-peer systems, securities markets, and information markets.

Game theory has played a role in online algorithms; in particular, the k-server problem, which has in the past been referred to as games with moving costs and request-answer games. Yao's principle is a game-theoretic technique for proving lower bounds on the computational complexity of randomized algorithms, especially online algorithms.

Combinatorial

Games in which the difficulty of finding an optimal strategy stems from the multiplicity of possible moves are called combinatorial games. Examples include chess, shogi, and Go. Games that involve imperfect information may also have a strong combinatorial character, for instance backgammon. There is no unified theory addressing combinatorial elements in games. There are, however, mathematical tools that can solve some particular problems and answer some general questions.

Games of perfect information have been studied in combinatorial game theory, which has developed novel representations, e.g. surreal numbers, as well as combinatorial and algebraic (and sometimes non-constructive) proof methods to solve games of certain types, including "loopy" games that may result in infinitely long sequences of moves. These methods address games with higher combinatorial complexity than those usually considered in traditional (or "economic") game theory. A typical game that has been solved this way is Hex. A related field of study, drawing from computational complexity theory, is game complexity, which is concerned with estimating the computational difficulty of finding optimal strategies.

Research in artificial intelligence has addressed both perfect and imperfect information games that have very complex combinatorial structures (like chess, go, or backgammon) for which no provable optimal strategies have been found. The practical solutions involve computational heuristics, like alpha–beta pruning or use of artificial neural networks trained by reinforcement learning, which make games more tractable in computing practice.

Stochastic outcomes

Individual decision problems with stochastic outcomes are sometimes considered "one-player games". They may be modeled using similar tools within the related disciplines of decision theory, operations research, and areas of artificial intelligence, particularly AI planning (with uncertainty) and multi-agent system. Although these fields may have different motivators, the mathematics involved are substantially the same, e.g. using Markov decision processes (MDP).

Stochastic outcomes can also be modeled in terms of game theory by adding a randomly acting player who makes "chance moves" ("moves by nature"). This player is not typically considered a third player in what is otherwise a two-player game, but merely serves to provide a roll of the dice where required by the game.

For some problems, different approaches to modeling stochastic outcomes may lead to different solutions. For example, the difference in approach between MDPs and the minimax solution is that the latter considers the worst-case over a set of adversarial moves, rather than reasoning in expectation about these moves given a fixed probability distribution. The minimax approach may be advantageous where stochastic models of uncertainty are not available, but may also be overestimating extremely unlikely (but costly) events, dramatically swaying the strategy in such scenarios if it is assumed that an adversary can force such an event to happen. (See Black swan theory for more discussion on this kind of modeling issue, particularly as it relates to predicting and limiting losses in investment banking.)

General models that include all elements of stochastic outcomes, adversaries, and partial or noisy observability (of moves by other players) have also been studied. The "gold standard" is considered to be partially observable stochastic game (POSG), but few realistic problems are computationally feasible in POSG representation.

Relation to other fields

Economics

Game theory is a major method used in mathematical economics and business for modeling competing behaviors of interacting agents. Applications include a wide array of economic phenomena and approaches, such as auctions, bargaining, mergers and acquisitions pricing, fair division, duopolies, oligopolies, social network formation, agent-based computational economics, general equilibrium, mechanism design, and voting systems; and across such broad areas as experimental economics, behavioral economics, information economics, industrial organization, political economy, and managerial economics.

A prototypical paper on game theory in economics begins by presenting a game that is an abstraction of a particular economic situation. One or more solution concepts are chosen, and the author demonstrates which strategy sets in the presented game are equilibria of the appropriate type. Economists and business professors suggest two primary uses (noted above): descriptive and prescriptive.

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 W.V.O. Quine (1960, 1967), Lewis (1969) 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 Lewis (1969) 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 Gauthier (1986) and Kavka (1986)).

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., Skyrms (1996, 2004) and Sober and Wilson (1998)).

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 1663. 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 Recherches sur les principes mathématiques de la théorie des richesses (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 Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels (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 Applications aux Jeux de Hasard 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.

As a formal discipline (early–mid 20th century)

The work of American mathematician John von Neumann established game theory as its own independent field in the early-to-mid 20th century, with von Neumann publishing his paper On the Theory of Games of Strategy (1928), which proved the minimax theorem. Von Neumann's original proof used Brouwer's fixed-point theorem on continuous mappings into compact convex sets, which became a standard method in game theory and mathematical economics. Von Neumann's work in game theory culminated in his 1944 book Theory of Games and Economic Behavior, co-authored with German political scientist and economist Oskar Morgenstern.

This foundational work provided the first comprehensive formal model for situations in which each participant’s outcomes depend not only on their own choices but also on the choices of others, also containing the method for finding mutually consistent solutions for two-person zero-sum games. Their subsequent work focused primarily on cooperative game theory, which analyzes optimal strategies for groups of individuals, presuming that they can enforce agreements between them about proper strategies.

Building upon the work of von Neumann and Morgenstern, the Princeton mathematician John Forbes Nash Jr in 1950 formalised a solution concept (later known as the Nash equilibrium) for non-cooperative games that were not necessarily zero-sum contests. In his 1950 paper, Nash also proved that every finite non-cooperative game had at least one Nash equilibrium solution. The generality of the Nash equilibrium allowed it to be applied to scenarios such as oligopoly pricing and environmental agreements. Further, Nash’s bargaining model offered a formal framework for negotiations.

Early, theoretic Nobel-winning work (c. 1950s–1980s)

Game theory experienced a flurry of activity in the 1950s, during which the concepts of the core, the extensive form game, fictitious play, repeated games, and the Shapley value were developed. The 1950s also saw the first applications of game theory to philosophy and political science. The first mathematical discussion of the prisoner's dilemma appeared, and an experiment was undertaken by mathematicians Merrill M. Flood and Melvin Dresher, as part of the RAND Corporation's investigations into game theory. RAND pursued the studies because of possible applications to global nuclear strategy.

In 1994, the first Nobel Prize in economics given to game theorists was awarded to the mathematician John Nash, the philosopher John Harsanyi, and the economist Reinhard Selten for “for their pioneering analysis of equilibria in the theory of non-cooperative games”. Harsanyi had applied Bayesian inference to game theory in formulating Bayesian games, whereas Selten had introduced the solution concept of subgame perfect equilibria, which further refined the Nash equilibrium, and the trembling hand perfection, among other contributions. In 1996, the economist William Vickrey, who had applied game theory to the field of auction theory, was announced as a half-winner of the Nobel for "fundamental contributions to the economic theory of incentives under asymmetric information”, but he died before he could receive it.

In 2005, the American economist Thomas Schelling and Israeli mathematician Robert Aumann were awarded the Nobel “for having enhanced our understanding of conflict and cooperation through game-theory analysis”. Schelling had showed how strategic behavior and coordination can emerge even from simple individual choices, particularly through focal points and dynamic models of conflict and cooperation. Aumann introduced correlated equilibrium and repeated games, showing how cooperation can persist over time even among self-interested actors.

In 2007 the legally-trained Polish-American economist Leonid Hurwicz, and the American mathematicians Eric Maskin and Roger Myerson, won the Nobel “for having laid the foundations of mechanism design theory”. Hurwicz was the first to develop mechanism design theory, which shifted attention from analyzing outcomes of given rules to designing rules that yield socially desirable outcomes even under self-interest.

In 2012, Alvin E. Roth and Lloyd S. Shapley were warded the Prize “for the theory of stable allocations and the practice of market design”. In particular,Shapley's application of game theory in market design led to the concept of the market game.

Recent laureates include Jean Tirole (2014), and Paul Milgrom and Robert B. Wilson (2020).

Computational and alternative game theories

John Maynard Smith applied game-theoretic concepts to evolutionary biology, defining evolutionarily stable strategies that cannot be displaced once established in a population. The 1990s also brought computational advancements and refined mechanism design, enabling large-scale applications in telecommunications, market platforms, and auctions. In the 2000s, behavioral game theory incorporated insights from psychology, exploring bounded rationality, fairness, and reciprocity, challenging the assumption of perfect rationality.

From the 2010s onward, game theory has become deeply embedded in the digital economy and artificial intelligence. Today, its applications span almost every domain. In economics and markets, it shapes auction design, antitrust policy, and matching markets. In politics and international relations, it informs voting systems, coalition-building, treaty design, and deterrence strategies. In military and security, it guides defense planning, cybersecurity, and counterterrorism resource allocation. In biology and ecology, it models evolutionary dynamics and cooperation among species. In business and management, it informs supply chain negotiations, contract structures, and competitive strategy.