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₁ 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₁, whereas player i switches his action to x_i. In other words, s₁ defines the context in which player i operates.

Given two strategy-tuples s₁ and s₂ in Σ, we say that s₂ is a best-response to s₁ if, for each player i, s_2,i is contained in the output of d_i on the context generated by s₁. 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.

See also

• Bayesian open games.

External links

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