Namespaces
Variants
Actions

Difference between revisions of "Positional game"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
 +
{{TEX|done}}
 
A game having the character of a process developing in discrete time on a tree-ordered set (also called a [[Tree|tree]]). The name finite positional game is given to a system
 
A game having the character of a process developing in discrete time on a tree-ordered set (also called a [[Tree|tree]]). The name finite positional game is given to a system
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p0738501.png" /></td> </tr></table>
+
$$\Gamma=\langle I,X,\mathfrak R,\{P_x\}_{x\in X_0},\{\mathfrak R_i\}_{i\in I},\{h_i\}_{i\in I}\rangle,$$
  
 
where
 
where
  
1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p0738502.png" /> is the set of players (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p0738503.png" />);
+
1) $I$ is the set of players ($|I|=n$);
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p0738504.png" /> is a finite tree, whose vertices are called positions and whose root is called the initial position. A sequential relation is naturally defined for positions; positions directly following a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p0738505.png" /> are called alternatives to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p0738506.png" />, while positions that do not have alternatives are called terminal positions and the paths leading to them are called trajectories; the set of terminal positions is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p0738507.png" />;
+
2) $X$ is a finite tree, whose vertices are called positions and whose root is called the initial position. A sequential relation is naturally defined for positions; positions directly following a given $x\in X$ are called alternatives to $x$, while positions that do not have alternatives are called terminal positions and the paths leading to them are called trajectories; the set of terminal positions is denoted by $X^*$;
  
3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p0738508.png" /> is a decomposition of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p0738509.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385010.png" /> sequence sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385011.png" />. In positions contained in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385013.png" />, a step is performed by player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385014.png" />, while the step is performed randomly in positions from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385015.png" />;
+
3) $\mathfrak R$ is a decomposition of the set $X\setminus X^*$ into $n+1$ sequence sets $X_0,\dots,X_n$. In positions contained in $X_i$, $i>0$, a step is performed by player $i$, while the step is performed randomly in positions from $X_0$;
  
4) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385016.png" /> are probability distributions in the sets of alternatives for each position <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385017.png" />;
+
4) $P_x$ are probability distributions in the sets of alternatives for each position $x\in X_0$;
  
5) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385018.png" /> is a decomposition of each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385019.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385020.png" />. It is assumed that all positions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385021.png" /> contained in a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385022.png" /> have an identical number of alternatives, and no position in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385023.png" /> follows a position in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385024.png" />; the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385025.png" /> are called information sets. Between the alternatives for all positions in a single information set there is a one-to-one correspondence, and each class is called an alternative of the information set itself;
+
5) $\mathfrak R=\{U_1^i,\dots,U_{m_i}^i\}$ is a decomposition of each $X_i$, $i>0$. It is assumed that all positions $x$ contained in a given $U_k^i$ have an identical number of alternatives, and no position in the $U_k^i$ follows a position in $U_k^i$; the sets $U_k^i$ are called information sets. Between the alternatives for all positions in a single information set there is a one-to-one correspondence, and each class is called an alternative of the information set itself;
  
6) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385026.png" /> is a function that puts each terminal position into correspondence with the gain of the player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385027.png" /> at it.
+
6) $h_i$ is a function that puts each terminal position into correspondence with the gain of the player $i$ at it.
  
A pure strategy of player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385028.png" /> in a positional game is a function that assigns an alternative to each information set. A set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385029.png" /> pure strategies for all players constitutes a situation. The game process in a given situation can be considered as a [[Random walk|random walk]] over the set of positions from the initial position to a terminal one, and at each position the player whose sequence set belongs to that position knows only the information set containing it and selects an alternative in accordance with his strategy. In positions from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385030.png" /> the choice of an alternative is random. This random walk defines a probability distribution on the set of terminal positions. If one takes for a player's gain the mathematical expectation of his gain at the terminal positions, a [[Non-cooperative game|non-cooperative game]] in normal form is obtained.
+
A pure strategy of player $i$ in a positional game is a function that assigns an alternative to each information set. A set of $n$ pure strategies for all players constitutes a situation. The game process in a given situation can be considered as a [[Random walk|random walk]] over the set of positions from the initial position to a terminal one, and at each position the player whose sequence set belongs to that position knows only the information set containing it and selects an alternative in accordance with his strategy. In positions from $X_0$ the choice of an alternative is random. This random walk defines a probability distribution on the set of terminal positions. If one takes for a player's gain the mathematical expectation of his gain at the terminal positions, a [[Non-cooperative game|non-cooperative game]] in normal form is obtained.
  
 
A positional game is called a game with complete information if the information sets of the players consist of one position each. In a game with complete information, an equilibrium situation exists in pure strategies (the Zermelo–von Neumann theorem).
 
