Editing Glossary of game theory (section)

==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 <math> \nu\ : \Gamma\ \to \mathbb{R} ^\mathrm{N} </math>. 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  <math> \sigma\ _{-i} </math> is a strategy <math> \tau\ _i </math> that maximizes player '''i''''s payment. Formally, we want: <br> <math>
\forall \sigma\ _i \in\ \Sigma\ ^i \quad \quad
\pi\ (\sigma\ _i ,\sigma\ _{-i} ) \le \pi\ (\tau\ _i ,\sigma\ _{-i} )
</math>.

; Coalition : is any subset of the set of players: <math> \mathrm{S} \subseteq \mathrm{N} </math>.

; 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 (logic)|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.<ref>[https://mathoverflow.net/q/27967 Mathoverflow.net/Decidability-of-chess-on-an-infinite-board] Decidability-of-chess-on-an-infinite-board</ref>

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

;[[Strictly determined game|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 strategy|pure strategies]].<ref>{{cite book|title=A gentle introduction to game theory|author=Saul Stahl|page=[https://archive.org/details/gentleintroducti0000stah/page/54 54]|chapter=Solutions of zero-sum games|publisher=AMS Bookstore|year=1999|isbn=9780821813393|chapter-url=https://archive.org/details/gentleintroducti0000stah/page/54}}</ref><ref>{{cite book|title=An Introduction to Linear Programming and the Theory of Games|author=Abraham M. Glicksman|page=94|chapter=Elementary aspects of the theory of games|publisher=Courier Dover Publications|year=2001|isbn=9780486417103}}</ref>

; Dictator: A player is a ''strong dictator'' if he can guarantee any outcome regardless of the other players. <math>m \in \mathbb{N}</math> 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: <br> ''n'' is a ''Strong dictator'' if: <br> <math> \forall a \in \mathrm{A}, \; \exist \sigma\ _n \in \Sigma\ ^n \; s.t. \; \forall \sigma\ _{-n} \in \Sigma\ ^{-n}: \; \Gamma\ (\sigma\ _{-n},\sigma\ _n) = a </math> <br> ''m'' is a ''Weak dictator'' if: <br> <math> \forall a \in \mathrm{A}, \; \forall \sigma\ _{-m} \in \Sigma\ ^{-m} \; \exist \sigma\ _m \in \Sigma\ ^m \; s.t. \; \Gamma\ (\sigma\ _{-m},\sigma\ _m) = a </math>
:Another way to put it is:
::A ''strong dictator'' is <math>\alpha</math>-effective for every possible outcome.
::A ''weak dictator'' is <math>\beta</math>-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: <br> <math>
\forall j \in \mathrm{N} \; \quad   \nu\ _j (a) \le\ \nu\ _j (b) 
</math> for domination, and <br> <math>
\exists i \in \mathrm{N} \; s.t. \; \nu\ _i (a)   <  \nu\ _i (b)  
</math> for strict domination. <br> An outcome '''a''' is (strictly) '''dominated''' if it is (strictly) '''dominated''' by some other '''outcome'''. <br> 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 <math> \tau\ _i </math> if for any complement strategies tuple <math> \sigma\ _{-i} </math>, player ''i'' benefits by playing <math> \tau\ _i </math>. Formally speaking: <br> <math>
\forall \sigma\ _{-i} \in\ \Sigma\ ^{-i} \quad \quad
\pi\ (\sigma\ _i ,\sigma\ _{-i} ) \le \pi\ (\tau\ _i ,\sigma\ _{-i} )
</math> and <br> <math> 
\exists \sigma\ _{-i} \in\ \Sigma\ ^{-i} \quad s.t. \quad 
\pi\ (\sigma\ _i ,\sigma\ _{-i} ) < \pi\ (\tau\ _i ,\sigma\ _{-i} )
</math>. <br> 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 <math> \Sigma\ ^i </math>. 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 <math> \nu\ : \Gamma\ \to \mathbb{R} ^\mathrm{N} </math>. 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 <math> \sigma\ = (\sigma\ _i) _ {i \in \mathrm{N}} </math> of the strategy space of a game is a ''pure nash equilibrium point'' if no player '''i''' can benefit by deviating from his strategy <math> \sigma\ _i </math>, given that the other players are playing in <math> \sigma</math>. Formally: <br> <math>
\forall i \in \mathrm{N} \quad \forall \tau\ _i \in\ \Sigma\ ^i \quad 
\pi\ (\tau\ ,\sigma\ _{-i} ) \le \pi\ (\sigma\ )
</math>. <br> 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 complexity|game-tree complexity]] of [[chess]] (10<sup>120</sup>).

; [[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: <br> <math>
\forall \gamma\ \in \Gamma\ \sum_{i \in \mathrm{N}} \nu\ _i (\gamma\ ) = const. </math> <br> 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'''.

{{Game theory}}