Complete information
Fundamentals
Definition
In game theory, a game of complete information is one in which all players possess full knowledge of the game's structure, including the set of players, the strategies available to each player, and the payoff functions determining outcomes for every possible combination of strategies.[7] This setup assumes no private information exists regarding these elements, allowing players to base their decisions solely on the known rules and consequences.[2] A defining characteristic of complete information games is the assumption of common knowledge: not only does every player know the game's structure, but each player knows that all others know it, knows that others know that they know it, and so on infinitely.[7] This recursive mutual awareness eliminates uncertainty about the game's parameters, simplifying theoretical analysis by enabling the application of rational choice models without additional layers of belief formation about others' information.[8] The Prisoner's Dilemma serves as a canonical example of a static game under complete information, where two suspects must independently decide whether to confess or remain silent, with publicly known payoff matrices reflecting years of imprisonment based on their choices—such as mutual silence yielding the shortest sentences and mutual confession the longest.[7] Formally, such a game is represented as a tuple $ G = (N, (S_i){i \in N}, (u_i){i \in N}) $, where $ N $ is the finite set of players, $ S_i $ is the strategy set for player $ i $, and $ u_i: \prod_{j \in N} S_j \to \mathbb{R} $ is the payoff function for player $ i $.[7]Historical development
Early foundations trace back to Ernst Zermelo's 1913 proof of the determinacy of chess, demonstrating optimal play in a perfect information game.[7] The foundations of the complete information concept in game theory emerged in the early 20th century amid efforts to formalize strategic decision-making in zero-sum games, where players possess full knowledge of payoffs, strategies, and rules. Émile Borel laid initial groundwork in his 1921 paper "La théorie du jeu et les équations intégrales à noyau symétrique," introducing the minimax theorem as a solution for such games and implicitly assuming complete information as the baseline for rational play.[9] This work built on probability theory to address bluffing and mixed strategies, as exemplified in games like poker (which involve incomplete information), marking the first systematic mathematical treatment of interactive decisions in zero-sum games assuming complete knowledge of the structure.[10] John von Neumann advanced these ideas significantly in his 1928 paper "Zur Theorie der Gesellschaftsspiele," proving the minimax theorem for two-person zero-sum games and solidifying complete information as a core assumption, ensuring the existence of optimal mixed strategies.[11] Von Neumann also pioneered the extensive form representation in the 1920s, depicting games as decision trees to capture sequential moves while maintaining the complete information framework.[12] Post-World War II, von Neumann collaborated with Oskar Morgenstern on their seminal 1944 book Theory of Games and Economic Behavior, which extended the theory to broader economic applications, formalizing normal forms and emphasizing complete information for non-zero-sum scenarios.[13] John Nash further revolutionized the field with his 1950 paper on bargaining games and 1951 paper "Non-Cooperative Games," introducing Nash equilibria for finite non-cooperative games under complete information, shifting focus from zero-sum to general-sum interactions.[14] Refinements to normal forms in the 1950s, including Nash's existence theorem and Harold Kuhn's work on extensive games, enhanced the analytical tools for these settings.[15] Key milestones in the 1970s refined the informational assumptions underpinning complete information games. Robert Aumann's 1976 paper "Agreeing to Disagree" formalized common knowledge—a mutual understanding of all game elements shared infinitely among players—as essential for complete information equilibria, proving that rational agents with identical priors cannot hold differing beliefs under such conditions.[16] This concept delineated the boundaries of complete information by highlighting its reliance on recursive mutual awareness. Concurrently, John Harsanyi's 1967–1968 trilogy "Games with Incomplete Information Played by 'Bayesian' Players" transformed incomplete information games into complete but imperfect ones via type spaces and Bayesian updating, underscoring complete information as the idealized counterpart and influencing subsequent modeling.[17] From the 1960s to 1970s, game theory transitioned from pure mathematics to economic modeling, with complete information serving as the standard for analyzing markets and institutions, as seen in works by economists like Reinhard Selten on sequential rationality.[18] Post-2003 developments integrated complete information into computational game theory, emphasizing scalable algorithms for equilibrium computation in complex environments.[19] A prominent example is DeepMind's AlphaGo in 2016, which mastered the complete (and perfect) information game of Go using Monte Carlo tree search and deep neural networks, demonstrating practical advancements in solving vast strategy spaces under full transparency.[20]Information Structures
Complete versus incomplete information
In game theory, incomplete information arises in strategic interactions where players do not possess full knowledge of other players' payoffs, types (such as private valuations or costs), or intended strategies.[21] This contrasts with complete information games, where the entire payoff structure and all relevant parameters are common knowledge among participants.[22] Incomplete information is typically modeled using Bayesian games, a framework developed by John Harsanyi, in which each player's type is drawn from a known probability distribution, and players form beliefs about others' types based on prior information.[21] The structural differences between complete and incomplete information games fundamentally alter equilibrium analysis. In complete information settings, players select pure or mixed strategies directly, enabling the computation of Nash equilibria through best-response mappings without uncertainty over opponents' incentives.[22] Incomplete information, however, introduces type-dependent strategies, where actions are functions of private types, and players must incorporate beliefs over type spaces to evaluate expected payoffs. This leads to Bayesian Nash equilibrium, in which strategies are optimal given beliefs, and beliefs are consistent with the common prior via Bayes' rule wherever possible.[21] As a result, incomplete information expands the strategy space and requires handling uncertainty, often complicating the identification of equilibria compared to the deterministic structure of complete information games.[22] These differences have profound analytical implications, particularly in increasing the complexity of solving for stable outcomes. Complete information games permit straightforward equilibrium calculations using fixed-point theorems on strategy profiles, but incomplete information demands evaluating interim expected payoffs—conditional on a player's own type—which involves integrating over beliefs about others' types and actions.[22] This added layer of uncertainty can lead to phenomena like adverse selection in markets, where asymmetric knowledge about quality causes high-value participants to withdraw, resulting in inefficient equilibria dominated by lower-quality options.[23] For example, in a first-price sealed-bid auction under independent private values, bidders submit simultaneous bids without observing rivals' private valuations, forcing reliance on Bayesian updating and shading bids below true values to balance winning probability and payment, which exemplifies the heightened strategic opacity of incomplete information.[24] By comparison, an English (ascending-bid) auction reveals bidding behavior publicly as the process unfolds, allowing participants to infer others' valuations more directly and approaching complete information dynamics, though initial private values still introduce some uncertainty.[24] The distinction between complete and incomplete information has driven key extensions in economic modeling, bridging classical game theory to real-world applications with hidden attributes. George Akerlof's 1970 model of the "market for lemons" demonstrates how sellers' superior knowledge of product quality leads to adverse selection and potential market collapse under incomplete information, highlighting inefficiencies absent in complete settings.[23] Similarly, Michael Spence's 1973 signaling framework shows how agents with private types can use costly actions, like education in job markets, to credibly convey information and mitigate incompleteness, fostering separating equilibria where types are distinguished.[25] These contributions underscore how incomplete information refines the analysis of incentives and outcomes beyond the assumptions of complete knowledge.Complete versus perfect information
In game theory, perfect information refers to a property of extensive-form games where, at every decision point, each player has full knowledge of the entire history of all previous moves made by themselves and all other players. This condition implies no simultaneous moves and no hidden actions, ensuring that information sets in the game tree consist of single nodes.[26][27] The concepts of complete and perfect information are orthogonal, meaning a game can exhibit one without the other along independent dimensions: completeness concerns common knowledge of the game's structure and payoffs, while perfection addresses observability of move histories. For instance, a game may have complete information yet imperfect information, such as Rock-Paper-Scissors, where payoffs are fully known but players move simultaneously without observing each other's choices. Conversely, a game can have perfect information but incomplete information, as in an English auction, where all bids (moves) are publicly observed in sequence, but private valuations (affecting payoffs) remain unknown to others.[26][28] These distinctions carry significant implications for game analysis. Perfect information facilitates the use of backward induction, allowing players to solve the game by reasoning recursively from terminal nodes, which often yields pure-strategy subgame perfect equilibria in finite games. Complete information, by contrast, ensures that payoff functions are common knowledge, enabling standard equilibrium analysis without Bayesian updating over types, irrespective of whether moves are observable. An example of a game with both complete and perfect information is chess, where all moves are visible and payoffs (win/loss/draw) are fixed and known.[27][29] The term "perfect information" was formalized by Harold W. Kuhn in his 1953 work on extensive-form games, where he refined the representation to incorporate information sets and perfect recall, distinguishing it from earlier sequential analyses like Zermelo's 1913 treatment of chess.Formal Representations
Normal form
In game theory, the normal form, also known as the strategic form, provides a compact representation of games under complete information where players select strategies simultaneously, without observing others' choices. It is defined as a tuple $ G = (N, (S_i){i \in N}, (u_i){i \in N}) $, where $ N $ is the finite set of players, $ S_i $ denotes the finite strategy set available to player $ i $, and $ u_i: S \to \mathbb{R} $ is the von Neumann-Morgenstern utility (payoff) function for player $ i $, with $ S = \prod_{i \in N} S_i $ representing all possible strategy profiles.[7] This structure assumes complete information, meaning every player knows the full game specification, including all strategy sets and payoff functions, which facilitates analysis of interdependent decision-making.[7] For two-player games, the normal form is typically depicted as a payoff matrix, with rows corresponding to one player's strategies, columns to the other's, and each cell containing a payoff vector $ (u_1(s_1, s_2), u_2(s_1, s_2)) $ that encodes the outcomes for the chosen strategy pair. This matrix format directly captures simultaneous-move interactions, a hallmark of complete information settings, by treating each player's strategy as a complete plan that accounts for all possible responses from others, thereby enabling best-response calculations where a player optimizes given fixed strategies of opponents.[7] Under complete information, the transparency of strategies and payoffs supports rigorous equilibrium analysis, as players can anticipate mutual best responses without uncertainty about the game's rules.[7] A classic example is the Prisoner's Dilemma, a two-player game illustrating dominant strategies in normal form. Consider two suspects interrogated separately, each choosing to Cooperate (remain silent) or Defect (confess and implicate the other). The payoff matrix, with payoffs representing years in prison (lower is better, negated for utility), is:| Player 2 \ Player 1 | Cooperate | Defect |
|---|---|---|
| Cooperate | (-1, -1) | (-3, 0) |
| Defect | (0, -3) | (-2, -2) |
Extensive form
In the extensive form, sequential games of complete information are represented as a game tree that explicitly models sequential decision-making. The tree consists of nodes, which are points where a player makes a decision or the game reaches a terminal payoff; branches emanating from non-terminal nodes, each representing a possible action available to the player at that node; and terminal nodes, where payoffs are assigned to each player based on the path taken to reach them.[31] This structure captures the order of moves, contingencies, and outcomes in dynamic interactions.[32] For perfect information—a subset of complete information where there are no simultaneous moves or chance elements—the extensive form uses singleton information sets at every decision node, meaning players observe all prior actions in the history leading to the current node, with no uncertainty about the game's past state.[6] This setup assumes perfect recall, where each player remembers all previous actions they have taken and all observations they have made throughout the game.[32] Strategies in this representation are complete contingent plans, defined as functions that map every possible history—an ordered sequence of actions leading to a decision node—for a player to a specific action from the available set at that node.[31] Subgames arise naturally from the tree structure, each defined by a non-terminal node and comprising that node along with all its descendants, allowing isolated analysis of subsequent play while preserving the original rules and payoffs.[6] The extensive form's advantages lie in its ability to incorporate timing, sequential contingencies, and observable histories, which reveal strategic nuances absent in static representations like the normal form.[31] For instance, it facilitates the refinement of equilibria by highlighting credible commitments or threats based on the game's unfolding structure. A representative example is the Centipede game, a finite tree where two players alternate decisions to "take" a growing pot of money or "pass" it to the opponent, with payoffs increasing for cooperation but tempting defection at each step—such as Player 1 facing (1,0) for taking immediately versus passing to a branch where Player 2 chooses between (0,2) and further continuation to (3,1) or (2,4), ultimately unraveling via backward induction to predict early termination despite mutual gains from passing.[33]Equilibrium Concepts
Nash equilibrium
In non-cooperative games with complete information, the Nash equilibrium serves as the foundational solution concept, identifying strategy profiles where no player can improve their payoff by unilaterally changing their strategy while others remain fixed.[34] Formally, consider a game with a finite set of players , each with a strategy set and utility function , where is the joint strategy space. A strategy profile is a Nash equilibrium if, for every player and every alternative strategy ,
This condition ensures mutual best responses among players.[34]
Nash established the existence of at least one Nash equilibrium (possibly in mixed strategies) for any finite game using a fixed-point argument based on Brouwer's fixed-point theorem, mapping the strategy space to best-response correspondences and showing that any fixed point corresponds to an equilibrium.[34] In complete information settings, equilibria can be computed via best-response dynamics, an iterative process where players sequentially adjust to best-respond to the current profile of others' strategies; in certain classes of games, such as potential games, this process converges to a pure Nash equilibrium.[35]
Nash equilibria may be pure, where players select deterministic strategies satisfying the best-response condition, or mixed, involving probability distributions over strategies. Pure equilibria exist if the game has dominant strategies or if strict dominance eliminates non-equilibrium profiles, but many games lack pure equilibria; for instance, in the Matching Pennies game—where Player 1 wins by matching Player 2's head/tail choice and Player 2 wins by mismatching—the unique Nash equilibrium is mixed, with each player randomizing equally over their actions to make the opponent indifferent.[36]
A canonical example is the Prisoner's Dilemma, a two-player game where each has actions Cooperate (C) or Defect (D), with payoffs structured such that mutual cooperation yields (3,3), mutual defection (1,1), and mixed outcomes favor the defector (0,5 for one defecting against cooperation, and vice versa). To find equilibria, check best responses: if Player 2 cooperates, Player 1's best response is to defect (5 > 3); if Player 2 defects, Player 1's best response is to defect (1 > 0). By symmetry, the same holds for Player 2. Thus, (D,D) is the unique Nash equilibrium, as neither player benefits from unilateral deviation.[36]
Despite its robustness, the Nash equilibrium has limitations in complete information games: it may select inefficient outcomes, as in the Prisoner's Dilemma where (D,D) is Pareto-dominated by (C,C), and it disregards sequential structure in dynamic games, prompting refinements like subgame perfect equilibrium for extensive-form representations.[36]
Subgame perfect equilibrium
In extensive-form games with complete information, a subgame perfect equilibrium (SPE) is defined as a strategy profile that forms a Nash equilibrium in every subgame induced by the non-terminal nodes of the game tree. This refinement ensures sequential rationality, meaning players make optimal decisions not only in the overall game but also in every possible continuation from any decision point. The concept was introduced by Reinhard Selten to eliminate Nash equilibria supported by non-credible off-path behaviors.[37] The primary method to compute an SPE is backward induction, which proceeds by starting at the terminal nodes of the game tree and working upwards to the root, selecting optimal actions at each non-terminal node given the anticipated responses in subsequent subgames. At each step, a player chooses the action that maximizes their payoff, assuming all future play follows the equilibrium strategies. This process guarantees that the resulting strategy profile is sequentially rational throughout the game.[38] A representative example is the Stackelberg leader-follower duopoly model under complete information, where the leader commits to an output level first, and the follower responds optimally. Consider a simplified discrete version with zero marginal costs and inverse demand $ P = 24 - Q $, where $ Q = q_L + q_F $. The leader chooses output $ q_L $ (6 or 9 units), observed by the follower, who then chooses $ q_F $ (7 or 10 units). The payoffs are as follows:| Leader's Choice | Follower's Choice | Leader's Payoff | Follower's Payoff |
|---|---|---|---|
| 6 | 7 | 66 | 77 |
| 6 | 10 | 48 | 80 |
| 9 | 7 | 72 | 56 |
| 9 | 10 | 45 | 50 |