Glossary of game theory

Last updated

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.

Contents

Definitions of a game

Notational conventions

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

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

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

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

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

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).
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 coalitionS 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 outcomea 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 (10120).
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.

Related Research Articles

Normal distribution probability distribution

In probability theory, a normaldistribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is

In physics, optical depth or optical thickness, is the natural logarithm of the ratio of incident to transmitted radiant power through a material, and spectral optical depth or spectral optical thickness is the natural logarithm of the ratio of incident to transmitted spectral radiant power through a material. Optical depth is dimensionless, and in particular is not a length, though it is a monotonically increasing function of optical path length, and approaches zero as the path length approaches zero. The use of the term "optical density" for optical depth is discouraged.

Students <i>t</i>-distribution probability distribution

In probability and statistics, Student's t-distribution is any member of a family of continuous probability distributions that arises when estimating the mean of a normally distributed population in situations where the sample size is small and the population standard deviation is unknown. It was developed by William Sealy Gosset under the pseudonym Student.

Theta function Special functions of several complex variables

In mathematics, theta functions are special functions of several complex variables. They are important in many areas, including the theories of Abelian varieties and moduli spaces, and of quadratic forms. They have also been applied to soliton theory. When generalized to a Grassmann algebra, they also appear in quantum field theory.

In mathematics, the Hamilton–Jacobi equation (HJE) is a necessary condition describing extremal geometry in generalizations of problems from the calculus of variations, and is a special case of the Hamilton–Jacobi–Bellman equation. It is named for William Rowan Hamilton and Carl Gustav Jacob Jacobi.

Scaled inverse chi-squared distribution

The scaled inverse chi-squared distribution is the distribution for x = 1/s2, where s2 is a sample mean of the squares of ν independent normal random variables that have mean 0 and inverse variance 1/σ2 = τ2. The distribution is therefore parametrised by the two quantities ν and τ2, referred to as the number of chi-squared degrees of freedom and the scaling parameter, respectively.

In probability theory, the central limit theorem says that, under certain conditions, the sum of many independent identically-distributed random variables, when scaled appropriately, converges in distribution to a standard normal distribution. The martingale central limit theorem generalizes this result for random variables to martingales, which are stochastic processes where the change in the value of the process from time t to time t + 1 has expectation zero, even conditioned on previous outcomes.

Toroidal coordinates three-dimensional orthogonal coordinate system

Toroidal coordinates are a three-dimensional orthogonal coordinate system that results from rotating the two-dimensional bipolar coordinate system about the axis that separates its two foci. Thus, the two foci and in bipolar coordinates become a ring of radius in the plane of the toroidal coordinate system; the -axis is the axis of rotation. The focal ring is also known as the reference circle.

Newman–Penrose formalism Notation in general relativity

The Newman–Penrose (NP) formalism is a set of notation developed by Ezra T. Newman and Roger Penrose for general relativity (GR). Their notation is an effort to treat general relativity in terms of spinor notation, which introduces complex forms of the usual variables used in GR. The NP formalism is itself a special case of the tetrad formalism, where the tensors of the theory are projected onto a complete vector basis at each point in spacetime. Usually this vector basis is chosen to reflect some symmetry of the spacetime, leading to simplified expressions for physical observables. In the case of the NP formalism, the vector basis chosen is a null tetrad: a set of four null vectors—two real, and a complex-conjugate pair. The two real members asymptotically point radially inward and radially outward, and the formalism is well adapted to treatment of the propagation of radiation in curved spacetime. The Weyl scalars, derived from the Weyl tensor, are often used. In particular, it can be shown that one of these scalars— in the appropriate frame—encodes the outgoing gravitational radiation of an asymptotically flat system.

In the Newman–Penrose (NP) formalism of general relativity, Weyl scalars refer to a set of five complex scalars which encode the ten independent components of the Weyl tensor of a four-dimensional spacetime.

In 3-dimensional topology, a part of the mathematical field of geometric topology, the Casson invariant is an integer-valued invariant of oriented integral homology 3-spheres, introduced by Andrew Casson.

In mathematics, the theory of optimal stopping or early stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance. A key example of an optimal stopping problem is the secretary problem. Optimal stopping problems can often be written in the form of a Bellman equation, and are therefore often solved using dynamic programming.

In statistics, the multivariate t-distribution is a multivariate probability distribution. It is a generalization to random vectors of the Student's t-distribution, which is a distribution applicable to univariate random variables. While the case of a random matrix could be treated within this structure, the matrix t-distribution is distinct and makes particular use of the matrix structure.

Expected shortfall (ES) is a risk measure—a concept used in the field of financial risk measurement to evaluate the market risk or credit risk of a portfolio. The "expected shortfall at q% level" is the expected return on the portfolio in the worst of cases. ES is an alternative to value at risk that is more sensitive to the shape of the tail of the loss distribution.

In mathematics, Maass forms or Maass wave forms are studied in the theory of automorphic forms. Maass forms are complex-valued smooth functions of the upper half plane, which transform in a similar way under the operation of a discrete subgroup of as modular forms. They are Eigenforms of the hyperbolic Laplace Operator defined on and satisfy certain growth conditions at the cusps of a fundamental domain of . In contrast to the modular forms the Maass forms need not be holomorphic. They were studied first by Hans Maass in 1949.

The Brownian motion models for financial markets are based on the work of Robert C. Merton and Paul A. Samuelson, as extensions to the one-period market models of Harold Markowitz and William F. Sharpe, and are concerned with defining the concepts of financial assets and markets, portfolios, gains and wealth in terms of continuous-time stochastic processes.

The table of chords, created by the Greek astronomer, geometer, and geographer Ptolemy in Egypt during the 2nd century AD, is a trigonometric table in Book I, chapter 11 of Ptolemy's Almagest, a treatise on mathematical astronomy. It is essentially equivalent to a table of values of the sine function. It was the earliest trigonometric table extensive enough for many practical purposes, including those of astronomy. Centuries passed before more extensive trigonometric tables were created. One such table is the Canon Sinuum created at the end of the 16th century.

In the Newman–Penrose (NP) formalism of general relativity, independent components of the Ricci tensors of a four-dimensional spacetime are encoded into seven Ricci scalars which consist of three real scalars , three complex scalars and the NP curvature scalar . Physically, Ricci-NP scalars are related with the energy–momentum distribution of the spacetime due to Einstein's field equation.

Stochastic portfolio theory (SPT) is a mathematical theory for analyzing stock market structure and portfolio behavior introduced by E. Robert Fernholz in 2002. It is descriptive as opposed to normative, and is consistent with the observed behavior of actual markets. Normative assumptions, which serve as a basis for earlier theories like modern portfolio theory (MPT) and the capital asset pricing model (CAPM), are absent from SPT.

Lagrangian field theory is a formalism in classical field theory. It is the field-theoretic analogue of Lagrangian mechanics. Lagrangian mechanics is used to analyze the motion of a system of discrete particles each with a finite number of degrees of freedom. Lagrangian field theory applies to continua and fields, which have an infinite number of degrees of freedom.

References

  1. Mathoverflow.net/Decidability-of-chess-on-an-infinite-board Decidability-of-chess-on-an-infinite-board
  2. Saul Stahl (1999). "Solutions of zero-sum games". A gentle introduction to game theory. AMS Bookstore. p.  54. ISBN   9780821813393.
  3. 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.