Game theory

History

The significance of the work of the early game theorists in economics was its formalisation of strategic interaction, equilibrium concepts, and rational choice behavior, under the assumptions of perfect rationality, self-interest, complete information, and fixed game structure.^[14] Game theory as a field had its genesis in the 1944 book Theory of Games and Economic Behavior, written my mathematicians John von Neumann and Oskar Morgenstern. The book built upon von Neumann's earlier work, which used the Brouwer fixed-point theorem on continuous mappings into compact convex sets, a method that later became standard in game theory and mathematical economics.^[15] In 1994, the Nobel Prize in economics was awarded to the game theorists John Forbes Nash, Reinhard Selten, and John Harsanyi.^[3][9]

Initially, as a field of applied mathematics, game theory was used in economics to describe and predict the behaviors of firms, markets, and consumers. The use of game theory in the social sciences has since expanded, with game theory later being widely applied in the analysis of political, sociological, psychological, and animal behaviours.^[16][17] Modern academic research finds applications of game theory in fields as broad as international relations, network science, voting systems, linguistics, law, distributed control, policy design, competition regulations, project management, and military technology.^[9][18]

Game theory has also been used to develop theories of ethical or normative behavior and to prescribe such behavior.^[19][20] In economics and philosophy, scholars have applied game theory to help in the understanding of good or proper behavior. Game-theoretic approaches have also been suggested in the philosophy of language and philosophy of science.^[21]

Theory and methodology

The main branches of economic theory are game theory, decision theory, mechanism design theory, and general equilibrium theory. Unlike game theory, which analyses multi-agent interactions, decision theory focuses on preferences and the formation of beliefs within single-player scenarios. Decision theory is often used in the form of decision analysis, which shows how best to acquire information before making a decision. Mechanism design theory is closely related to game theory, although the former is more focused on about the consequences of different types of rules, whereas the latter often takes the rules of the game as given. Areas of focus within mechanism design include compensation, wages, risk, incentives, and auctions.^[22] Within game theory and mechanism design, a metagame refers to a game that aims to develop rules for the target or subject game, being applied in the contexts of metagame analysis, and confrontation analysis.^[23]

Although game theory has broad application in general equilibrium theory, general equilibrium economists are usually concerned with macroeconomic issues of trade and production in scenarios with a very large number of individual consumers and producers. In particular, the theory of dynamic stochastic general equilibrium (DSGE) is applied, often in combination with game theoretic methods, to issues of investment management, political economy, industrial organisation, international trade, and monetary, fiscal, and tax policy.^[22]

As an economic methodology, game theory provides a framework for the analysis of decision-making processes involving multiple stakeholders, each with conflicting or cooperative objectives. Unlike traditional econometric models that are descriptive (in the sense of predicting future outcomes based on historical data and statistical trends between variables) and optimisation algorithms (which assume static environments and generally address single-objective problems within predefined constraints), game theory is inherently dynamic and accounts for the strategic interactions among participants. Game theory can further be applied in simulation-based approaches, such as agent-based modeling, in order to replicate market dynamics and policy outcomes under different scenarios by way of modelling reward-punishment mechanisms, competition for limited resources, and coalition formation.^[24]

Games

A game is cooperative if the players are able to form binding commitments externally enforced (e.g. through contract law). A game is non-cooperative if players cannot form alliances or if all agreements need to be self-enforcing (e.g. through credible threats).^[25]

A symmetric game is a game where each player earns the same payoff when making the same choice. The identity of the player does not change the resulting game facing the other player, and the game looks the same to all players.^[26][27] Formally, a symmetric two-player game can be defined as one where the matrix of one player's payoffs is the transpose of the other player's payoffs.^[28][29]

Zero-sum games (or constant-sum games) are games in which choices by players can neither increase nor decrease the available resources. More informally, in such a game, a player benefits only at the equal expense of others.^[30]

Simultaneous games are games where both players move simultaneously, such that all players are unaware of the actions of other players. Sequential games are games where players do not make decisions simultaneously, and player's earlier actions affect the outcome and decisions of other players.^[31]

Games typically are assumed to be finite and discrete, with a finite number of players, moves, events, and outcomes. Nonetheless, continuous games allow players to choose a strategy from a continuous strategy set. For example, Cournot competition is typically modeled with players' strategies being any non-negative quantities, including fractional quantities.^{[citation needed]}

Strategies

A pure strategy is a deterministic strategy, whereas a mixed strategy is probabilistic. Games can be divided into strictly and non-strictly determined games, such that a non-strictly determined game possesses only mixed strategies, whereas a strictly determined game possesses pure strategies as well.^[43][44] Only a strictly determined game possesses a saddle point, that is, an equilibrium that represents the best strategies for all players.^[45]

For a two-player game, a dominant strategy for a given player is a strategy that produces a better payoff than the other player; conversely, a dominated strategy is one that is always worse than the other player and therefore never rational to play.^[46][41]

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:^[43]

