Appendix:Glossary of game theory

From Wiktionary, the free dictionary
Jump to navigation Jump to search

This is a glossary of game theory—the branch of mathematics in which games are studied: that is, models describing human behaviour.

Contents: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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

A

[edit]
acceptable game
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
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.

B

[edit]
best reply
The best reply to a given complement is a strategy that maximizes player i's payment. Formally, we want:
.

C

[edit]
coalition
Any subset of the set of players: .
Condorcet winner
An outcome such that all non-dummy players prefer it to all other outcomes, given a preference ν on the outcome space.
cooperative game

A game in which players are allowed 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.

coordination game
A normal form game in which players have the same sets of strategies and their payoffs are higher if they chose the same strategies than they are if they choose different strategies.

D

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

E

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

extensive form game
A tree, where, at each node of the tree, a different player has the choice of choosing an edge.

F

[edit]
finite game
A game with finitely many players, each of which has a finite set of strategies.

M

[edit]
mixed strategy
For player i, 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.

N

[edit]
Nash equilibrium
The set of choices of players' strategies for which no player can benefit by changing his or her strategy while the other players keep theirs unchanged.
normal form game

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.

O

[edit]
outcome function
A function that assigns to each combination of chosen strategies an outcome from an outcome space. It appears in one of the formalizations of a normal form game; see normal form game.
outcome space
A set of all the possible outcomes of a game—outcomes to which a real-valued award is assigned for each player. Conventionally labeled as . It appears in one of the formalizations of a normal form game; see normal form game.

P

[edit]
Pareto efficiency
The property of being Pareto efficient.
Pareto efficient
An outcome a of game form π is (strongly) Pareto efficient if it is undominated under all preference profiles.
Pareto optimal
Of an allocation of goods to individual, such that it is Pareto efficient.
Pareto optimal
Of a strategy of a player, such that there is no alternative strategy outperforming it agaist at least one opponent's strategy while not underperforming it against any opponent's strategy.
Pareto optimality
The property of being Pareto optimal.
payoff function
Informally, a mathematical function describing the real-valued award given to a single player at the outcome of a game. Formally, a function , where is the strategy space. Accordingly, to completely specify a game, the payoff function has to be specified for each player in the player set P= {1, 2, ..., m}.
preference profile
A real-valued function that specifies for each outcome of the game and each of N players to what degree he prefers the outcome; that is, , where is the outcome space. See allocation of goods. This is the ordinal approach at describing the outcome of the game.
pure Nash equilibrium point
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.

S

[edit]
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.
simple game
A simplified form of a cooperative game, where the possible gain is assumed to be eiter '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.

V

[edit]
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. Antonym: dummy.

W

[edit]
weakly acceptable game
A game that has pure Nash equilibria some of which are pareto efficient.

Z

[edit]
zero-sum game
A normal form game for which, for each combination of strategies chosen by each player, the sum of the players' payoffs is zero.

Further reading

[edit]