Optimal Stopping Problem

Motivation. Imagine a gambling situation, where there is a sequence of prizes inside boxes. The gambler knows the distribution of these boxes, but is only shown one at a time. They can claim only one box, and once a box is opened the prize must be claimed or trashed. How can the gambler act?

def. (Optimal stopping problem) let prizes of random variables $X_1,X_2\dots ,X_n$ be distributed $F_1,F_2,\dots ,F_n$. The gambler only knows the distribution of each of these boxes, and the order in which the boxes are shown is shuffled randomly.

thm. Prophet Inequality. There is a strategy for the gambler to achieve at least $\frac{1}{2}$ of the optimal revenue, i.e.:

$$\mathbb{E}(\text{payoff})\ge \frac{1}{2}\mathbb{E}({\text{max}}_{i=1}^n{X}_i)$$

where…

• $\text{payoff}$ is the payoff to the gambler
• let $X^{\ast }:={\text{max}}_{i=1}^n{X}_i$, a random variable. This is what the “Prophet” gets, i.e. a optimal strategy. Additionally, the theorem states that this strategy is a optimal cutoff strategy, which is one that stops if the payoff from the current opened box is larger than predetermined cutoff $w$.

Proof. We know that $\text{payoff}=\text{base payoff}+\text{excess payoff}$ where

• base payoff is $w$
• excess payoff is $X_j-w$, where $X_j$ is the box we stop at We also know that these two are random varibles:

$$w=\{\begin{array}{ll}w& \text{if }{X}^{\ast }\ge w\\ 0& \text{else}\end{array}$$ $$\text{excess payoff}=\{\begin{array}{ll}\mathbb{E}((X_j-w{)}^{+})& \text{if stopped at }{X}_j\\ 0& \text{if never stopped}\end{array}$$

Now, the expected payoff is:

$$\begin{array}{r}\mathbb{E}(\text{payoff})=\underset{\text{ expected base }}{\underbrace{\mathbb{P}(X^{\ast }\ge w)\cdot w}}+\underset{\text{ expected excess }}{\underbrace{\sum _{j=1}^n\mathbb{P}(\text{stopping at }{X}_j)\cdot \mathbb{E}((X_j-w{)}^{+})}}\end{array}$$

We know that the probability of stopping at $X_j$ (from the first case of excess payoff) is:

$$\begin{array}{rlr}\mathbb{P}(\text{stopping at }{X}_j)& =\mathbb{P}({\text{max}}_{i=1}^{j-1}{X}_i<w)& \text{...that boxes before }j\text{ where }<w\\ & \ge \mathbb{P}({\text{max}}_{i=1}^n{X}_i<w)& \text{...that all boxes are }<w\\ & =\mathbb{P}(X^{\ast }<w)& \text{by definition of }{X}^{\ast }\end{array}$$

Thus:

$$\mathbb{E}(\text{payoff})\ge \mathbb{P}(X^{\ast }\ge w)\cdot w+\underset{\text{ take out since X∗ is not relevant to j }}{\underbrace{\mathbb{P}(X^{\ast }<w)\cdot \sum _{j=1}^n\mathbb{E}((X_j-w{)}^{+})}}$$

(lemma 1) On the other hand, the expected prophet payoff is

$$\begin{array}{rlr}\mathbb{E}(X^{\ast })& =\mathbb{E}(w+{\text{max}}_{j=1}^n(X_j-w))& \\ & \le w+\mathbb{E}({\text{max}}_{j=1}^n(X_j-w{)}^{+})& \text{by definition of (…)+}\\ & \le w+\sum _{j=1}^n\mathbb{E}((X_j-w{)}^{+})& \text{sum greater than max}\end{array}$$

(lemma 2) Noticing lemma 1 and lemma 2 both have term ${\sum }_{j=1}^n\mathbb{E}((X_j-w{)}^{+})$, we can organize for that:

$$\frac{\mathbb{E}(\text{payoff})-w\cdot \mathbb{P}(X^{\ast }\ge w)}{\mathbb{P}(X^{\ast }<w)}\ge \sum _{j=1}^n\mathbb{E}((X_j-w{)}^{+})\ge \mathbb{E}(X^{\ast })-w$$

Simplifying we get

$$\mathbb{E}(\text{payoff})\ge \frac{1}{2}\mathbb{E}(X^{\ast })$$

■