# Glossary of game theory

From Wikipedia the free encyclopedia

This article needs additional citations for verification. (December 2009) (Learn how and when to remove this template message) |

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[edit]

### Notational conventions[edit]

- Real numbers
- .
- The set of
**players** - .
- Strategy space
- , where
- Player i's strategy space
- is the space of all possible ways in which player
**i**can play the game. - A strategy for player
**i**

is an element of .

- Complements

an element of , is a tuple of strategies for all players other than **i**.

- Outcome space
- is in most textbooks identical to -
- Payoffs
- , describing how much gain (money, pleasure, etc.) the players are allocated by the end of the game.

### Normal form game[edit]

A game in normal form is a function:

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:

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

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

### Extensive form game[edit]

This is given by a tree, where at each vertex of the *tree* a different player has the choice of choosing an edge. The *outcome* set of an extensive form game is usually the set of tree leaves.

### Cooperative game[edit]

A game in which players are allowed to form coalitions (and to enforce coalitionary discipline). A cooperative game is given by stating a *value* for every coalition:

It is always assumed that the empty coalition gains nil. *Solution concepts* for cooperative games usually assume that the players are forming the *grand coalition* , whose value is then divided among the players to give an allocation.

### Simple game[edit]

A Simple game is a simplified form of a cooperative game, where the possible gain is assumed to be either '0' or '1'. A simple game is couple (**N**, **W**), where **W** is the list of "winning" **coalitions**, capable of gaining the loot ('1'), and **N** is the set of players.

## Glossary[edit]

- Acceptable game
- is a
**game form**such that for every possible**preference profiles**, the game has**pure nash equilibria**, all of which are**pareto efficient**.

- Allocation of goods
- is a function . The allocation is a
**cardinal**approach for determining the good (e.g. money) the players are granted under the different outcomes of the game.

- Best reply
- the best reply to a given complement is a strategy that maximizes player
**i'**s payment. Formally, we want:

.

- Coalition
- is any subset of the set of players: .

- 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.

- Decidability
- In relation to game theory, refers to the question of the existence of an algorithm that can and will return an answer as to whether a game can be solved or not.
^{[1]}

- Determinacy
- A subfield of set theory that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Games studied in set theory are Gale–Stewart games – two-player games of perfect information in which the players make an infinite sequence of moves and there are no draws.

- Determined game (or
**Strictly determined game**) - In game theory, a strictly determined game is a two-player zero-sum game that has at least one Nash equilibrium with both players using pure strategies.
^{[2]}^{[3]}

- Dictator
- A player is a
*strong dictator*if he can guarantee any outcome regardless of the other players. is a*weak dictator*if he can guarantee any outcome, but his strategies for doing so might depend on the complement strategy vector. Naturally, every strong dictator is a weak dictator. Formally:

*m*is a*Strong dictator*if:

*m*is a*Weak dictator*if:

- Another way to put it is:
- a
*weak dictator*is -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*).

- a
- Also see
*Effectiveness*. Antonym:*dummy*.

- Dominated outcome
- Given a
**preference***ν*on the**outcome space**, we say that an outcome**a**is dominated by outcome**b**(hence,**b**is the*dominant*strategy) if it is preferred by all players. If, in addition, some player strictly prefers**b**over**a**, then we say that**a**is**strictly dominated**. Formally:

for domination, and

for strict domination.

An 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 if for any complement strategies tuple , player
*i*benefits by playing . Formally speaking:

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 game. I.e. if the outcome of the game is insensitive to player**i'**s strategy. - Antonyms:
*say*,*veto*,*dictator*.

- 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 strategies 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**.

- 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 . 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
**outcome***a*of**game form***π*is (strongly)**pareto efficient**if it is**undominated**under all**preference profiles**.

- Preference profile
- is a function . This is the
**ordinal**approach at describing the outcome of the game. The preference describes how 'pleased' the players are with the possible outcomes of the game. See**allocation of goods**.

- Pure Nash Equilibrium
- An element of the strategy space of a game is a
*pure nash equilibrium point*if no player**i**can benefit by deviating from his strategy , given that the other players are playing in . Formally:

.

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. - Antonym:
*Dummy*.

- Shannon number
- A conservative lower bound of the game-tree complexity of chess (10
^{120}).

- Solved game
- A game whose outcome (win, lose or draw) can be correctly predicted assuming perfect play from all players.

- Value
- A
**value**of a game is a rationally 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 different
**outcomes**. Formally:

w.l.g. we can assume that constant to be zero. In a zero-sum game, one player's gain is another player's loss. Most classical board games (e.g. chess, checkers) are**zero sum**.

## References[edit]

**^**Mathoverflow.net/Decidability-of-chess-on-an-infinite-board Decidability-of-chess-on-an-infinite-board**^**Saul Stahl (1999). "Solutions of zero-sum games".*A gentle introduction to game theory*. AMS Bookstore. p. 54. ISBN 9780821813393.**^**Abraham M. Glicksman (2001). "Elementary aspects of the theory of games".*An Introduction to Linear Programming and the Theory of Games*. Courier Dover Publications. p. 94. ISBN 9780486417103.