Glossary of game theory

Game theory is the branch of mathematics in which games are studied: that is, models describing human behaviour. This is a glossary of some terms of the subject.

Contents

1 Definitions of a Game

1.1 Notational conventions
1.2 Normal form game
1.3 Extensive form game
1.4 Simple game

2 Glossary

Definitions of a Game

Notational conventions

Real numbers: $\mathbb{R}$ .
The set of players: $N$ .
Strategy space: $\Sigma\ = \prod_{i \in \mathrm{N}} \Sigma\ ^i$ . Where:
Player i's strategy space: $\Sigma\ ^i$ is the space of all possible ways in which player i can play the game.
A strategy for player i

$( \sigma\ )_i$ is an element of $\Sigma\$ .

complements

$( \sigma\ )_{ -i }$ an element of $\Sigma\ ^{-i} = \prod_{ j \in \mathrm{N}, j \ne i} \Sigma\ ^j$ , is a tuple of strategies for all players other than i.

Outcome Space: $\Gamma\$ is in most textbooks identical to -
Payoffs: $\mathbb{R} ^ \mathrm{N}$ , describing how much gain (money, pleasure, etc.) the players are allocated by the end of the game.

Normal form game

A game in normal form is a function:

$\pi\ : \prod_{i\in \mathrm{N}} \Sigma\ ^ i \to \mathbb{R}^\mathrm{N}$

Given the tuple of strategies chosen by the players, one is given an allocation of payments (given as real numbers).

A further generalization can be achieved by splitting the game into a composition of two functions:

$\pi\ : \prod_{i \in \mathrm{N}} \Sigma\ ^i \to \Gamma\$

the outcome function of the game (some authors call this function "the game form"), and:

$\nu\ : \Gamma\ \to \mathbb{R}^\mathrm{N}$

the allocation of payoffs (or preferences) to players, for each outcome of the game.

Extensive form game

This is given by a tree, where at each vertex of the tree a different player has the choice of choosing an edge.

Simple game

A Simple game is a couple (N, W), where W is a list of "winning" coalitions of members of N. A simple game is a special form of cooperative zero-sum game.

Glossary

Acceptable game: is a game form such that it has pure nash equilibria, all of which are pareto efficient, under all preference profiles.

Allocation of goods: is a function $\nu\ : \Gamma\ \to \mathbb{R} ^\mathrm{N}$ . Formally this is the same as a preference profile, this is interpreted as describing how much goods (e.g. money) the players are granted under the different outcomes of the game.

Best reply: the best reply to a given complement $\sigma\ _{-i}$ is a strategy $\tau\ _i$ that maximizes player i's payment. Formally, we want:
$\forall \sigma\ _i \in\ \Sigma\ ^i \quad \quad \pi\ (\sigma\ _i ,\sigma\ _{-i} ) \le \pi\ (\tau\ _i ,\sigma\ _{-i} )$ .

Coalition: is any subset of the set of players: $\mathrm{S} \subseteq \mathrm{N}$ .

Condorcet winner: Given a preference ν on the outcome space, an outcome a is a condorcet winner if all non-dummy players prefer a to all other outcomes.

Dominated outcome: Given a preference ν on the outcome space, we say that an outcome a is dominated by outcome b if it is preffered by some player, but no vise versa. Formally:
$\forall j \in \mathrm{N} \; \quad \nu\ _j (a) \le\ \nu\ _j (b)$ , and
$\exists i \in \mathrm{N} \; s.t. \; \nu\ _i (a) < \nu\ _i (b)$ .

An outcome a is dominated if it is dominated by some other outcome. An outcome a is dominated for a coalition S if all players in S prefer some other outcome to a. See also Condorcet winner.

Dominated strategy: we say that strategy $\sigma\ _i$ is (strongly) dominated by strategy $\tau\ _i$ if for any complement $\sigma\ _{-i}$ , player i benefits by playing $\tau\ _i$ . Formally speaking:
$\forall \sigma\ _{-i} \in\ \Sigma\ ^{-i} \quad \quad \pi\ (\sigma\ _i ,\sigma\ _{-i} ) \le \pi\ (\tau\ _i ,\sigma\ _{-i} )$ and
$\exists \sigma\ _{-i} \in\ \Sigma\ ^{-i} \quad s.t. \quad \pi\ (\sigma\ _i ,\sigma\ _{-i} ) < \pi\ (\tau\ _i ,\sigma\ _{-i} )$ .

A strategy σ is dominated if it is dominated by some other strategy.

Dummy: A player i is a dummy if he has no effect on the outcome of the game. I.e. if the outcome of the game is insensitive to player i's strategy.

Acronyms: say, veto.

Effectiveness: A coalition (or a single player) S is effective for a if it can force a to be the outcome of the game. S is α-effective if the members of S have strategies s.t. no matter what the complement of S does, the outcome will be a.

S is β-effective if for any strategis of the complement of S, the members of S can answer with strategies that ensure outcome a.

Finite game: is a game with finitely many players, each of which has a finite set of strategies.

Mixed strategy: for player i is a probability distribution P on $\Sigma\ ^i$ . It is understood that player i chooses a strategy randomly according to P.

Mixed Nash Equilibrium: Same as Pure Nash Equilibrium, defined on the space of mixed strategis. Every finite game has Mixed Nash Equilibria.

Pareto efficiency: An outcome a of game form π is (strongly) pareto efficient if it is undominated under all prefference profiles.

Preference profile: is a function $\nu\ : \Gamma\ \to \mathbb{R} ^\mathrm{N}$ . Formally this is the same as an allocation of goods, this is interpreted as describing how 'pleased' the players are with the possible outcomes of the game.

Pure Nash Equilibrium: An element $\sigma\ = (\sigma\ ) _ {i \in \mathrm{N}}$ of the strategy space of a game is a pure nash equilibrium point if no player i can benefit by deviating from his strategy $(\sigma\ )_i$ , given that the other players are playing in $\sigma\$ . Formally:
$\forall i \in \mathrm{N} \quad \forall \tau\ _i \in\ \Sigma\ ^i \quad \pi\ (\tau\ ,\sigma\ _{-i} ) \le \pi\ (\sigma\ )$ .
No equilibrium point is dominated.

Say: A player i has a Say if he is not a Dummy, i.e. if there is some tuple of complement strategies s.t. π (σ_i) is not a constant function.

Acromyn: Dummy.

Value: A value of a game is a rationally expected outcome. There are more than a few definitions of value, describing different meathods of obtaining a solution to the game.

Veto: A veto denotes the ability (or right) of some player to prevent a specific alternative from being the outcome of the game. A player who has that ability is called a veto player.

Acronym: Dummy.

Weakly acceptable game: is a game that has pure nash equilibria some of which is pareto efficient.

Zero sum game: is a game in which the allocation is constant over different outcomes. Formally:
$\forall \gamma\ \in \Gamma\ \sum_{i \in \mathrm{N}} \nu\ _i (\gamma\ ) = const.$
w.l.g. we can assume that constant to be zero. In a zero sum game one player's gain is onother player's loss. Most classical board games (e.g. chess, checkers) are zero sum.