Randomization in the two-parameter optimal stopping problem : combinatorial, probabilistic and infinitesimal methods

The motivation to this research is the study of the optimal stopping problem for multiparameter processes : given a random process depending on finitely many parameters t = (t1,…,tn), which if stopped at point t in the parameter set produces a reward Xt, what random stopping point T = (T1,…,Tn) maximizes the expected reward ? This is a natural model for a gambler who has the choice of playing several different games and of stopping at the most advantageous time. Of course, the decision to stop at a given point should only depend on the information available at that point, so the maximum is taken over the set T of non-anticipative strategies. The case n = 1 has been extensively studied over the last twenty years or so, but when n > 1, the problem is quite different and much less is known so far. Since most difficulties are already present when n = 2, our study is centered on this case. The first question relative to the optimal stopping problem that needs to be addressed is whether optimal stopping rules exist under suitable regularity assumptions on the reward process. This reduces to showing that the function T→E(XT) attains its maximum at some point T0∈T. It is thus natural to embed T into some larger ("randomized") set U with certain convexity and compactness properties, in such a way that T→E(XT) can be extended to a function with sufficient regularity that a maximum over U will exist. The choice of randomization should be such that one can then recover a maximum over T. The regularity question can often be solved by an approximation of upper semi-continuous multiparameter processes by continuous ones (see Chapter 9). This technique will enable us to show that upper semi-continuity of the sample paths of the reward process guarantees regularity of the extension of the map T→E(XT). As for the randomization question, a natural extension of a method developed for single-parameter processes leads to the convex set U of randomized stopping points. Contrary to the single-parameter case, the set of extremal elements of U may properly contain T. An important object of study is to determine sufficient conditions on the underlying information structure that ensure equality of these two sets. This has led to several developments in graph theory, convexity theory and stochastic processes. Insight about the set of randomized stopping points can be obtained by examining this set when it is finite-dimensional (see Chapter 4). In this case, U is a bounded polyhedron P defined by a (0,1)-matrix. An interesting analogy appears : maximizing over T is similar to solving an integer program, whereas maximizing over U is similar to solving a linear program. This observation is of importance for the practical numerical solution of an optimal stopping problem. These two problems are equivalent when the polytope P is perfect, and conditions for this can be expressed in terms of perfect graphs. Relating properties of the information structure in the two-parameter proba