Normal-form game
A normal-form game, also known as a strategic-form game, is a fundamental representation in game theory that models strategic interactions among a finite set of players who simultaneously select actions from their respective strategy sets, with outcomes and payoffs determined by the resulting strategy profile.[1] Formally, it is defined as a tuple \Gamma = (N, (S_i)_{i \in N}, (u_i)_{i \in N}), where N is the set of players, S_i is the strategy set for each player i, and u_i: \prod_{i \in N} S_i \to \mathbb{R} is the payoff (or utility) function for player i, mapping each strategy profile to a real-valued payoff reflecting preferences over outcomes.[2] This structure assumes complete information, simultaneous moves, and rational players seeking to maximize their expected payoffs, often represented in matrix form for two-player games to visualize strategy combinations and associated payoffs.[1] The concept originated with John von Neumann's 1928 work on the minimax theorem for zero-sum games and was rigorously formalized in his 1944 collaboration with Oskar Morgenstern in Theory of Games and Economic Behavior, which established the foundations of noncooperative game theory by introducing von Neumann-Morgenstern utility functions to handle cardinal preferences via lotteries over outcomes.[3] Unlike the extensive-form representation, which captures sequential moves and information sets via game trees, the normal form abstracts away timing and focuses on strategic interdependence, making it suitable for analyzing static, one-shot interactions.[1] Key solution concepts in normal-form games include Nash equilibrium, where no player benefits from unilaterally deviating given others' strategies, and dominated strategies, which can be eliminated to simplify analysis.[4] Normal-form games are pivotal for studying phenomena like cooperation and conflict in diverse fields, including economics (e.g., Cournot oligopoly models for quantity competition), biology (e.g., evolutionary stable strategies), and engineering (e.g., resource allocation in energy markets).[2] Classic examples include the Prisoner's Dilemma, illustrating tension between individual and collective rationality, and zero-sum games like matching pennies, where one player's gain equals another's loss.[3] While finite games with pure strategies guarantee at least one mixed-strategy Nash equilibrium by Nash's 1951 theorem, the form's limitations—such as ignoring dynamics or incomplete information—have spurred extensions like Bayesian games.[4]Introduction
Definition
A normal-form game, also known as a strategic-form game, is a core model in game theory that describes strategic interactions among a set of rational players who select actions simultaneously, without observing others' choices, to determine outcomes based on payoffs. This representation captures static decision-making under interdependence, where each player's payoff depends on the collective strategy profile chosen by all participants.[5] Key characteristics of a normal-form game include complete information, where all players possess full knowledge of the game structure, including available strategies and payoff mappings; strategy sets that may be finite or infinite, accommodating discrete or continuous choices; and a non-cooperative setting, in which players act independently to maximize their individual utilities without enforceable commitments. These features distinguish normal-form games from dynamic models like extensive-form games, which incorporate sequential moves and information revelation.[1] Unlike cooperative games, which allow for binding agreements and coalition formation to achieve joint outcomes, normal-form games emphasize individual rationality and potential self-interested conflicts, precluding enforceable side payments or contracts. The foundational framework was established by John von Neumann and Oskar Morgenstern, who formalized it as a tool for analyzing economic and strategic behavior. In standard notation, a normal-form game involves n players, indexed by i = 1 to n, each with a strategy set S_i denoting the possible actions available to player i. Payoff functions then assign real-valued utilities to each combination of strategies across all players.[2]Historical Context
The concept of the normal-form game traces its origins to early 20th-century efforts to formalize strategic decision-making in mathematics. In 1921, French mathematician Émile Borel introduced ideas related to the minimax theorem in the context of games like poker, laying preliminary groundwork for analyzing strategic interactions through probabilistic strategies, though without a fully rigorous proof.[6] This work anticipated the structured representation of player choices and outcomes but remained focused on specific game types. John von Neumann advanced these ideas significantly in his 1928 paper "Zur Theorie der Gesellschaftsspiele," where he proved the minimax theorem for two-person zero-sum games and introduced the normal form as a matrix-based representation of strategies and payoffs, establishing a foundational framework for game theory.[7] Building on this, von Neumann collaborated with economist Oskar Morgenstern to publish "Theory of Games and Economic Behavior" in 1944, which expanded the normal-form approach to broader economic contexts, incorporating utility theory and demonstrating its applicability beyond pure zero-sum scenarios.[8] Following World War II, the normal-form game gained prominence in operations research and economics, driven by wartime applications in strategic planning and postwar efforts to model economic competition and resource allocation.[9] In 1950 and 1951, John Nash extended the framework to non-zero-sum games through his development of the Nash equilibrium concept, which identified stable strategy profiles in normal-form representations where no player benefits from unilateral deviation.[10] Later refinements, such as those by Jean-François Mertens in the 1980s, addressed stability issues in these equilibria, providing criteria for strategically robust outcomes in normal-form games.Components and Formulation
Players and Strategies
In a normal-form game, the players form a finite set of rational decision-makers, typically denoted by N = \{1, 2, \dots, n\}, where each player seeks to maximize their own payoff given the actions of others.[11] This setup assumes simultaneous decision-making without binding commitments, distinguishing it from extensive-form representations.[8] Each player i \in N has a set of pure strategies S_i, consisting of all possible complete plans of action available to them in the game.[12] A pure strategy specifies a definite choice for player i, such as selecting a specific move without randomization. The collection of pure strategies across all players forms the strategy space S = \prod_{i \in N} S_i, and a strategy profile s = (s_1, \dots, s_n) represents a specific combination where s_i \in S_i for each i.[11] To capture uncertainty or imperfect information, players may employ mixed strategies, which are probability distributions over their pure strategies. For player i, a mixed strategy \sigma_i: S_i \to [0,1] assigns probabilities such that \sum_{s_i \in S_i} \sigma_i(s_i) = 1, allowing randomization across actions.[13] A mixed strategy profile is then \sigma = (\sigma_1, \dots, \sigma_n), where each \sigma_i is independent of the others, enabling analysis of equilibria that may not exist in pure strategies alone.[10] Normal-form games often feature finite strategy spaces, particularly discrete choices, as in rock-paper-scissors, where each player's S_i = \{\text{rock}, \text{paper}, \text{scissors}\}, yielding |S| = 3^n possible pure strategy profiles for n players.[12] However, strategy spaces can be infinite, such as compact intervals like [0,1] in the tragedy of the commons, where players choose extraction levels continuously, or unbounded sets like [0, \infty) in Cournot competition, where firms select output quantities.[11][14] Finite cases guarantee the existence of mixed-strategy Nash equilibria, while infinite spaces require additional compactness or continuity assumptions for similar results.[10]Payoff Functions
In a normal-form game, the payoff function for each player i \in N (where N is the set of players) is denoted u_i: S \to \mathbb{R}, which assigns a real-valued utility to every strategy profile s = (s_1, \dots, s_n) \in S (the Cartesian product of all players' strategy sets).[1] This function quantifies the outcome of the game from player i's perspective, capturing preferences over possible results.[15] Payoff functions are typically interpreted through von Neumann-Morgenstern (vNM) utility theory, which provides a cardinal representation of preferences under uncertainty. Unlike ordinal utilities, which only rank outcomes without measuring intensity, vNM utilities are unique up to positive affine transformations and enable the computation of expected utilities for lotteries or mixed strategies.[11] For a mixed strategy profile \sigma = (\sigma_1, \dots, \sigma_n), where each \sigma_j is a probability distribution over player j's strategies, player i's expected payoff is given by E[u_i(\sigma)] = \sum_{s \in S} \left[ \prod_{j \in N} \sigma_j(s_j) \right] u_i(s). This formulation arises from the vNM axioms of completeness, transitivity, continuity, and independence, ensuring that rational agents maximize expected utility. Games are classified as zero-sum if the sum of payoffs across all players is zero for every strategy profile, i.e., \sum_{i \in N} u_i(s) = 0 for all s \in S, implying pure conflict where one player's gain equals another's loss. In contrast, non-zero-sum games allow for variable total payoffs, enabling cooperation or mutual benefit, as the sum \sum_{i \in N} u_i(s) can differ across profiles.[1] Standard normal-form game analysis assumes common knowledge of all payoff functions, meaning every player knows the payoffs, knows that others know them, and so on ad infinitum.[16] Additionally, players are assumed rational, seeking to maximize their expected payoffs given beliefs about others' actions.[17] These assumptions underpin the strategic evaluation of outcomes in normal-form games.[11]Representations
Matrix Representation
The matrix representation, often called the bimatrix form, is a tabular method used to visualize normal-form games involving exactly two players with finite strategy sets. In this format, the rows represent the pure strategies available to player 1, while the columns represent those of player 2. Each entry in the resulting matrix consists of an ordered pair (u_1(s_1, s_2), u_2(s_1, s_2)), where u_1 and u_2 denote the payoffs to player 1 and player 2, respectively, for the joint strategy profile (s_1, s_2).[18][1] Consider a simple case where player 1 has strategies labeled A and B, and player 2 has strategies X and Y. The bimatrix takes the following structure:| X | Y | |
|---|---|---|
| A | (a_1, b_1) | (a_2, b_2) |
| B | (a_3, b_3) | (a_4, b_4) |
Strategic Form Tuple
The strategic form provides a compact mathematical representation of a normal-form game, encapsulating its essential elements in tuple notation. Formally, a normal-form game in strategic form is defined as the tuple \Gamma = (N, (S_i)_{i \in N}, (u_i)_{i \in N}), where N is a finite set of players, S_i denotes the strategy set available to player i \in N, and u_i: S \to \mathbb{R} is the payoff function assigning a real-valued payoff to each strategy profile s = (s_i)_{i \in N} \in S = \prod_{i \in N} S_i for player i. This formulation, introduced in the foundational work on noncooperative games, allows for arbitrary finite or infinite strategy sets and any number of players n = |N|, providing a general framework beyond the two-player case. To incorporate uncertainty and randomization, the strategic form extends to mixed strategies via the tuple \Gamma_m = (N, (\Sigma_i)_{i \in N}, (U_i)_{i \in N}), where \Sigma_i = \Delta(S_i) is the set of mixed strategies for player i, consisting of all probability distributions over the pure strategies in S_i, and U_i: \Sigma \to \mathbb{R} is the expected utility function defined as U_i(\sigma) = \mathbb{E}_{s \sim \sigma} [u_i(s)] for a mixed strategy profile \sigma = (\sigma_i)_{i \in N} \in \Sigma = \prod_{i \in N} \Sigma_i, where the expectation is taken with respect to the product distribution induced by \sigma (reducing to a summation for finite S).[12] This extension preserves the structure of the original game while enabling analysis of equilibria involving randomization, as mixed strategies induce expected payoffs linear in the probabilities. The pure strategy game \Gamma and its mixed extension \Gamma_m are isomorphic in the sense that pure strategies correspond to degenerate mixed strategies (Dirac distributions on singletons in S_i), ensuring that solution concepts like Nash equilibrium defined on \Gamma_m restrict appropriately to pure strategy profiles in \Gamma. This isomorphism underscores the generality of the tuple notation, which contrasts with matrix representations limited to finite two-player games by facilitating theoretical extensions to broader classes of interactions.[21]Examples
Prisoner's Dilemma
The Prisoner's Dilemma is a foundational example in normal-form game theory, originally formulated by RAND Corporation researchers Merrill Flood and Melvin Dresher in 1950 to explore non-cooperative decision-making, and later named by mathematician Albert Tucker to evoke a criminal interrogation scenario.[22] In this setup, two suspects are arrested for a crime and held in isolation, unable to communicate. Each must independently choose whether to remain silent (cooperate with the other prisoner by not betraying them) or confess (defect by implicating the partner). The outcomes depend on their joint choices, with payoffs measured in years of prison time (lower values are preferable, often converted to utilities where higher numbers indicate better outcomes, such as reduced sentence length).[22] The standard payoff structure assigns the following prison sentences: if both remain silent, each serves 1 year; if one confesses while the other remains silent, the confessor goes free (0 years) and the silent one serves 3 years; if both confess, each serves 2 years.[22] Represented as a normal-form payoff matrix with utilities (negative values for years served, higher utility better), the game for Player 1 (rows) and Player 2 (columns) is:| Player 2 \ Player 1 | Silent (Cooperate) | Confess (Defect) |
|---|---|---|
| Silent (Cooperate) | -1, -1 | -3, 0 |
| Confess (Defect) | 0, -3 | -2, -2 |
Coordination Game
A coordination game is a type of normal-form game in which players' interests align such that they all benefit from selecting the same strategy, with the primary challenge being to achieve mutual alignment without communication.[24] Unlike games of pure conflict, coordination games feature payoffs that reward synchronization, often resulting in multiple stable outcomes where deviation by any player reduces everyone's welfare. A classic example of a pure coordination game involves two drivers approaching each other on a narrow road, each deciding simultaneously whether to swerve left or right to avoid collision. If both choose the same direction, they pass safely with high payoffs; if they choose differently, they collide with low payoffs. The symmetric payoff matrix for this game, where payoffs represent utilities (higher for success, lower for failure), is as follows:| Driver 1 \ Driver 2 | Left | Right |
|---|---|---|
| Left | 1, 1 | 0, 0 |
| Right | 0, 0 | 1, 1 |
| Husband \ Wife | Opera | Fight |
|---|---|---|
| Opera | 2, 1 | 0, 0 |
| Fight | 0, 0 | 1, 2 |
Solution Concepts
Dominated Strategies
A strategy s_i for player i in a normal-form game strictly dominates another strategy t_i if it yields a payoff u_i(s_i, s_{-i}) \geq u_i(t_i, s_{-i}) for every strategy profile s_{-i} of the opponents, with strict inequality holding for at least one such profile. This condition implies that no rational player would ever choose the dominated strategy t_i, as the dominating strategy s_i is always at least as good and sometimes better, regardless of others' actions. Weak dominance relaxes the strict inequality requirement, allowing equality in all cases but still prohibiting the weakly dominated strategy under common knowledge of rationality. The iterated elimination of strictly dominated strategies (IESDS) is a procedure that successively removes strictly dominated strategies from the game, updating the strategy sets after each round until no further eliminations are possible. This stepwise reduction simplifies the game while preserving the set of rationalizable outcomes, as each elimination step reflects the belief that rational players avoid inferior choices. In finite games, IESDS is order-independent, meaning the final reduced game is unique regardless of the sequence of eliminations. Rationalizability refers to the solution concept obtained as the limit of infinite iterations of strict dominance elimination in finite normal-form games, capturing all strategy profiles consistent with common knowledge of rationality among players.[25] Introduced independently by Bernheim and Pearce, rationalizable strategies form a refinement that eliminates implausible choices beyond what a single round of dominance might achieve, though it may not yield a unique outcome.[26] To illustrate, consider the following generic 2x2 normal-form game with players Row and Column, each having strategies A/B and X/Y, respectively:| X | Y | |
|---|---|---|
| A | 3, 0 | 2, 1 |
| B | 1, 2 | 0, 3 |
| X | Y | |
|---|---|---|
| A | 3, 0 | 2, 1 |
Nash Equilibrium
In a normal-form game, a Nash equilibrium is a strategy profile \sigma^* where no player can improve their expected payoff by unilaterally changing their strategy, assuming the other players' strategies remain fixed. Formally, \sigma^* is a Nash equilibrium if, for every player i, \sigma_i^* is a best response to \sigma_{-i}^*, i.e., u_i(\sigma_i^*, \sigma_{-i}^*) \geq u_i(s_i, \sigma_{-i}^*) for all pure strategies s_i \in S_i, and every pure strategy with positive probability under \sigma_i^* achieves this maximum payoff.[27] John Nash proved the existence of at least one Nash equilibrium (possibly mixed) for every finite normal-form game with a finite number of players and actions, relying on Brouwer's fixed-point theorem applied to a continuous best-response correspondence over the simplex of mixed strategies.[27] This result holds even for games without pure-strategy equilibria, such as matching pennies, where players must randomize to prevent exploitation.[27] A pure-strategy Nash equilibrium occurs when each player assigns probability 1 to a single pure strategy in the profile, satisfying the best-response condition deterministically; in contrast, a mixed-strategy Nash equilibrium involves players randomizing over multiple pure strategies with positive probability.[27] While pure equilibria are simpler to interpret, mixed ones are necessary for equilibrium in games with inherent conflict, and Nash's theorem guarantees their existence in finite games.[27] To compute Nash equilibria, methods like best-response dynamics iteratively update each player's strategy to their current best response against the others' strategies, potentially converging to a pure equilibrium in potential games or under certain conditions, though cycles can occur in general.[28] This approach highlights the equilibrium's role as a steady state of such adjustment processes. Nash equilibria possess stability against unilateral deviations by construction, making them robust to individual perturbations in non-cooperative settings.[27] However, they are not necessarily Pareto efficient, as outcomes may exist where all players are better off; for instance, in the Prisoner's Dilemma, the unique Nash equilibrium of mutual defection is Pareto dominated by mutual cooperation.[29]Relation to Extensive-Form Games
Conversion Between Forms
The normal form of an extensive-form game is obtained by defining each player's strategy as a complete contingent plan that specifies an action for every information set controlled by that player, with payoffs calculated as the expected values derived from the outcomes of all possible strategy profiles leading to terminal histories.[30] This reduction process transforms the sequential structure into a simultaneous-move representation, where the strategy set for each player consists of all such behavioral plans.[1] In extensive-form games with imperfect information, information sets partition the decision nodes into groups where the player cannot distinguish between histories; strategies must therefore assign the same action to all nodes within each information set, which expands the normal-form strategy space relative to the extensive form's sequential choices and can lead to exponentially larger matrices.[30] For instance, in games where a player observes partial signals, the contingent plans must cover all possible realizations consistent with the information set, ensuring consistency across indistinguishable paths. While the normal form fully captures the set of possible outcomes and expected payoffs from any strategy profile in the extensive form, it discards the temporal ordering of moves and subgame structure, potentially obscuring refinements like subgame perfection that rely on sequential rationality.[30] Nash equilibria in this induced normal form identify strategy profiles that are stable under simultaneous play but may include non-credible threats when interpreted sequentially.[31] A classic illustration is the entry deterrence game, where the potential entrant moves first to Enter or Stay Out; if Enter, the incumbent then chooses Accommodate (yielding duopoly payoffs of 15 for each) or Fight (yielding -1 for each), while Stay Out gives the entrant 0 and the incumbent monopoly profit of 35.[31] Converting to normal form yields the following payoff matrix, with the entrant's strategies as rows and the incumbent's contingent plans as columns:| Entrant \ Incumbent | Accommodate | Fight |
|---|---|---|
| Enter | 15, 15 | -1, -1 |
| Stay Out | 0, 35 | 0, 35 |