Glossary of game theory

El directorio enciclopédico desde la Wikipedia.

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.

[edit] Definitions of a game

[edit] 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\ ^i$ .

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.

[edit] Normal form game

A game in normal form is a function:

$. === Extensive form game === <math> \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}$ .

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 </math>
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 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 $\tau\ _i$ if for any complement strategies tuple $\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 (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.

v • d • e Topics in game theory

Definitions	Normal-form game · Extensive-form game · Cooperative game · Information set · Preference

Equilibrium concepts	Nash equilibrium · Subgame perfection · Bayesian-Nash · Perfect Bayesian · Trembling hand · Proper equilibrium · Epsilon-equilibrium · Correlated equilibrium · Sequential equilibrium · Quasi-perfect equilibrium · Evolutionarily stable strategy · Risk dominance · Pareto efficiency

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

Classes of games	Symmetric game · Perfect information · Dynamic game · Sequential game · Repeated game · Signaling game · Cheap talk · Zero-sum game · Mechanism design · Bargaining problem · Stochastic game · Nontransitive game · Global games

Games	Prisoner's dilemma · Traveler's dilemma · Coordination game · Chicken · Volunteer's dilemma · Dollar auction · Battle of the sexes · Stag hunt · Matching pennies · Ultimatum game · Minority 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 · Signaling game · Trust game · Princess and monster game

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

Página espejo de la Wikipedia

Directorio de Enlaces Directorio dmoz Directorio espejo dmoz Pedro Bernardo