$${\displaystyle \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) ${\displaystyle A}$ available to each player are, respectively, ${\displaystyle A_{1}=\{r_{i}\mid 1\leq i\leq m\}}$ and ${\displaystyle A_{2}=\{c_{j}\mid 1\leq j\leq 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:^[43]

$${\displaystyle (M_{r})_{ij}=u_{1}(r_{i},c_{j})\qquad (M_{c})_{ij}=u_{2}(r_{i},c_{j})}$$

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.^[53][54]

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.^[55][56]

Battle of the sexes

Main article: Battle of the sexes (game theory)

	Preferred Action (action1)	Unpreferred action (action2)
Unpreferred action (action1)	1,2	0,0
Preferred action (action2)	0,0	2,1
Battle of sexes (note that they both want to do the same action but have different preferences)

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

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.^[59]

Formally, a characteristic function is a function ${\displaystyle v:2^{N}\to \mathbb {R} }$^[60] from the set of all possible coalitions of players to a set of payments, and also satisfies ${\displaystyle v(\emptyset )=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.^[61] In addition to classical game representations, some of the alternative representations also encode time related aspects.

Best response

In an N-player normal form game, a strategy ${\displaystyle s^{*}}$ 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^{*},s_{-i})\geq u_{i}(s,s_{-i})\qquad \forall s\in \Delta ({\mathcal {A}}_{i}).}$

That is, ${\displaystyle s^{*}}$ 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}^{*}}$ 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}^{*}(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 ${\displaystyle (A\sigma _{c}^{\mathsf {T}})_{i}}$ represents the utility for the row player when playing their ${\displaystyle i^{\mathrm {th} }}$ action.^[41]

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 \max _{x\in {\mathcal {A}}_{1}}xMy^{\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 \max _{i\leq m}(My^{\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:^[76]

$${\displaystyle \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 ${\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:^[76]

$${\displaystyle {\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 ${\displaystyle x}$ for the row player solves the following linear program, where u is the max-min value of the game:^[76]

$${\displaystyle {\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:^[77]

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.^[14]

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},\ldots ,{\tilde {s}}_{N})}$ such that:^[78]

$${\displaystyle 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.^[78][79] At the same time, it is also known that every finite game with perfect information has a Nash equilibrium in pure strategies.^[80]

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.^[82]

Correlated

Robert Aumann's correlated equilibrium concept generalises the Nash equilibrium further.^[83][84] 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.^[81] 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.^[36]

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.^[81]

Correlated equilibria extend mixed Nash equilibria, and strict correlated equilibria extend strict Nash equilibria.^[81]

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 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.^[85]

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

1. internal stability, i.e., ${\displaystyle [(x,y)\notin \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 \Delta ]}$.^[85]

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.^[81][82]

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.^[81]

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.^[86][87] 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.^[88]

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.^[88]

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.^[89]

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.^[90]

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.^[91]

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.^[92]

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.^[35] 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.^[35] 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.^[93] 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.^[35] 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.^[35] 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.^[94]

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.^[9] 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.^[24] 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.^[95]

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.^[96] The best-known equilibrium in biology is the evolutionarily stable strategy (ESS), which is equivalent to a Nash equilibrium in TGT.^[97] 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:^[24]

where

• ${\displaystyle x_{i}}$ is the probability or frequency of a particular pure strategy being adopted in a population,
• ${\displaystyle x=(x_{1},\ldots ,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 \phi (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.^[98]

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.^[104]

More information , ...

Hawk-dove payoff matrix to column player^[104]

	Hawk	Dove
Hawk	${\displaystyle E_{HH}=-2}$	${\displaystyle E_{HD}=-2}$
Dove	${\displaystyle E_{DH}=-2}$	${\displaystyle E_{DD}=-2}$

Close

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.

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.^[24]

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.^[106] 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.

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.^{[111][112][113][114][115]}

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.^[116] 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.^[117]

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.^[118][119] 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.^[120]

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.^[117][121]

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).^[122]

Stochastic outcomes can also be modeled in terms of game theory by adding a randomly acting player who makes "chance moves" ("moves by nature").^[123] 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.^[124] (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.^[124]

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.^{[154][155][156][157][158]}

Early examples of game theory applied to political science are provided by Anthony Downs. In his 1957 book An Economic Theory of Democracy,^[159] 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.^[160]

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.^[161][162] 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.^[163][164]

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),^[165][166] Skyrms (1990),^[167] and Stalnaker (1999).^[168]

The synthesis of game theory with ethics was championed by R. B. Braithwaite.^[169] 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.^[170]

In ethics, some (most notably David Gauthier, Gregory Kavka, and Jean Hampton) ^[who?] 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)).^[b]

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.^{[citation needed]}

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.^[171][172]

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.^[77] 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.^[184][185]

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.^[14] 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.^[186]

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.^[79] 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.^[14]

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.^[187]

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.^[3][14] 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.^[14][188]

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”.^[4] 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.^[189][14]

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”.^[5] 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.^[14]

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”.^[6] In particular,Shapley's application of game theory in market design led to the concept of the market game.^[14][190]

Recent laureates include Jean Tirole (2014),^[7] and Paul Milgrom and Robert B. Wilson (2020).^[8]

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.^[191] 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.^[14]

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.^[14]