In game theory, two players interact by each selecting an element from a semigroup, with one receiving a payoff given by a bounded function mapping the product of choices into the interval from negative one to one. When the semigroup satisfies amenability conditions, classical strategies consisting of countably additive probability measures extend naturally to include certain finitely additive measures, yielding a well-defined game value together with optimal strategies for both participants; any preexisting classical solution remains optimal under this extension. Four-strategy settings further illustrate that evolutionary dynamics equations produce analytical cycle structures whose quantitative features match both agent-based learning simulations and laboratory experiments with human subjects, confirming that non-Euclidean superplane cycles are observable and controllable. In applied two-player sports, history-dependent strategy profiles can be analyzed in real time to identify responses that maximize win probability against a given opponent sequence. Reinforcement-learning agents paired with neuroevolution of augmenting topologies have been shown to sustain indefinite play in continuous two-dimensional environments by learning distinctions between rewarding passages and collision penalties. These constructions collectively isolate the core elements of players, admissible strategy sets, and resulting payoffs while demonstrating how extensions and empirical checks preserve solution concepts across abstract and practical domains.
Simultaneous-move games receive their standard representation through the normal-form tuple consisting of a player set N, strategy sets S_i for each player, and payoff functions u_i that map every strategy profile to a real number for that player. For any finite two-player instance the structure appears as a payoff matrix whose rows index the first player’s strategies, columns index the second player’s strategies, and each cell records the ordered pair of resulting payoffs. Because choices occur at the same instant, the matrix encodes no temporal sequence; it simply enumerates every feasible combination and the associated utilities. When the number of players exceeds two the same tuple definition continues to apply, although the payoff array becomes multidimensional and is typically enumerated rather than drawn. Each cell therefore corresponds to exactly one strategy profile, allowing direct inspection of best responses and equilibrium candidates without reference to any extensive-form tree. The supplied description of the normal-form tuple and its matrix visualization is taken verbatim from the web-research block on simultaneous-move representation; none of the listed arXiv papers supplies this definitional material.
Dominant strategies arise only in special structures where one action for a player yields a strictly or weakly higher payoff against every possible combination of opponents' choices. In the Prisoner's Dilemma each player possesses a unique strictly dominant strategy to defect. No general theorem guarantees their presence, and many games including coordination problems and matching pennies lack them for at least one participant. When they exist for all players the resulting profile is the unique dominant-strategy equilibrium. Iterated elimination of dominated strategies begins with the full game and successively removes any strategy that is strictly or weakly dominated within the current strategy sets, producing a sequence of reduced games. For finite games this process is well-defined and can be driven by communication among rational agents, yielding an epistemic justification that the surviving profiles are consistent with common knowledge of rationality. Extensions to well-founded extensive games with perfect information allow transfinite elimination and show that games with injective payoffs reduce to the unique subgame-perfect equilibrium; the same framework solves strictly competitive games with n outcomes in at most n-1 steps. These procedures therefore refine Nash equilibrium by discarding strategies that rational players would never employ.
Nash equilibrium is a strategy profile in a strategic-form game such that for every player i no unilateral change of strategy raises that player’s payoff given the strategies chosen by the others. Formally, with finite players, strategy sets S_i and payoff functions u_i, a profile s* satisfies u_i(s_i*, s_{-i}*) ≥ u_i(s_i, s_{-i}*) for all alternative s_i. This condition is equivalent to each player’s strategy being a best response to the profile of the remaining players. John Nash proved in 1950–1951 that every finite game possesses at least one Nash equilibrium once mixed strategies are admitted; the argument applies Kakutani’s fixed-point theorem to the best-response correspondence defined on the mixed-strategy simplex. The same theorem guarantees existence when each strategy set is nonempty, compact and convex and each payoff is continuous and quasi-concave in the player’s own strategy. When compactness or continuity fails, equilibria need not exist. The cited papers on inapproximability of approximate equilibria, variational reformulations with non-ordered preferences, and quantum bit-error-rate bounds all presuppose the existence result for finite or suitably regular games and derive their hardness or security statements from it.
Mixed strategies extend pure-strategy Nash equilibria by enlarging each player’s feasible choices from a discrete set of actions to the full simplex of probability distributions over those actions. A pure strategy then becomes the special case in which one action receives probability one and all others receive zero. The Nash definition itself remains unchanged: a profile of mixed strategies is an equilibrium when each player’s mixture is a best response to the others. Because the strategy space is now convex, every finite normal-form game possesses at least one Nash equilibrium, even when no pure-strategy equilibrium exists. Computation of an equilibrium mixture rests on an indifference property: in any mixed-strategy equilibrium a player assigns positive probability only to pure strategies that deliver identical expected payoffs against the opponents’ mixtures; otherwise the player would deviate to the strictly better action. Consequently, the equilibrium probabilities of one player are found by solving the system of equations that render the opponent indifferent among every pure strategy in the opponent’s support, together with the normalization constraints that the probabilities sum to one. In the elementary two-by-two case this produces a pair of linear equations whose unique solution yields the equilibrium mixing rates. The same indifference logic scales directly to larger finite games once the support of each mixture is identified.
Sequential games receive their formal structure in extensive form by encoding timing, choices, information, and payoffs inside a rooted directed graph known as a game tree. The root represents the initial node; non-terminal nodes mark decision points assigned to a specific player or to Nature for chance events; and terminal nodes carry n-tuples of payoffs that conclude every path. Branches leaving each non-terminal node are labeled with the feasible actions available to the player who moves there. A history is the ordered sequence of actions reaching any node, while a complete play is any full path from root to a terminal leaf. Information sets partition a player’s nodes to capture what that player knows at the moment of choice; singleton sets define perfect information, whereas larger sets force the same action across indistinguishable nodes. When Nature moves, fixed probability distributions govern its branches. This explicit ordering of nodes along paths permits systematic examination of sequential interaction, including the first mover’s opening choice and every subsequent response that follows observed actions in perfect-information settings. The resulting description therefore comprises the player set, the assignment of moves, action availability, knowledge partitions, chance probabilities where present, and payoffs attached to every terminal outcome.
In extensive-form games a strategy profile constitutes a subgame-perfect equilibrium precisely when its restriction to every subgame is itself a Nash equilibrium of that subgame, a requirement that forces every continuation strategy to be a mutual best response from any reachable node. Because any threat whose prescribed action is not optimal at the node where it would have to be carried out fails the Nash test inside the corresponding subgame, the equilibrium condition automatically discards strategy profiles sustained by non-credible threats. Existence of such equilibria is guaranteed for multiplayer quantitative reachability games on finite graphs and, in the two-player case, for the stronger notion of subgame-perfect secure equilibrium; an algorithm further decides existence of ordinary secure equilibria when more than two players are present. When payoffs lie in the Hausdorff difference hierarchy, subgame-perfect equilibria exist exactly for linear preferences that contain no infinite ascending chains and satisfy the pairwise acyclicity condition that forbids any triple of outcomes x, y, z and players a, b such that z <_a y <_a x together with x <_b z <_b y. In continuous-time stopping problems a strong equilibrium, defined to match the subgame-perfect requirement more closely than earlier mild or weak notions, is always attained by an optimal mild equilibrium whenever the state is a continuous-time Markov chain and the discount function is log sub-additive. The further refinement to subgame-credible Nash equilibrium adds an external-credibility filter: whenever a player’s continuation strategy differs across equivalent subgames, her own continuation payoff must not fall, thereby eliminating self-harming punishments while retaining existence in every multi-stage game.
Repeated games expand equilibrium possibilities beyond one-shot stage games by letting players condition future play on observed history, enabling credible threats and rewards that sustain cooperation even when defection dominates statically. arXiv 2411.12725v2 establishes a Folk Theorem-style characterization for general repeated games under finite recall and varied monitoring, proving that Q-learning, projected gradient, replicator, and log-barrier dynamics can converge to a wide set of payoff vectors that include collusive outcomes. In contrast, arXiv 1402.2801v2 shows an anti-Folk Theorem result: when signals satisfy (ε,γ)-differential privacy with ε and γ small, any equilibrium of the repeated game reduces to approximate stage-game equilibria for fixed discount factors, and this collapse occurs naturally in large n-player games where unilateral deviations have limited impact. arXiv 2507.10148v1 proves that a Folk Theorem holds in indefinitely repeated network games with local imperfect monitoring and local communication precisely when the network is 2-connected, yielding perfect Bayesian equilibria that support cooperative payoffs. arXiv 1203.6553v1 extends related long-run convergence ideas through turnpike theorems for finite-horizon zero-sum Markov games on Borel spaces, showing optimal strategies and state distributions approach stationary solutions. These results together delineate when repetition sustains cooperation and when monitoring or scale constraints prevent it.
Games with private information are formalized as Bayesian games by adding a type for each player that represents that player’s private information, together with a common prior over all type profiles and payoff functions that depend on both actions and types. Each player knows her own type but not the others’, so a strategy is a type-contingent rule mapping from types to actions, and equilibrium is defined in terms of expected payoffs computed from the conditional beliefs induced by the common prior and Bayes’ rule. In the standard formulation a Bayesian game specifies a set of players, an action set for each player, a type set for each player, a joint prior distribution over type profiles, and utilities over action profiles and type profiles. This captures private information by treating it as uncertainty about types rather than as a separate game form. The key modeling assumption is that what is not common knowledge concerns only payoffs and utilities, while the player set and action sets remain common knowledge. Operationally the game is analyzed from different informational stages: ex ante, where no player knows any types so payoffs are evaluated under the prior; interim, where each player knows her own type and uses the posterior over others’ types; and ex post, where all types are known so payoffs are realized directly. Finding an approximate Bayesian Nash equilibrium is PPAD-complete even for a two-player incomplete-information game with a constant number of actions, as shown by reduction from the inapproximability of Nash equilibrium in polymatrix degree-3 graphical games.
Signaling games capture how an informed sender with private type information transmits it credibly to an uninformed receiver through observable actions whose costs vary by type. When education costs less for high-productivity workers, only they obtain it in equilibrium, allowing employers to update beliefs and offer wages that separate types. In the model of Fudenberg and He, agents additionally know opponents’ payoff functions and rationality, believe opponents avoid conditionally dominated strategies, and update beliefs from personal observations against random opponents. Patient young senders’ experimentation then depends on which receiver responses they consider plausible. The limiting long-run outcomes are bounded above by rationality-compatible equilibria that refine the Intuitive Criterion of Cho and Kreps and contain all divine equilibria of Banks and Sobel; they are bounded below by uniform RCE, which sometimes exist and imply universally divine equilibrium. Payoff knowledge can therefore both tighten and expand the set of learning predictions relative to models lacking such information.
Install this pack and your MIND begins smart — then every answer is grounded in your own knowledge graph.
Try MIND free →