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_Seque… [accessed Aug 28, 2017].

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