Randomization in the two-parameter optimal stopping problem

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 probabilistic model to properties of the associated graph leads to a new class of perfectly orderable graphs. These combinatorial techniques give considerable insight into the increase in complexity of the information structure when passing from one to two parameters : the single-parameter case is quite restricted, whereas the two-parameter case is in a certain sense already the most general (see Chapter 5). Furthermore, these methods enable us to show, in a finite-dimensional setting, that under a classical hypothesis on the two-parameter probabilistic model, all extremal elements of U are stopping points. Structural properties of the two-parameter information structure on arbitrary probability spaces are also examined. Most results on two-parameter processes have been obtained under Hypothesis F4 of Cairoli and Walsh. However, this hypothesis is not invariant under a change of equivalent measure, whereas a weaker hypothesis CQI, introduced by Krengel and Sucheston, is. Though one could hope that CQI would imply the existence of an equivalent measure such that F4 holds, we show through an example that this is not the case. Furthermore, in discrete time, we give necessary and sufficient conditions for the existence of an equivalent measure such that F4 holds (see Chapter 2). Since the initial optimal stopping problem will usually lead to an infinite-dimensional set U, extensions of results on finite perfect graphs and polytopes to such settings becomes of interest. Results in this direction are presented in Chapter 6. But the extension to discrete time and arbitrary probability spaces is achieved using a purely probabilistic decomposition of a non-extremal randomized stopping point on N2 into a convex combination of two others. The intuition behind this construction comes from a detailed study of "two-parameter graphs", and the probabilistic tool is a "conditional supremum" operator (see Chapter 7), which has many properties of conditional expectation, but is invariant under a change of equivalent measure. In fact, a conditional qualitative independence hypothesis on the two-parameter filtration becomes a commutation property of this operator. Extensions of this result to a continuous parameter setting are examined. However, extending the decomposition of a randomized stopping point would require the construction of a continuous time optional increasing path. This kind of construction can be done, in the presence of some regularity hypothesis, by solving certain random differential equations (see Chapter 3). But no regularity is present in the continuous parameter setting. This and other difficulties motivate the use of techniques from infinitesimal stochastic calculus for the study of this extension (see Chapter 8). By constructing a canonical hyperfinite probability space for two-parameter processes, which satisfies Hypothesis F4 of Cairoli and Walsh, we can "lift" two-parameter randomized stopping points to hyperfinite weight processes. This lifting enables, via the Transfer Principle, a continuous time solution by the methods developed in the discrete case. Certain difficulties related to the two-parameters, which do not appear in the hyperfinite theory for single-parameter processes, are solved using the "conditional supremum" operator described above. With this result, we obtain the existence of optimal stopping points for upper semicontinuous two-parameter processes defined on this canonical hyperfinite probability space. Though this result does not say how a player can achieve an optimal reward, no simple solution to such a question is to be expected. Indeed, some stopping points lie on a unique optional increasing path (see Chapter 3), and so any mistake by the player, even early in the game, may prevent him from attaining the optimal stopping point. Many questions pertaining to the optimal stopping problem remain to be solved, but it seems reasonable to hope that blending Stochastic Processes and Discrete Mathematics, two areas generally considered disparate, together with the hyperfinite techniques of Non-Standard Analysis, should lead to many further interesting developments.