flowchart TD
A0(("Alice"))
Ba(("Bob"))
Bb(("Bob"))
Abf(("Alice"))
Tac["(0, 4)"]
Tad["(2, 1)"]
Tbe["(1, 2)"]
Tbg["(3, 8)"]
Tbh["(8, 0)"]
A0 -->|"a: stay home"| Ba
A0 -->|"b: go out"| Bb
Ba -->|"c: action film"| Tac
Ba -->|"d: cook together"| Tad
Bb -->|"e: cafe"| Tbe
Bb -->|"f: live music"| Abf
Abf -->|"g: rock club"| Tbg
Abf -->|"h: jazz club"| Tbh
classDef decision fill:#ffffff,stroke:#111111,stroke-width:2px,color:#111111;
classDef terminal fill:#ffffff,stroke:#ffffff,color:#111111;
class A0,Ba,Bb,Abf decision;
class Tac,Tad,Tbe,Tbg,Tbh terminal;
1 Strategic games
1.1 Introduction and motivation
Game theory is the mathematical study of interactive decision-making, where multiple agents pursue their own objectives and each player’s outcome depends on the decisions made by all players.
The defining feature is strategic interdependence: the outcome depends on the choices of several decision-makers, and what is best for one player can depend on what the others choose. Players may be people, firms, institutions, or autonomous agents. Applications include bargaining, markets, auctions, voting, security, cost allocation, and multi-agent learning.
A utility function represents a player’s preferences over outcomes. Utility need not be money, and utility maximization need not mean selfish behavior. If a player values fairness, safety, or another person’s welfare, those concerns can be part of that player’s preferences.
The modern theory grew from the minimax analysis of two-player zero-sum games (Neumann 1928). Nash equilibrium supplied a general consistency condition for non-cooperative games (Nash 1951), while the Shapley value formalized a method for allocating the gains from cooperation (Shapley 1953). Auction and mechanism design later made strategic reasoning part of the design of markets and institutions (Vickrey 1961; Myerson 1981).
1.1.1 From optimization to strategic reasoning
The standard unilateral optimization treats the environment as fixed. A decision-maker controls the relevant variables and evaluates a single objective. In a game, some variables are controlled by other decision-makers who are optimizing too.
| Optimization | Game theory |
|---|---|
| One decision-maker | Several decision-makers |
| One objective | Each player has an objective |
| The decision-maker controls the variables | The outcome depends on everyone’s choices |
| What is my best feasible decision? | What is best when others choose strategically too? |
Game theory extends optimization rather than replacing it. Once the opponents’ choices are fixed, a player’s problem is again an optimization problem. The difficulty is to make the players’ optimization problems mutually consistent.
1.1.2 From human players to artificial agents
The word player first suggests a person, but the formal concept is more abstract: a player is any decision-making entity to which we assign available strategies and preferences over outcomes. It may therefore represent a person, a firm, an institution, a software agent, or an entire platform.
Strategic interaction among humans has not disappeared, but more decisions are now delegated to algorithms or mediated by computational systems:
- trading algorithms interact in financial markets;
- ride-hailing and airline platforms update prices dynamically;
- recommender systems influence which alternatives users encounter;
- users, developers, and other agents can strategically influence the behavior of systems built around large language models;
- self-play and adversarial training place learned agents in deliberate competition.
Games have also become important testbeds for artificial intelligence: AlphaGo, DeepStack, and AlphaStar demonstrated strong performance in settings with very different action spaces and information structures (Silver et al. 2016; Moravčík et al. 2017; Vinyals et al. 2019).
This shift raises a conceptual and practical challenge. For an artificial player, we must decide what counts as its information, objective, and strategy; we must also ask whether behavior observed in a test predicts behavior after deployment. Kovařík and coauthors argue that advanced systems may recognize and respond strategically to evaluation itself. Game-theoretic models can make the resulting assumptions explicit and help scrutinize evaluation-based safety claims (Kovařík et al. 2025). Thus games are not only environments in which AI systems act: they can also become controlled tests of competition, coordination, manipulation, and response to incentives.
1.1.3 Taxonomy of games
Games can be classified along several related dimensions. The categories in different rows can be combined: a single game may be dynamic, finite, general-sum, non-cooperative, complete-information, and perfect-information at the same time.
| Modelling question | Main alternatives |
|---|---|
| How are choices represented? | normal form, extensive form |
| Is the focus on individual choices or coalitions? | non-cooperative, cooperative, coalitional |
| When are choices made? | static, dynamic |
| What is observed during play? | perfect information, imperfect information |
| What is known about the game’s structure? | complete information, incomplete information |
| How large are the strategy sets? | finite, infinite |
| How are players’ interests related? | zero-sum, general-sum |
The normal form records strategies and utilities while suppressing the order of moves. The extensive form represents possible histories, who moves after each history, and what that player observes. A coalitional game instead emphasizes what groups of players can achieve together and how their joint value or cost might be allocated.
The information distinctions answer different questions. Perfect information means that every player who moves observes the complete history of earlier actions. Complete information means that the structure of the game - including the players, strategy sets, and utility functions - is common knowledge. A simultaneous auction can therefore have imperfect information during play and, when valuations are private, incomplete information about the game’s payoff-relevant data.
Three examples indicate the scope of the taxonomy:
- A sealed-bid auction is naturally described by simultaneous bids and can be represented in normal form.
- A sequence of observed decisions is naturally drawn as an extensive-form tree.
- Connecting several cities to a shared provider motivates a coalitional cost game: the central question is what each coalition can build and how the cost should be shared.
This chapter develops the first two solution methods for normal-form games: dominance and pure-strategy Nash equilibrium. It also distinguishes strategic stability from social efficiency and shows how a dynamic game can be converted to normal form.
1.2 Normal-form games and examples
1.2.1 Strategy profiles
The set of pure-strategy profiles is
\[ \mathbf S=\prod_{i\in N}S_i. \]
For player \(i\), write
\[ \mathbf S_{-i}=\prod_{j\ne i}S_j, \qquad \mathbf s=(s_i,\mathbf s_{-i}). \]
Thus \(s_i\in S_i\) denotes one strategy of player \(i\), \(\mathbf s\in\mathbf S\) selects one strategy for every player, and \(\mathbf s_{-i}\in\mathbf S_{-i}\) collects the opponents’ strategies. This notation makes a unilateral deviation transparent for player \(i\): replace \(s_i\) while holding \(\mathbf s_{-i}\) fixed.
To use a normal-form model, players select their strategies before observing one another’s strategy choices:
- each player \(i\) selects one strategy \(s_i\);
- the choices form a profile \(\mathbf s=(s_1,\ldots,s_n)\in\mathbf S\);
- player \(i\) receives utility \(u_i(\mathbf s)\).
In a dynamic game, an action is a move at a particular decision point. A strategy in such a game is a complete contingent plan since it may prescribe later actions after observed histories. In a one-stage game, a pure strategy consists of one action, so the terms are often used interchangeably. Section 1.6 makes this distinction precise.
1.2.2 Examples of two-player games
For a finite two-player game, a payoff matrix places player 1’s strategies in rows and player 2’s strategies in columns. The cell at \((s_1,s_2)\) contains \((u_1(s_1,s_2),u_2(s_1,s_2))\).
A two-player game is zero-sum if
\[ u_1(s_1,s_2)+u_2(s_1,s_2)=0 \qquad\text{for every }(s_1,s_2)\in S_1\times S_2. \]
General-sum games need not have either identical or exactly opposed interests.
1.3 Dominance
1.3.1 Rational choice
We model a rational player as choosing a strategy that maximizes their utility, given the available information about the opponents’ choices. Rationality is conditional: the best strategy can depend on what others do. It also imposes no particular moral content because the utility function itself represents what the player values.
Dominance provides a useful exception to this dependence. If one strategy is worse than another against every possible profile of opponents, a utility-maximizing player can discard it without predicting what the opponents will do.
A rational player never uses a strictly dominated pure strategy. Eliminating a weakly dominated strategy requires more care because an equality can matter for subsequent strategic comparisons.
1.3.2 Dominance in the prisoner’s dilemma
For player 1,
\[ u_1(D,C)=0>-1=u_1(C,C), \qquad u_1(D,D)=-3>-4=u_1(C,D). \]
Thus \(D\) strictly dominates \(C\). The game is symmetric, so \(D\) is also strictly dominant for player 2. The solution based on dominance is therefore \((D,D)\), without any belief about the other prisoner’s choice.
1.3.3 Iterated elimination
Iterated elimination of strictly dominated strategies applies the same reasoning repeatedly:
- begin with the full strategy sets;
- find a pure strategy that is strictly dominated in the current restricted game;
- delete it and form the reduced game;
- repeat until no further deletion is possible for any player.
Consider the following game between Alice (row player) and Bob (column player) as an example.
\[ \begin{array}{c|ccc} & c & d & e \\ \hline a & 1, 0 & 1, 2 & 0, 1 \\ b & 0, 3 & 0, 1 & 2, 0 \end{array} \]
This game is solved in three rounds:
- For Bob, \(d\) strictly dominates \(e\), so delete \(e\).
- In the reduced game, \(a\) strictly dominates \(b\) for Alice, so delete \(b\).
- Against the remaining row \(a\), Bob strictly prefers \(d\) to \(c\), so delete \(c\).
The sole surviving profile is \((a,d)\), with payoff \((1,2)\). The successive deletions can be interpreted as increasingly strong assumptions about players’ rationality and their reasoning about one another. A formal epistemic interpretation requires additional machinery.
Many games, including matching pennies and coordination games, contain no dominated pure strategies. Dominance is therefore a useful first test rather than a universal solution method.
1.4 Nash equilibrium
Dominance asks whether a player can reject a strategy without predicting the opponents. Nash equilibrium instead asks whether all players’ choices are mutually consistent. Equivalently, no player can gain through a unilateral deviation (Nash 1951).
Equilibrium is a stability condition. It does not imply uniqueness, fairness, or collective desirability, and it does not prevent players from benefiting through a coordinated change.
Proof. Since \(s_i^*\) is weakly dominant,
\[ u_i(s_i^*,\mathbf s_{-i}) \geq u_i(s_i,\mathbf s_{-i}) \]
for every \(s_i\in S_i\) and every \(\mathbf s_{-i}\in\mathbf S_{-i}\). In particular, for \(\mathbf s_{-i}=\mathbf s_{-i}^*\),
\[ u_i(s_i^*,\mathbf s_{-i}^*) \geq u_i(s_i,\mathbf s_{-i}^*) \]
for every player \(i\) and every \(s_i\in S_i\). \(\square\)
1.4.1 Best responses
Player \(i\)’s best-response correspondence is
\[ \operatorname{BR}_i(\mathbf s_{-i}) = \arg\max_{s_i\in S_i}u_i(s_i,\mathbf s_{-i}). \tag{1.2}\]
It is a set-valued mapping rather than necessarily a function because several strategies can tie for the maximum. In a finite game with nonempty strategy sets, the best-response set in (1.2) is nonempty.
Proof. This equivalence simply rewrites the inequalities in (1.1): each equilibrium strategy must maximize its player’s utility against the opponents’ equilibrium strategies. \(\square\)
1.4.2 Finding pure equilibria
In each column, mark player 1’s highest payoff. In each row, mark player 2’s highest payoff. Include all ties. A cell is a pure-strategy Nash equilibrium exactly when both players’ payoffs are marked.
The small games introduced above display several possible patterns:
| Game | Nash equilibria | Main lesson |
|---|---|---|
| Prisoner’s dilemma | \((D,D)\) | a unique equilibrium can follow from dominance |
| Matching pennies | none | pure strategies may be insufficient |
| Sharing household chores | none | general-sum games may also lack a pure equilibrium |
| Bach or Stravinski | \((B,B)\) and \((S,S)\) | coordination with conflicting preferences |
| Coordination game | \((a,a)\) and \((b,b)\) | equilibrium need not select one outcome |
No pure strategy is dominated in either game. In Bach or Stravinski, the players prefer different coordinated outcomes. In the coordination game, both prefer \((a,a)\) to \((b,b)\), yet neither player can move from \((b,b)\) to \((a,a)\) unilaterally.
Matching pennies and the household-chores game show why the next chapter introduces mixed strategies. Allowing randomization restores a general existence result for finite games; this chapter makes no such claim for pure strategies.
1.5 Equilibrium and efficiency
The following concept tries to address the question Which strategy profiles are socially efficient? One possible answer is when no player’s utility can be increased without simultaneously decreasing the utility to another player.
Define the social welfare of strategy profile \(\mathbf s\) by
\[ w(\mathbf s)=\sum_{i\in N}u_i(\mathbf s). \]
Proof. If \(\mathbf s^*\) maximizes \(w\) and another profile \(\mathbf s\) made every player weakly better off and at least one player strictly better off, summing the inequalities would give \(w(\mathbf s)>w(\mathbf s^*)\), a contradiction. \(\square\)
This is a method for finding one Pareto optimum, not a characterization of all Pareto optima. In a zero-sum game, every profile is Pareto optimal because the sum of utilities is constant.
The distinction from Nash equilibrium is fundamental:
| Game | Strategic stability | Pareto efficiency |
|---|---|---|
| Prisoner’s dilemma | \((D,D)\) is the unique equilibrium | \((D,D)\) is the only pure profile that is not Pareto optimal |
| Matching pennies | no pure equilibrium | every pure profile is Pareto optimal |
| Bach or Stravinski | \((B,B)\) and \((S,S)\) are equilibria | both equilibrium profiles are Pareto optimal |
| Coordination game | \((a,a)\) and \((b,b)\) are equilibria | only \((a,a)\) is Pareto optimal |
Nash equilibrium concerns unilateral deviations; Pareto optimality concerns joint comparisons. Neither concept generally implies the other.
1.6 Dynamic games and their normal form
The normal form can represent a dynamic interaction, but its strategies must then be understood as complete plans rather than single moves. The following Alice–Bob game makes the conversion explicit.
1.6.1 The Alice–Bob game
Alice and Bob are planning an evening together. Alice first decides whether they should stay home (\(a\)) or go out (\(b\)). If they stay home, Bob chooses between an action film (\(c\)) and cooking together (\(d\)). If they go out, Bob chooses a quiet cafe (\(e\)) or live music (\(f\)). In the latter case, Alice has the final choice between a rock club (\(g\)) and a jazz club (\(h\)). The terminal numbers are preference scores rather than monetary rewards.
Alice moves first. Bob observes her action and then moves at one of two decision nodes. If the history \(bf\) occurs, Alice moves again. Every player observes the complete preceding history, so the game has perfect information.
1.6.2 Strategies as complete contingent plans
A strategy prescribes an action at every decision point where the player might move, including decision points that will not be reached when that strategy is played. Therefore the strategy sets are
\[ S_A=\{ag,ah,bg,bh\}, \qquad S_B=\{ce,cf,de,df\}. \]
For example, \(ah\) instructs Alice to choose \(a\) initially and \(h\) if \(bf\) were reached. The second instruction is off the realized path when Alice chooses \(a\), but it remains part of her strategy because a strategy must be a complete plan.
1.6.3 Constructing the normal form
To convert this game into the normal form, combine one complete plan for Alice with one complete plan for Bob, follow the path induced in Figure 1.1, and place the terminal payoff in the corresponding cell:
\[ \begin{array}{c|cccc} & ce & cf & de & df \\ \hline ag & 0, 4 & 0, 4 & 2, 1 & 2, 1 \\ ah & 0, 4 & 0, 4 & 2, 1 & 2, 1 \\ bg & 1, 2 & 3, 8 & 1, 2 & 3, 8 \\ bh & 1, 2 & 8, 0 & 1, 2 & 8, 0 \end{array} \]
Three cells illustrate the procedure:
- \((ag,df)\) induces \(a\to d\) and payoff \((2,1)\);
- \((bh,cf)\) induces \(b\to f\to h\) and payoff \((8,0)\);
- \((bh,ce)\) induces \(b\to e\) and payoff \((1,2)\).
Repeated entries are not mistakes. Under \(ag\), for instance, Alice chooses \(a\) immediately, so her instruction \(g\) can never be reached, while Bob’s instruction after \(b\) is off the path for that profile. Both remain because a strategy is a complete contingent plan. Some off-path instructions affect play against other strategies; others, such as the difference between \(ag\) and \(ah\), produce outcome-equivalent strategies and disappear only in a reduced normal form.
The normal-form game retains the utilities associated with every profile of complete plans, but it does not display which actions occur first, what is observed, or which instructions lie off the realized path. Different extensive-form games can consequently have the same normal form.
1.6.4 Nash equilibrium and sequential reasoning
Marking best responses in the matrix gives the unique pure-strategy Nash equilibrium
\[ (bh,ce). \]
It induces the path \(b\to e\) and payoff \((1,2)\). The same outcome follows from solving the tree from its terminal decisions by backward induction:
- after \(bf\), Alice chooses \(h\) because \(8>3\);
- after \(b\), Bob chooses \(e\) because \(2>0\);
- after \(a\), Bob chooses \(c\) because \(4>1\);
- at the root, Alice chooses \(b\) because \(1>0\).
Thus Alice proposes going out, but Bob chooses the cafe. Although both would prefer the rock-club outcome \((3,8)\) to the cafe outcome \((1,2)\), Alice would switch to her preferred jazz club once given the final choice. Bob anticipates that choice and avoids live music. The story illustrates how the inability to commit to a later action can rule out an outcome that both players prefer.