Prophet Inequalities for Mixtures

This is a 12-month research project in mathematical optimisation and applied probability. It provides additional research time to take advantage of recent advances of the Project Lead and develop prophet inequalities for mixtures of distributions. Prophet inequalities are a central object in the theory of optimal stopping, which studies decision-making under uncertainty regarding future opportunities. Optimal stopping is governed by elegant mathematics and has applications in statistics, economics, and business, for example to hypothesis testing, options trading, and inventory management. The two most fundamental problems in optimal stopping are the secretary problem and the prophet problem. In both problems a decision-maker observes a sequence of values and must select one of the values without knowledge of future values and without recourse. In the secretary problem values are arbitrary and arrive in a random order, and the goal is to maximise the probability of selecting the largest one. A well-known optimal strategy, known colloquially as the 37% rule, observes an initial 1/e˜0.368 fraction of the values and then selects the first value thereafter that exceeds all previous values. This guarantees the largest value to be selected with probability at least 1/e. In the prophet problem values are random variables and the goal is to maximise the expectation of the selected value. A prophet inequality is an inequality that establishes, for some a between 0 and 1, that the expectation of the selected value is at least a times the expectation of the maximum value in the sequence. Additional assumptions on the distribution of the random variables lead to different variants of the prophet problem. For the most restrictive variant, where values are independent and identically distributed (iid), an optimal strategy is known. The strategy is more complicated than that for the secretary problem and achieves a˜0.745. This project will study a variant of the prophet problem where values are drawn from a mixture, i.e., where they are iid from a distribution which is itself drawn from a distribution over distributions. It builds directly on recent work of the Project Lead which solved variants of the prophet problem where the distribution is unknown or where the values form an exchangeable sequence. The prophet problem for mixtures lies between the secretary problem and the iid prophet problem in the sense that the optimum value of a lies between 1/e and 0.745. The motivation for studying it is threefold. First, it models a property found in applications, where a decision-maker is faced with one of a number of possible scenarios and both the likelihood and structure of individual scenarios are well understood. Second, it provides a natural framework for studying an aspect of optimal stopping that is profoundly underexplored, namely the role of correlation. Third, it reveals a number of weaknesses of both our current understanding of prophet problems and known techniques for their analysis.