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.[1] [2] [3]
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.
A higher-order simultaneous game[4] 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:
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 s1 in Σ, defines for each player i a function from Xi to R: the function maps each possible action xi in Xi to the outcome that would result if all players except i play as in s1, whereas player i switches his action to xi. In other words, s1 defines the context in which player i operates.
Given two strategy-tuples s1 and s2 in Σ, we say that s2 is a best-response to s1 if, for each player i, s2,i is contained in the output of di on the context generated by s1. 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 ui 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 Xi that maximize the utility of agent i, given the context.
The main object of study in CGT is the open game. An open game has the following elements:
It is an abstraction of a higher-order game.
Open games can be decomposed in two ways: