Glossary of Game Theory

Glossary

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:
$\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: .

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.

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).
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:
$\forall j \in \mathrm{N} \; \quad \nu\ _j (a) \le\ \nu\ _j (b)$ for domination, and
$\exists i \in \mathrm{N} \; s.t. \; \nu\ _i (a) < \nu\ _i (b)$ 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:
$\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 (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:
$\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.

Antonym: Dummy.

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:
$\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 another player's loss. Most classical board games (e.g. chess, checkers) are zero sum.

Topics in game theory

Definitions	Normal-form game Extensive-form game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian-Nash Perfect Bayesian Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Cheap talk Zero–sum game Mechanism design Bargaining problem Stochastic game Large poisson game Nontransitive game Global games

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Cake cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Screening game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key Figures	Kenneth Arrow Robert Aumann Kenneth Binmore Samuel Bowles Melvin Dresher Merrill M. Flood Drew Fudenberg Donald B. Gillies John Harsanyi Leonid Hurwicz David K. Levine Daniel Kahneman Harold W. Kuhn Eric Maskin Jean-François Mertens Paul Milgrom Oskar Morgenstern Roger Myerson John Nash John von Neumann Ariel Rubinstein Thomas Schelling Reinhard Selten Herbert Simon Lloyd Shapley John Maynard Smith Jean Tirole Albert W. Tucker William Vickrey Robert B. Wilson Peyton Young

See also	Tragedy of the commons Tyranny of small decisions All-pay auction List of games in game theory Confrontation Analysis

Read more about this topic: Glossary Of Game Theory

Glossary of Game Theory - Glossary