A positional game is called a game with complete information if the information sets of the players consist of one position each. In a game with complete information, an equilibrium situation exists in pure strategies (the Zermelo–von Neumann theorem).
Line 26: Line 27:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> , ''Positional games'' , Moscow  (1967)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  C. Berge,  "Théorie génerale des jeux à <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385031.png" /> personnes" , Gauthier-Villars  (1957)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  H.W. Kuhn,  "Extensive games and the problem of information"  H.W. Kuhn (ed.)  A.W. Tucker (ed.) , ''Contributions to the theory of games'' , ''Ann. Math. Studies'' , '''28''' , Princeton Univ. Press  (1953)  pp. 193–216</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  G.L. Thompson,  "Signalling strategies in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073850/p07385032.png" />-person games"  H.W. Kuhn (ed.)  A.W. Tucker (ed.) , ''Contributions to the theory of games'' , ''Ann. Math. Studies'' , '''28''' , Princeton Univ. Press  (1953)  pp. 267–277</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  N.N. Vorob'ev,  "Dismembered strategies in positional games"  ''Probl. Kibernetiki'' :  7  (1962)  pp. 5–20  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  Bui Kong Kyong,  "Reduced-dismembered strategy in positional games"  ''Vestnik Leningrad. Gos. Univ.'' , '''1'''  (1969)  pp. 49–59  (In Russian)</TD></TR></table>
+
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> , ''Positional games'' , Moscow  (1967)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  C. Berge,  "Théorie génerale des jeux à $n$ personnes" , Gauthier-Villars  (1957)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  H.W. Kuhn,  "Extensive games and the problem of information"  H.W. Kuhn (ed.)  A.W. Tucker (ed.) , ''Contributions to the theory of games'' , ''Ann. Math. Studies'' , '''28''' , Princeton Univ. Press  (1953)  pp. 193–216</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  G.L. Thompson,  "Signalling strategies in $n$-person games"  H.W. Kuhn (ed.)  A.W. Tucker (ed.) , ''Contributions to the theory of games'' , ''Ann. Math. Studies'' , '''28''' , Princeton Univ. Press  (1953)  pp. 267–277</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  N.N. Vorob'ev,  "Dismembered strategies in positional games"  ''Probl. Kibernetiki'' :  7  (1962)  pp. 5–20  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  Bui Kong Kyong,  "Reduced-dismembered strategy in positional games"  ''Vestnik Leningrad. Gos. Univ.'' , '''1'''  (1969)  pp. 49–59  (In Russian)</TD></TR></table>
  
  

Latest revision as of 08:51, 25 November 2018

A game having the character of a process developing in discrete time on a tree-ordered set (also called a tree). The name finite positional game is given to a system

$$\Gamma=\langle I,X,\mathfrak R,\{P_x\}_{x\in X_0},\{\mathfrak R_i\}_{i\in I},\{h_i\}_{i\in I}\rangle,$$

where

1) $I$ is the set of players ($|I|=n$);

2) $X$ is a finite tree, whose vertices are called positions and whose root is called the initial position. A sequential relation is naturally defined for positions; positions directly following a given $x\in X$ are called alternatives to $x$, while positions that do not have alternatives are called terminal positions and the paths leading to them are called trajectories; the set of terminal positions is denoted by $X^*$;

3) $\mathfrak R$ is a decomposition of the set $X\setminus X^*$ into $n+1$ sequence sets $X_0,\dots,X_n$. In positions contained in $X_i$, $i>0$, a step is performed by player $i$, while the step is performed randomly in positions from $X_0$;

4) $P_x$ are probability distributions in the sets of alternatives for each position $x\in X_0$;

5) $\mathfrak R=\{U_1^i,\dots,U_{m_i}^i\}$ is a decomposition of each $X_i$, $i>0$. It is assumed that all positions $x$ contained in a given $U_k^i$ have an identical number of alternatives, and no position in the $U_k^i$ follows a position in $U_k^i$; the sets $U_k^i$ are called information sets. Between the alternatives for all positions in a single information set there is a one-to-one correspondence, and each class is called an alternative of the information set itself;

6) $h_i$ is a function that puts each terminal position into correspondence with the gain of the player $i$ at it.

A pure strategy of player $i$ in a positional game is a function that assigns an alternative to each information set. A set of $n$ pure strategies for all players constitutes a situation. The game process in a given situation can be considered as a random walk over the set of positions from the initial position to a terminal one, and at each position the player whose sequence set belongs to that position knows only the information set containing it and selects an alternative in accordance with his strategy. In positions from $X_0$ the choice of an alternative is random. This random walk defines a probability distribution on the set of terminal positions. If one takes for a player's gain the mathematical expectation of his gain at the terminal positions, a non-cooperative game in normal form is obtained.

A positional game is called a game with complete information if the information sets of the players consist of one position each. In a game with complete information, an equilibrium situation exists in pure strategies (the Zermelo–von Neumann theorem).

An important concept in positional games is that of mixed strategies. A player has complete recall if each of his/her information sets follows as a unique alternative from all the previous information sets for that player. The presence of complete recall for a player means that at the moment of making the move, he/she remembers all the information sets in which he/she was and the choices in them. A behaviour strategy is a mixed strategy in which the random choices of alternatives from the information sets are stochastically independent. Each mixed strategy is equivalent to a certain behaviour strategy if and only if the player has complete recall (Kuhn's theorem).

More general positional games are the ones with infinite sets of alternatives in each position and with infinitely continuing trajectories, as well as games on graphs (cf. Game on a graph).

References

[1] , Positional games , Moscow (1967) (In Russian)
[2] C. Berge, "Théorie génerale des jeux à $n$ personnes" , Gauthier-Villars (1957)
[3] H.W. Kuhn, "Extensive games and the problem of information" H.W. Kuhn (ed.) A.W. Tucker (ed.) , Contributions to the theory of games , Ann. Math. Studies , 28 , Princeton Univ. Press (1953) pp. 193–216
[4] G.L. Thompson, "Signalling strategies in $n$-person games" H.W. Kuhn (ed.) A.W. Tucker (ed.) , Contributions to the theory of games , Ann. Math. Studies , 28 , Princeton Univ. Press (1953) pp. 267–277
[5] N.N. Vorob'ev, "Dismembered strategies in positional games" Probl. Kibernetiki : 7 (1962) pp. 5–20 (In Russian)
[6] Bui Kong Kyong, "Reduced-dismembered strategy in positional games" Vestnik Leningrad. Gos. Univ. , 1 (1969) pp. 49–59 (In Russian)


Comments

A positional game is better known in the West as a game in extensive form.

A player's gain can be defined as the expectation of his gain at the terminal positions. This, however, does not mean that one necessarily deals with a non-cooperative game as suggested. The definition of equilibrium (non-cooperative equilibrium, for instance) and the definition of gain are independent concepts.

References

[a1] T. Basar, G.J. Olsder, "Dynamic noncooperative game theory" , Acad. Press (1989)
[a2] R.D. Luce, H. Raiffa, "Games and decisions. Introduction and critical survey" , Wiley (1957)
How to Cite This Entry:
Positional game. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Positional_game&oldid=12001
This article was adapted from an original article by N.N. Vorob'evA.N. Lyapunov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article