Compositional game theory
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 Xi of choices (possible actions).
- We define Σ as the Cartesian product of all Xi, 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 di. The selection function takes as input a context, which is a function from Xi to R; and returns a set of best-responses, which is a subset of Xi.
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.
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: