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.

Definitions of a game

Notational conventions

; Real numbers : $mathbb\{R\}$.; The set of players : $mathrm\{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\; ^i$.; complements : $sigma\; \_\{-i\}$ an element of $Sigma\; ^\{-i\}\; =\; prod\_\{\; j\; in\; mathrm\{N\},\; j\; e\; 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::$.$

Extensive form game

$sigma\; \_\{-i\}$ is a strategy $au\; \_i$ that maximizes player i's payment. Formally, we want:
$forall\; sigma\; \_i\; in\; Sigma\; ^i\; quad\; quadpi\; (sigma\; \_i\; ,sigma\; \_\{-i\}\; )\; le\; pi\; (\; au\; \_i\; ,sigma\; \_\{-i\}\; )$.

; Coalition : is any subset of the set of players: $mathrm\{S\}\; subseteq\; mathrm\{N\}$.players. $m\; in\; mathbb\{N\}$ is a "weak dictator" if he can guarantee any outcome, but his strategies for doing so might depend on the complement > forall a in mathrm{A}, ; forall sigma _{-n} in Sigma ^{-n} ; exist sigma _n in Sigma ^n ; s.t. ; Gamma (sigma _{-n},sigma _n) = a
Another way to put it is:
a "weak dictator" is $alpha$-effective for every possible outcome.
A "strong dictator" is -effective for every possible outcome.
A game can have no more than one "strong dictator". Some games have multiple "weak dictators" (in "rock-paper-scissors" both players are "weak dictators" but none is a "strong dictator").
See "Effectiveness". Antonym: "dummy".

; Dominated outcome : Given a preference "ν" on the outcome space, we say that an outcome a is dominated by outcome a is (strictly) dominated if it is (strictly) 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 is (strongly) dominated by strategy $au\; \_i$ if for any complement strategies tuple $sigma\; \_\{-i\}$, player "i" benefits by playing $au\; \_i$. Formally speaking:
$forall\; sigma\; \_\{-i\}\; in\; Sigma\; ^\{-i\}\; quad\; quadpi\; (sigma\; \_i\; ,sigma\; \_\{-i\}\; )\; le\; pi\; (\; au\; \_i\; ,sigma\; \_\{-i\}\; )$ and
.
A strategy σ is (strictly) dominated if it is (strictly) dominated by some other strategy.

; Dummy : A player i is a dummy if he has no effect on the outcome of the 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.

; Grand coalition : refers to the coalition containing all players. In cooperative games it is often assumed that the grand coalition forms and the purpose of the game is to find stable imputations.

; 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 strategies. Every finite game has Mixed Nash Equilibria.

; Pareto efficiency : An the possible outcomes of the game. See allocation of goods.

; Pure Nash Equilibrium : An element $sigma\; =\; (sigma\; \_i)\; \_\; \{i\; in\; mathrm\{N$ of the strategy space of a game is a "pure expected outcome. There are more than a few definitions of value, describing different methods 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.Antonym: "Dummy".

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

; Zero sum game : is a game in which the allocation is constant over one player's gain is another player's loss. Most classical board games (e.g. chess, checkers) are zero sum.