# Compositional game theory

Compositional game theory is a branch of game theory and computer science, which aims to present large complex games as a composition of simple small games.

## Motivation

A major theme in computer science is the ability to construct simple building-blocks (e.g. functions or procedures in a programming language), and compose them into larger structures (e.g. more complex functions or programs). This principle is also called modularity.
In contrast, in classic game 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.

## Higher-order game

A higher-order simultaneous game is a generalization of a Simultaneous game in which players are defined by selection functions rather than by utility functions. Formally, a higher-order simultaneous game for n players contains the following elements:
* A set R of outcomes.
* For each player i, a set X$_i$ of choices (possible actions).
** We define Σ as the Cartesian product of all X$_i$, and call it the set of strategy profiles.
* An outcome function, from Σ to R. This function determines, for each combination of actions of the players, what the outcome will be.
* For each player i, there is a selection function denoted d$_i$. The selection function takes as input a context, which is a function from X$_i$ to R; and returns a set of best-responses, which is a subset of X$_i$.
The term "higher-order" comes from the latter element. The best-response correspondence of each player is a higher-order function, as is input is itself a function. Every strategy-profile s$_1$ in Σ, defines for each player i a function from X$_i$ to R: the function maps each possible action x$_i$ in X$_i$ to the outcome that would result if all players except i play as in s$_1$, whereas player i switches his action to x$_i$. In other words, s$_1$ defines the context in which player i operates.
Given two strategy-tuples s$_1$ and s$_2$ in Σ, we say that s$_2$ is a best-response to s$_1$ if, for each player i, s$_{2,i}$ is contained in the output of d$_i$ on the context generated by s$_1$. The best-response relation is a binary relation contained in Σ x Σ, denoted by B.
In a standard game, instead of the selection function, there is a utility function u$_i$ for each player i. A utility function takes as input an outcome from R, and returns a real number. Such a game can be represented as a higher-order game as follows. For each player i, the selection function returns the set of actions from X$_i$ that maximize the utility of agent i, given the context.

## Open games

The main object of study in CGT is the open game. An open game has the following elements:
* A set X of observations;
* A set Y of outcomes;
* A set Σ of strategy profiles.
* A play function P, which is a function from Σ x X to Y;
* A coplay function C, which is a function from Σ x X x R to S;
* A best-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:
* In sequence - yielding a sequential game;
* In parallel - yielding a simultaneous game.