Detailed form of the game

The game is in expanded form

The expanded form ( English. Extensive form ) of the game is called its representation in the form of a tree. A tree consists of vertices and edges connecting them. Vertices are divided into terminal (final) and non-terminal. Each non-terminal vertex is characterized by a set of valid moves and information available to the player. Terminal vertices report the amount of winnings received upon reaching them.

In an expanded form, it is possible to present games of incomplete information . In this case, the game begins with the course of nature , that is, some random event.

Definition for the ultimate game

The final game in expanded form is a structure $\Gamma =\langle {\mathcal {K}},\mathbf {H} ,[(\mathbf {H} _{i})_{i\in {\mathcal {I}}}],\{A(H)\}_{H\in \mathbf {H} },a,\rho ,u\rangle$ ${\ displaystyle \ Gamma = \ langle {\ mathcal {K}}, \ mathbf {H}, [(\ mathbf {H} _ {i}) _ {i \ in {\ mathcal {I}}}], \ {A (H) \} _ {H \ in \ mathbf {H}}, a, \ rho, u \ rangle}$ $\Gamma =\langle {\mathcal {K}},\mathbf {H} ,[(\mathbf {H} _{i})_{i\in {\mathcal {I}}}],\{A(H)\}_{H\in \mathbf {H} },a,\rho ,u\rangle$ Where:

${\mathcal {K}}=\langle V,v^{0},T,p\rangle$ ${\ displaystyle {\ mathcal {K}} = \ langle V, v ^ {0}, T, p \ rangle}$ ${\mathcal {K}}=\langle V,v^{0},T,p\rangle$ - finite tree with many vertices $V$ ${\ displaystyle V}$ $V$ , the only starting point $v^{0}\in V$ ${\ displaystyle v ^ {0} \ in V}$ $v^{0}\in V$ , a set of terminal vertices $T\subset V$ ${\ displaystyle T \ subset V}$ $T\subset V$ (let be $D=V\setminus T$ ${\ displaystyle D = V \ setminus T}$ $D=V\setminus T$ there is a set of non-terminal vertices) and a function of the nearest predecessor $p:V\rightarrow D$ ${\ displaystyle p: V \ rightarrow D}$ $p:V\rightarrow D$ .
$\mathbf {H}$ ${\ displaystyle \ mathbf {H}}$ $\mathbf {H}$ - splitting $D$ ${\ displaystyle D}$ $D$ called information partitioning.
$A(H)$ ${\ displaystyle A (H)}$ $A(H)$ - a set of possible actions for each information set $H\in \mathbf {H}$ ${\ displaystyle H \ in \ mathbf {H}}$ $H\in \mathbf {H}$ ; these sets form a partitioning of the set of all possible actions. ${\mathcal {A}}$ ${\ displaystyle {\ mathcal {A}}}$ $\mathcal{A}$ .
$a:V\setminus \{v^{0}\}\rightarrow {\mathcal {A}}$ ${\ displaystyle a: V \ setminus \ {v ^ {0} \} \ rightarrow {\ mathcal {A}}}$ $a:V\setminus \{v^{0}\}\rightarrow {\mathcal {A}}$ splitting a set of actions that displays each vertex $v$ ${\ displaystyle v}$ $v$ in sole action $a(v)$ ${\ displaystyle a (v)}$ $a(v)$ and satisfying the condition

$\forall H\in \mathbf {H} ,\forall v\in H$ ${\ displaystyle \ forall H \ in \ mathbf {H}, \ forall v \ in H}$ $\forall H\in \mathbf {H} ,\forall v\in H$ , restriction $a_{v}:s(v)\rightarrow A(H)$ ${\ displaystyle a_ {v}: s (v) \ rightarrow A (H)}$ $a_{v}:s(v)\rightarrow A(H)$ for $a$ ${\ displaystyle a}$ $a$ on $s(v)$ ${\ displaystyle s (v)}$ $s(v)$ bijectively and $s(v)$ ${\ displaystyle s (v)}$ $s(v)$ there are many vertices that follow $v$ ${\ displaystyle v}$ $v$ .

${\mathcal {I}}=\{1,...,I\}$ ${\ displaystyle {\ mathcal {I}} = \ {1, ..., I \}}$ ${\mathcal {I}}=\{1,...,I\}$ - a finite set of players $0$ ${\ displaystyle 0}$ $0$ - special player " Nature ", $(\mathbf {H} _{i})_{i\in {\mathcal {I}}\cup \{0\}}$ ${\ displaystyle (\ mathbf {H} _ {i}) _ {i \ in {\ mathcal {I}} \ cup \ {0 \}}}$ $(\mathbf {H} _{i})_{i\in {\mathcal {I}}\cup \{0\}}$ player-specific information partitioning $\mathbf {H}$ ${\ displaystyle \ mathbf {H}}$ $\mathbf {H}$ . Let be $\iota (v)=\iota (H)$ ${\ displaystyle \ iota (v) = \ iota (H)}$ $\iota (v)=\iota (H)$ there is a single player making a move at the top $v\in H$ ${\ displaystyle v \ in H}$ $v \in H$ .
$\rho =\{\rho _{H}:A(H)\rightarrow [0,1]|H\in \mathbf {H} _{0}\}$ ${\ displaystyle \ rho = \ {\ rho _ {H}: A (H) \ rightarrow [0,1] | H \ in \ mathbf {H} _ {0} \}}$ $\rho =\{\rho _{H}:A(H)\rightarrow [0,1]|H\in \mathbf {H} _{0}\}$ - family of distributions on a set of moves of nature.
$u=(u_{i})_{i\in {\mathcal {I}}}:T\rightarrow \mathbb {R} ^{\mathcal {I}}$ ${\ displaystyle u = (u_ {i}) _ {i \ in {\ mathcal {I}}}: T \ rightarrow \ mathbb {R} ^ {\ mathcal {I}}}$ $u=(u_{i})_{i\in {\mathcal {I}}}:T\rightarrow \mathbb {R} ^{\mathcal {I}}$ - win function.

Literature

Hart, Sergiu. Games in extensive and strategic forms // Handbook of Game Theory with Economic Applications. - Elsevier, 1992. - Vol. 1. - ISBN 978-0-444-88098-7 .
Binmore, Kenneth. Playing for real: a text on game theory. - Oxford University Press US, 2007. - ISBN 978-0-19-530057-4 .
Dresher M. (1961). Theory of games and strategy (theory of games and games), pp74–78. Rand Corp. ISBN 0-486-64216-X
Fudenberg D and Tirole J. (1991) Game theory (Ch3 Extensive form games, pp67-106). Mit press. ISBN 0-262-06141-4
Leyton-Brown, Kevin & Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction , San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1 , < http: // www.gtessentials.org > . An 88-page mathematical introduction; see Chapters 4 and 5. Free online at many.
Luce RD and Raiffa H. (1957). Games and decisions: introduction and critical survey. (Ch3: Extensive and Normal Forms, pp39-55). Wiley New York. ISBN 0-486-65943-7
Osborne MJ and Rubinstein A. 1994. A course in game theory (Ch6 Extensive game with perfect information, pp. 89–115). MIT press. ISBN 0-262-65040-1
Shoham, Yoav & Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations , New York: Cambridge University Press , ISBN 978-0-521-89943-7 , < http: // www .masfoundations.org > . A comprehensive reference from a computational perspective; see Chapter 5. Downloadable free online .

Detailed form of the game

Definition for the ultimate game

See also

Literature

More articles: