What is Glossary of Game theory? : Abaara fun facts and uncommon knowledge

eLeaP eLearning Management Systems LMS LCMS Systems. Online training made easy. Free trial now.

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: $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 too -
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} \in \mathrm{N}$ .

Condorcet winner: Given a preference ν on the outcom 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.

See also:
| Game theory |

< Back

Categories: Game theory