Compositional game theory is a branch ofgame theory andcomputer science, which aims to present large complex games as a composition of simple small games.^[1][2][3]

A major theme incomputer science is the ability to construct simple building-blocks (e.g. functions or procedures in aprogramming language), and compose them into larger structures (e.g. more complex functions or programs). This principle is also calledmodularity.

In contrast, in classicgame theory, even complex games are treated as single, monolithic objects. This makes the analysis of games hard to scale.

Compositional game theory(CGT) aims to apply the modularity principle to game theory. The main motivation is to make it easier to analyze large games using software tools.

Ahigher-order simultaneous game^[4] is a generalization of aSimultaneous game in which players are defined byselection functions rather than byutility functions. Formally, a higher-order simultaneous game forn players contains the following elements:

• A set R ofoutcomes.
• For each playeri, a setX_i ofchoices (possible actions).
  • We defineΣ as the Cartesian product of allX_i, and call it the set ofstrategy profiles.
• Anoutcome function, fromΣ toR. This function determines, for each combination of actions of the players, what the outcome will be.
• For each playeri, there is aselection function denotedd_i. The selection function takes as input acontext, which is a function fromX_i toR; and returns a set ofbest-responses, which is a subset ofX_i.

The term "higher-order" comes from the latter element. The best-response correspondence of each player is ahigher-order function, as is input is itself a function. Every strategy-profile s₁ inΣ, defines for each playeri a function fromX_i toR: the function maps each possible actionx_i inX_i to the outcome that would result if all players except i play as in s₁, whereas playeri switches his action tox_i. In other words, s₁ defines thecontext in which playeri operates.

Given two strategy-tuples s₁ and s₂ inΣ, we say that s₂ is abest-response to s₁ if, for each playeri, s_2,i is contained in the output ofd_i on the context generated by s₁. Thebest-response relation is abinary relation contained inΣ x Σ, denoted byB.

In a standard game, instead of the selection function, there is autility functionu_i for each playeri. A utility function takes as input an outcome fromR, and returns areal number. Such a game can be represented as a higher-order game as follows. For each playeri, the selection function returns the set of actions fromX_i that maximize the utility of agenti, given the context.

The main object of study in CGT is theopen game. An open game has the following elements:

• A setX ofobservations;
• A setY ofoutcomes;
• A setΣ ofstrategy profiles.
• Aplay functionP, which is a function fromΣ xX toY;
• Acoplay functionC, which is a function fromΣ x X x R to S;
• Abest-response function B, which is a function from X x (Y -> R) to a relation inΣ x Σ.

It is an abstraction of a higher-order game.

Open games can be decomposed in two ways:^[2]

• In sequence - yielding asequential game;
• In parallel - yielding asimultaneous game.

• Bayesian open games.^[5]

• Open game engine -Haskell code for constructing and analyzing open games.

• Game theory
• Category theory

• Articles with short description
• Short description matches Wikidata