On the Theory of Infinite Step Processes of Sequential Decision Making (a summary)

Boris I. Model
(Toronto, August 26, 2017)

Introduction
This is a summary of my research of Infinite Step Processes of Sequential Decision Making that was
started in 1970.

Part I
Differential Games and Set Theory
Let us assume that on plane R^2 a cat (that has velocity C=(c1,c2)) is running after a mouse (that has
velocity M=(m1,m2) and that is running from the cat). They begin at a moment t=0 and are to stop at
the moment t=1. The aim of the cat is to catch the mouse as soon as possible or at least to be as close as
possible to the mouse at the moment t=1. The aim of the mouse is quite opposite. A “solution” of the
game is quite obvious: the cat is to run directly to the mouse while the mouse is to run directly from the
cat. But the word Solution is written especially in quotation marks, because the main question (or at
least one of the main questions) is not only to find a solution, but TO UNDERSTAND first of all what
the movements themselves of the cat and of the mouse are. From the point of view of the game itself it
can be suggested that the mouse (and the cat also) can choose its velocity at any moment of time. So let
us assume, for example that the mouse is choosing some vector M*=(m*1,m*2) at any moment of time,
belonging to non-measurable Vitali set V and is choosing another vector M**=(m**1,m**2) (different
from M*) at any other moment of time. It’s clear that in this case mouse’s movement is not
understandable at all??! So above suggestion (that velocity could be chosen at any moment of time) can
make impossible description of the game by means of differential equations!!!
This deep internal contradiction between Game Nature and its Differential Description can be solved,
for example by means of assuming that the cat and the mouse can choose their decisions not just at any
moment of time but choosing a decision at a moment t(i) the mouse can choose a next one at any
moment t(i+1)>t(i) and does not change a previous decision (made at t(i)) till t(i+1) (the same is
assumed for the cat also). So time interval [0,1] is divided into countable set of subintervals (ordinal of
this partition [0,1] can be any ordinal number from the set of ordinals of countable sets). Such approach
seems to be very natural, because it is consistent with the Game Nature and also gives possibility to
determine very easily the game by means of Differential Equations (because on each subinterval
velocities are constant). The same approach can be used not only in the above game but also in posing
Differential Games in general and leads us from Differential Games to special class of Infinite Step
Decision Making Processes [1,2].
Questions arising in such class of well-ordered processes and in some more general class of processes
(where an ordinal of a set of processes steps does not necessary belong to the set of ordinals of
countable sets) are connected with Set Theory.
On 2003 Dr. Rene Schipperus had made a talk “Differential games on Cardinal numbers” in Seminar of
Kurt Gödel Research Center for Mathematical Logic at the University of Vienna.

References
1. B. I. Model’, The existences of an overall έ-optimal strategy and validity of Bellman’s

functional equation in an extended class of dynamic processes. I; II, Engineering Cybernetics, No.5,
1975, pp. 13 – 19; No. 6, 1975, pp. 12 – 19.
2. B. I. Model’, A certain class of differential games, Engineering Cybernetics, No.2, 1978, pp. 32 – 38.

Part II
A short survey of the considered processes and proved results
On the border of Set Theory and Game Theory there is a broad class of Infinite Step Processes of
Sequential Decision Making that can be characterized by the main following property: a Future
development of the process depends on the process Present state and does not depend directly on the
process Past (these processes have the same nature as for example chess and checkers have: a game
Future depends on the game Present state and does not depend directly on the game Past).
Some examples of such Infinite Step Processes give us Differential Games in certain posing and Games
of Search and Completion (subsequently also called Boris Model Games).
For these Processes with the use of Axiom of Choice some generalizations of basic results, which are
well known facts in case of Finite Step Decision Making Processes (for example, existence of a
uniformly optimal strategy), can be proved.
These results were published in the book (in Russian): B. I. Model, Elements of the theory of multistep
processes of sequential decision making, Nauka, Moscow, 1985 (Модель, Борис Израилович.
Элементы теории многошаговых процессов последовательного выбора решений — Москва :
Наука, 1985)
This book can be found in many libraries in different countries or can be read online.
Main results of the book are presented in English in:
1. B. I. Model’, The existences of an overall έ-optimal strategy and validity of Bellman’s
functional equation in an extended class of dynamic processes. I; II, Engineering Cybernetics, No.5,
1975, pp. 13 – 19; No. 6, 1975, pp. 12 – 19.
2. B. I. Model’, A certain class of differential games, Engineering Cybernetics, No.2, 1978, pp. 32 – 38.

Part III
Games of search and completion
As an example of considered processes and some connected with them questions Games
of Search and Completion, which are interesting by themselves also, are also studied.
For these games (of the same nature as for example chess and draughts have: a Future depends on the
Present and does not depend directly on the Past) with the use of continuum hypothesis much
unexpected results can be proved, for example:
The least guaranteed result of these simultaneously played but completely independent games turns
out to be less than the sum of the least guaranteed results of constituent games (and not equal to
this sum as it could be supposed and as it is in the case of chess or draughts!).
These results were published in: B. I. Model’, Games of search and completion, Journal of
Mathematical Sciences, Vol. 80, No 2, 1996, pp. 1699 — 1744, Plenum Publishing Corporation, New
York.

Considered games of search and completion (they were subsequently also called Boris Model Games)
have been cited and received further investigation in:
U. Abraham, R. Schipperus, Infinite games on finite sets, Israel Journal of Mathematics, 2007.
(We study a family of infinite games with imperfect information introduced by B. Model, Boris Model
Games on Cardinals.)
D. H. Fremlin, Give a penny, take a penny, University of Essex, UK, 2009.
F. Piccoli, Partially Ordered Sets and Their Invariants, University of East Anglia, UK, 2014.
(We investigate Model Games. Model games are set theoretical games on infinite sets introduced by B.
Model.)

Part IV
An open question
The question when information of process Past history additional to information of process Present
state, for example, perfect information, does not improve and when such information does improve best
guaranteed result in considered infinite stage processes (like chess, checkers, Games of Search and
Completion) comparing with best guaranteed result provided by information of only process Present
state has remained an open question.
For example, for chess and checkers (even without rules of stopping) information of game Past history
additional to information of game Present state does not improve best guaranteed result but for Infinite
Stage Games of Search and Completion, having just the same structure as chess and checkers [1],
information of game Past history additional to information of game Present state does improve best
guaranteed result [1,2].
So the question is: what criteria distinguish between processes for which information of process Past
history in addition to information of process Present state does not improve best guaranteed result, and
processes for which information of process Past history additional to information of process Present
state does improve best guaranteed result?
References:
1. B. I. Model’, The existences of an overall έ-optimal strategy and validity of Bellman’s functional
equation in an extended class of dynamic processes. I; II, Engineering Cybernetics, No.5, 1975, pp. 13
– 19; No. 6, 1975, pp. 12 – 19.
2. B. I. Model’, Games of search and completion, Journal of Mathematical Sciences, Vol. 80, No 2,
1996, pp. 1699 — 1744, Plenum Publishing Corporation, New York.

CitationsCitations0
ReferencesReferences1

Model’, Games of search and completion. 1996.1699-1744.
On the Theory of Infinite Step Processes of Sequential Decision Making (a summary) (PDF Download Available). Available from: https://www.researchgate.net/publication/319291731_On_the_Theory_of_Infinite_Step_Processes_of_Sequential_Decision_Making_a_summary [accessed Aug 28, 2017].

Оригинал материала

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *