Source-linked AI summary
Compositional game theory
Neil Ghani, Jules Hedges, Viktor Winschel, Philipp Zahn
TL;DR
Compositional game theory seeks to build complex games from components even though a composite game’s equilibria need not follow from those of its parts. The paper introduces open games with context-relative best responses and composition operators, showing how familiar equilibrium concepts are recovered while making games modular.
Problem
Compositional game theory must account for environments and interactions while defining larger games from component equilibria, although composite equilibria need not be determined by component equilibria.
Source: §I · p. 1Method
Open games represent strategic behavior through best responses relative to contexts and use composition operators to combine games.
Source: §I · p. 1, §III · p. 3Results
In the arg max case, open games recover standard best responses and Nash equilibria, and the paper presents a compositional theory that builds larger games from smaller elements.
Source: §II · p. 2, §IX · p. 9Takeaways & Limitations
The theory makes game models modular by constructing them from elements joined through parallel and sequential composition.
Source: §IX · p. 9The paper’s treatment covers simultaneous and sequential games, Nash equilibria, and pure strategies.
Source: §IX · p. 10
Abstract
from arXiv · showhide
We introduce open games as a compositional foundation of economic game theory. A compositional approach potentially allows methods of game theory and theoretical computer science to be applied to large-scale economic models for which standard economic tools are not practical. An open game represents a game played relative to an arbitrary environment and to this end we introduce the concept of coutility, which is the utility generated by an open game and returned to its environment. Open games are the morphisms of a symmetric monoidal category and can therefore be composed by categorical composition into sequential move games and by monoidal products into simultaneous move games. Open games can be represented by string diagrams which provide an intuitive but formal visualisation of the information flows. We show that a variety of games can be faithfully represented as open games in the sense of having the same Nash equilibria and off-equilibrium best responses.
I. INTRODUCTION
The paper brings compositionality to strategic games, where equilibria of a whole game need not follow from those of its parts. It introduces open games to represent interactions with environments and compose games sequentially and in parallel.
I. INTRODUCTION
- Compositional game theory builds large games from smaller components, but emergent behavior means component equilibria need not determine a composite game’s equilibria.The prisoner’s dilemma illustrates the issue: players individually prefer defection, while a single agent representing both would cooperate.Source: §I · p. 1
- Open games are morphisms in a symmetric monoidal category: monoidal products compose simultaneous interactions, while categorical composition joins games sharing a boundary sequentially.Closed systems are recovered as scalars.Source: §I · p. 1
- Open games model behavior relative to a simplified context that abstracts the future into one utility function, reducing a complex game to individual decisions.Composition operators handle the circularity of Nash equilibrium, where players are mutually best replies.Source: §I · p. 1
- The approach combines process-based games, compositional dynamics [2], and environment-relative selection functions and, which were not strongly compositional.Selection functions can model agents’ goals compositionally.Source: §I · p. 1
II. SELECTION FUNCTIONS AND HIGHER ORDER GAMES
The section uses selection functions to describe how agents choose in contexts, then extends that framework to simultaneous and sequential games. In the arg max case, its equilibria and best responses recover standard game-theoretic definitions.
II. SELECTION FUNCTIONS AND HIGHER ORDER GAMES
- A higher-order simultaneous game specifies players’ choices, outcomes, and selection functions that map each player’s utility context to its optimal moves.A context fixes the other players’ strategies and gives the utility associated with each unilateral deviation.Source: §II · p. 2
- In simultaneous games, selection equilibria and best responses match the usual pure-strategy Nash definitions; in the prisoner’s dilemma both players’ dominant strategy yields (D, D).The game’s best-response relation is constant across strategy profiles.Source: §II · p. 2
- In a higher-order sequential game, strategies condition moves on previous actions, and a play function produces the resulting move sequence.The framework defines selection equilibria through a best-response relation between strategy profiles.Source: §II · p. 2
- With arg max selection functions, higher-order sequential games agree with standard best responses and Nash equilibria, but are weaker than optimal strategies, which specialize to subgame perfect equilibrium.The cited optimal-strategy definition therefore imposes a stronger equilibrium concept.Source: §II · p. 2
III. OPEN GAMES
An open game packages strategies, play, coplay, and context-relative best responses. Its backward-flowing coutility and flexible contexts let games represent interactions with environments and support composition.
III. OPEN GAMES
- An open game is a four-tuple of strategy profiles, a play function, a coplay function, and a best-response function.The best-response function maps observations and continuations to relations on strategy profiles.Source: §III · p. 2
- Coutility is the value returned to the calling environment, with coplay computing how one game’s utility becomes another game’s input.The type of coutility need not be real-valued, monetary, or maximized.Source: §III · p. 3
- Open games extend beyond utility-maximizing agents: outcomes and coutility may be values other than real numbers, and utility need not be maximized.The paper notes this flexibility may be useful in modelling,.Source: §III · p. 3
- Best responses are defined relative to an arbitrary context containing the past state and a continuation describing the future, so these strategic representations can be composed.The composition operators account for mutual best replies in Nash equilibrium.Source: §III · p. 3
- The paper relates open games to lenses and geometry of interaction; the lens connection encapsulates algebraic structure while focusing attention on strategic behavior.In the cited GoI comparison, open games’ forward function does not use the backward input, so composition needs no trace operator.Source: §III · p. 3
IV. EXAMPLES OF OPEN GAMES
The section presents open games as compositions of decisions, functions, and counits, and shows that decision rules need not always maximize real-valued utility. These examples illustrate how atomic components represent choices and information flow.
IV. EXAMPLES OF OPEN GAMES
- A scalar open game has strategy profiles and a best-response relation; the prisoner’s dilemma is represented with profiles {C, D}2 and best response (D, D).Here, a scalar open game has type (1, 1) → (1, 1).Source: §IV · p. 4
- Open games can be built compositionally from atomic decisions, functions, and counits.A decision represents an agent’s single choice; a counit passes a forward value back as a value about which a past agent reasons.Source: §IV · p. 4
- A utility-maximizing decision is optimal when its strategy maps the current observation to a choice maximizing the continuation.The strategy for a single decision maps possible observations to possible choices.Source: §IV · p. 4
- Open-game decisions can use non-maximizing selection functions, a generality the authors argue is needed because an aggregate of maximizing agents need not itself maximize.The prisoner’s dilemma illustrates this: the two players acting as one entity would choose (C, C).Source: §IV · p. 4
V. THE MONOIDAL CATEGORY OF OPEN GAMES
Open games form a symmetric monoidal category through composition for sequential play and monoidal product for simultaneous play. Quotienting by an equivalence on games resolves the failure of composition to be associative on raw strategy profiles.
Composition operators
- Categorical composition models sequential play, while the monoidal product models simultaneous play.In the described sequential composition, the first component’s choice is visible to the second component but hidden from the outside.Source: §V · pp. 4–5
Quotient construction
- Composition is not associative on raw strategy profiles, so the paper quotients open games by an equivalence relation before forming a category.The relation uses a bijection between strategy profiles that preserves play, coplay, and best responses.Source: §V · p. 5
- The quotient identifies games with isomorphic strategy profiles and best responses, even when they represent games with different numbers of players.The paper gives the prisoner’s dilemma and a one-player game with four choices as an example; this is a technical consequence of the quotient and does not occur with a bicategory or double category.Source: §V · p. 5
Category structure
- Composition is well-defined on equivalence classes, and the resulting category Game has identity open games as its identity morphisms.The identity open game is strategically trivial.Source: §V · p. 5
Monoidal product
- The monoidal product is well-defined on equivalence classes and defines a bifunctor, completing the category’s monoidal structure.Its object-level product pairs the corresponding sets, and its symmetry is inherited from Set × Setop.Source: §V · pp. 5–6
Category structure
- Theorem 1 establishes Game as a symmetric monoidal category, with object product given by pairs of sets and monoidal unit (1, 1).Its morphisms are equivalence classes of open games.Source: §V · pp. 5–6
Lens-theoretic view
- A lens-based formulation expresses composite open games as families of lenses and simplifies how their play and coplay functions fit together.The composition’s strategy profiles are indexed by pairs of component strategies.Source: §V · p. 6
VI. STRING DIAGRAMS
String diagrams provide a visual language for open games, representing objects with oriented wires and composing atomic diagrams side-by-side or end-to-end. A coherence result makes the represented game invariant under allowed topological manipulations.
Coherence
- The diagram language extends that of symmetric monoidal categories, and a formal treatment proves a coherence theorem for defining open games by their diagrams.The account here is informal; the formal presentation is cited as [9].Source: §VI · pp. 6–7
Diagram syntax
- An open-game object can be represented by covariant and contravariant wires, with orientation encoding the duality between the two parts.The object (X, S) is represented as a tensor product of X and S*, up to isomorphism.Source: §VI · p. 6
- Atomic open games have corresponding diagrams, which are combined by end-to-end and side-by-side juxtaposition.Decision and function nodes represent their corresponding atomic games; diagram juxtaposition represents categorical composition and monoidal product.Source: §VI · pp. 6–7
Diagram rules
- The diagrams allow backwards-bending wires for counits, but not bends in the opposite direction because no natural strategically trivial open game exists for that direction.The coherence theorem states that the resulting game is invariant under topological manipulations, provided the diagram does not use an illegal bend.Source: §VI · p. 7
VII. SIMULTANEOUS MOVE GAMES
Simultaneous-move games can be built compositionally from player decisions while preserving their strategy profiles and best responses. The construction also extends to higher-order players and illustrates how different selection functions produce familiar game behaviors.
VII. SIMULTANEOUS MOVE GAMES
- The monoidal product of player decisions has the same strategy profiles and best-response relation as the corresponding simultaneous-move game, so its fixpoints are pure-strategy Nash equilibria.Source: §VII · p. 7
- By associativity, composing an m-player and an n-player open game with the monoidal product yields an (m + n)-player open game.Source: §VII · p. 7
- A scalar open game reproduces the simultaneous game’s best-response function, and its string diagram shows generated utility fed back to each agent via a counit.Source: §VII · pp. 7–8, Figure 1 · p. 8
- For arbitrary higher-order games, open games associated with selection functions have selection equilibria as best-response fixpoints; Figure 2 depicts players optimizing the other’s choice without requiring utility maximization.Source: §VII · p. 8, Figure 2 · p. 8
- With both players using Dfix, the construction gives a coordination game whose pure Nash equilibria are (A, A) and (B, B) when X = {A, B}.Source: §VII · p. 8
- Using the anti-fixpoint selection for both players gives an anti-coordination game with pure Nash equilibria (A, B) and (B, A) when X = {A, B}.Source: §VII · p. 8
- When one player coordinates and the other differentiates, the best responses match matching pennies, and the resulting game has no pure-strategy Nash equilibrium.Source: §VII · p. 8
VIII. SEQUENTIAL GAMES
Sequential games are built from open-game decisions that let later players observe earlier moves. The construction also represents hybrid games where an initial move is observed by players who then move simultaneously.
Sequential games
- The sequential-game construction focuses on finite perfect-information games where a different player chooses at each stage, with players and choice sets fixed by stage.Each player observes every previous move; relaxing these restrictions is possible but requires more work.Source: §VIII · p. 8
- A sequential decision duplicates the observed input X and passes one copy to a choice D_X,Y, so the decision can depend on X.The recursive construction starts from the identity game and extends each stage using the preceding game and a decision over the product of earlier choice sets.Source: §VIII · pp. 8–9
- The resulting game has strategy profiles and a best-response relation, with later choices represented as functions of observed earlier moves.For two players, the strategy profile is X × (X → Y).Source: §VIII · pp. 8–9
Hybrid sequential-simultaneous games
- Open games represent hybrid play by letting two players observe a first move, then choose simultaneously without observing each other’s choices.The paper illustrates this with a monopolist setting an input price followed by two competing firms choosing production.Source: §VIII · p. 9, Figure 6 · p. 9
- The hybrid representation is modular and is presented as more appropriate to the economic situation than its extensive-form imperfect-information representation.Source: §VIII · p. 9
IX. CONCLUSIONS AND FUTURE WORK
The paper presents open games as a modular way to build larger games from smaller components, and notes connections to lenses and geometry of interaction. Its initial scope is limited to simultaneous and sequential games, Nash equilibria, and pure strategies, with several extensions and computational tools left for future work.
Conclusions
- Open games construct larger games from smaller elements through parallel and sequential composition, making game theory modular.Source: §IX · p. 9
- The categorical tools for compositional games reveal connections to the theory of lenses and to geometry of interaction.Source: §IX · p. 10
Scope
- The paper’s initial scope covers simultaneous and sequential games, Nash equilibria, and pure strategies.Source: §IX · p. 10
Future work
- Repeated games, especially infinitely repeated games, require a refined equilibrium concept such as subgame perfect equilibria and more general composition operators.The paper points to initial results on modelling infinitely repeated games using final coalgebras of certain functors on open games.Source: §IX · p. 10
- Mixed strategies remain a difficult extension, and incomplete-information games are another direction for further study.The paper notes that mixed strategies require heavier category-theoretic tools and are work in progress.Source: §IX · p. 10
- The authors identify implementation and equilibrium computation as practical questions, and describe prototype tools for diagrams, compilation, simulation, and analysis.They suggest compositional structure might help combine numerical methods for solving economic models.Source: §IX · p. 10