Geodesic
On the problem of solving multimove games under time deficit
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 11 (2019) no. 2, pp. 96-120.

Voir la notice de l'article provenant de la source Math-Net.Ru

On example of antagonistic multimove game we consider the problem of choice by a first player of optimal by possibility strategy of behaviour under deficit of time available for him to make this choice. We suppose that each player makes his move in turn and before each move time available is insufficient to construct all the game tree from this move but it is sufficient to construct a subtree consisting of a limited amount of arcs. Thus we have the problem of a best choice of constructing strategy for this subtree and corresponding restriction of a subsequent game. We suppose that after the subtree pointed out above is constructed each player chooses his move on the base of calculations with the help of Kuhn algorithm for a game on this subtree. We consider two ways for constucting the subtree. The first one is naive way based on constructing a full tree for “uniform” restriction of the game to lesser amount of moves. The second one is based on probabilistic selection for subsequent branching of most “perspective” arcs with origin at current vertex. We prove that the first way can lead to arbitrary big miscalculations of a player. As to the second way we prove that the first player using it, in spite of rectricting his prior possibilities, forces the opponent player to act in the frame of a subgame selected and calculated for essentially larger amount of moves by the first player and this selection is made as expected best (in the probabilistic sense). Theoretical (obvious enough) reasoning is confirmed by some concrete example of antagonistic game on a tree graph and also by work results of an author computer program realizing the draughts game.
Keywords: multimove game under time deficit, Kuhn algorithm, expected best choice of game subtree. 
@article{MGTA_2019_11_2_a4,
     author = {Andrey V. Chernov},
     title = {On the problem of solving multimove games under time deficit},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {96--120},
     publisher = {mathdoc},
     volume = {11},
     number = {2},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2019_11_2_a4/}
}
TY  - JOUR
AU  - Andrey V. Chernov
TI  - On the problem of solving multimove games under time deficit
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2019
SP  - 96
EP  - 120
VL  - 11
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2019_11_2_a4/
LA  - ru
ID  - MGTA_2019_11_2_a4
ER  - 
%0 Journal Article
%A Andrey V. Chernov
%T On the problem of solving multimove games under time deficit
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2019
%P 96-120
%V 11
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2019_11_2_a4/
%G ru
%F MGTA_2019_11_2_a4
Andrey V. Chernov. On the problem of solving multimove games under time deficit. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 11 (2019) no. 2, pp. 96-120. http://geodesic.mathdoc.fr/item/MGTA_2019_11_2_a4/

[1] Vasin A. A., Morozov V. V., Vvedenie v teoriyu igr s prilozheniyami k ekonomike, MGU, M., 2003, 278 pp.

[2] Venttsel E. S., Ovcharov L. A., Teoriya veroyatnostei i ee inzhenernye prilozheniya, Vysshaya shkola, M., 2000, 480 pp.

[3] Gorelik V. A., Kononenko A. F., Teoretiko-igrovye modeli prinyatiya reshenii v ekologo-ekonomicheskikh sistemakh, Radio i svyaz, M., 1982, 145 pp. | MR

[4] Zhukovskii V. I., Kooperativnye igry pri neopredelennosti i ikh prilozheniya, Editorial URSS, M., 1999, 336 pp.

[5] Kononenko A. F., Khalezov A. D., Chumakov V. V., Prinyatie reshenii v usloviyakh neopredelennosti, VTs AN SSSR, M., 1991, 196 pp.

[6] Petrosyan L. A., Kuzyutin D. V., Ustoichivye resheniya pozitsionnykh igr, SPbGU, SPb., 2008, 327 pp.

[7] Petrosyan O. L., “Model mnogoshagovykh igr s uchetom vremeni realizatsii alternativy”, MTIiP, 7:2 (2015), 49–68 | MR | Zbl

[8] Takha Kh. A., Vvedenie v issledovanie operatsii, Izdatelskii dom «Vilyams», M., 2001, 912 pp.

[9] Ugolnitskii G. A., Ierarkhicheskoe upravlenie ustoichivym razvitiem, Fizmatlit, M., 2010, 336 pp.

[10] Shubik M., “Nastoyaschee i buduschee teorii igr”, MTIiP, 4:1 (2012), 93–116 | MR | Zbl

[11] Harsanyi J. C., “Games with Incomplete Information Played by “Bayesian” Players. Part I; II; III”, Management Science, 14 (1968), 159–182 ; 320–334 ; 486–502 | DOI | MR | Zbl | Zbl