Positional game

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)