Bayesian Optimal Stopping with Maximum Value Knowledge Pieter Kleer, Daan Noordenbos Abstract We consider an optimal stopping problem with n n correlated offers where the goal is to design a (randomised) stopping strategy that maximises the expected value of the offer at which we stop. Instead of assuming to know the complete correlation structure, which is unrealistic in practice, we only assume to have knowledge of the distribution of the maximum value X max X_{\max} of the sequence, and want to analyse the worst-case correlation structure whose maximum follows this distribution. This can be seen as a trade-off between the setting in which no distributional information is known, and the Bayesian setting in which the (possibly correlated) distributions of all the individual offers are known. As our first main result we show that a deterministic threshold strategy using the monopoly price of the distribution of the maximum value is asymptotically optimal assuming that the expectation of the maximum value grows sublinearly in n n . In our second main result, we further tighten this bound by deriving a tight quadratic convergence guarantee for sufficiently smooth distributions of the maximum value. Our results also give rise to a more fine-grained picture regarding prophet inequalities with correlated values, for which distribution-free bounds only yield a performance guarantee of the order 1 / n 1/n . 1 Introduction We study an optimal stopping problem where a seller has a single item for sale and sequentially receives n offers (v_{1},\dots,v_{n}) from potential buyers. When an offer is received, the seller must decide whether to accept the offer, and thereby passing up all future offers, or reject the offer and continue to the next one. The goal is to maximise the (expected) value of the accepted offer, where the expectation is with respect to the randomness of the chosen stopping rule and distributional information regarding the offer sequence (if any). When no distributional information about the sequence is known, but only its length n , it is folklore that the best stopping rule is to choose one of the n points in the sequence uniformly at random as stopping point. This rule yields, in expectation over the randomness of the stopping rule, at least 1/n times the (actual) maximum offer value. When the offer values are drawn from a (possibly correlated) known joint distribution, Hill and Kertz hill1983stop show that the best one can hope for is a stopping rule that yields an expected stopping value of the order \mathbb{E}[X_{\max}]/n , with X_{\max} the maximum value of the sequence, if no further assumptions are made about the joint distribution; this is known as a correlated prophet inequality result. There is a plethora of work on prophet inequalities, especially when the values of the offers are not correlated, but independent. We discuss the prophet inequality literature more extensively in Section 1.2 . Most relevant for us are recent works in which more structured correlations models have been explored in the context of prophet inequalities. Immorlica et al. immorlica2023prophet consider a linear correlation model and show that the competitive ratio degrades gradually with increasing correlation. Livanos et al. livanos2024improved obtain similar results for offers with graphical dependence. These results seem to suggest that it is correlation that degrades the competitive ratio. We provide a more nuanced perspective, namely that correlation only degrades the performance when the maximum offer behaves pathologically. We therefore consider a new model, where instead of making assumptions about the correlation structure, we assume distributional knowledge about the maximum offer value. This is arguably a more realistic assumption than knowing the complete correlation structure, since correlations are difficult to estimate from data. This difficulty arises, because specifying correlations often requires many parameters and the correlation structure may change over time. Furthermore, only partial information, like the highest offer, may be available. In contrast, the distribution of the maximum offer is often much easier to estimate from historical data or could more easily be approximated by an expert, making our model more robust and practical to use. The goal is now to quantify the worst-case correlation structure whose maximum offer value follows the chosen distribution, against the best (randomised) stopping rule. That is, we first choose a stopping rule after which our adversary nature may choose the worst-case correlation structure against this rule. More formal, we want to solve the sup-inf problem \sup_{\tau\in\mathcal{T}}\inf_{\boldsymbol{X}\in\mathcal{I}(F,n)}\mathbb{E}[\boldsymbol{X}_{\tau}], where \mathcal{T} is the set of all randomised stopping rules, and \mathcal{I}(F,n) the set of all joint distributions over sequences of n values (v_{1},\dots,v_{n}) where the maximum of the sequence follows F ; such a distribution is denoted by \mathbf{X} . We emphasise that the distribution F is allowed to depend on n . Finally, \mathbf{X}_{\tau} is the random offer value at which we stop. Formal definitions are given in Section 2 . For clarity, we will give an example of what instances in \mathcal{I}(F,n) might look like. Example 1.1 . Suppose the distribution F=F_{\max} is given by \mathbb{P}(X_{\max}=1)=1/2 and \mathbb{P}(X_{\max}=2)=1/2 , and that n=4 . Then example elements (i.e., correlation structures) in \mathcal{I}(F,n) are given in Table 1 . Instance v_{\max} Probability (0,1,1,0) 1 \frac{1}{2} (2,0,1,1) 2 \frac{1}{4} (0,1, \frac{3}{2} ,2) 2 \frac{1}{4} Instance v_{\max} Probability (0,1,0,1) 1 \frac{1}{3} (1,0,0, \frac{1}{2} ) 1 \frac{1}{6} (2,0,0,2) 2 \frac{1}{2} Table 1 : Two examples of elements \mathbf{X}\in\mathcal{I}(F,n) with \mathbb{P}(X_{\max}=1)=\frac{1}{2} and \mathbb{P}(X_{\max}=2)=\frac{1}{2} . It turns out that the above sup-inf problem is equivalent to its inf-sup variant (by an application of the Von Neumann-Fan theorem; see Theorem 2.1 ), i.e., \sup_{\tau\in\mathcal{T}}\inf_{\boldsymbol{X}\in\mathcal{I}(F,n)}\mathbb{E}[\boldsymbol{X}_{\tau}]=\inf_{\boldsymbol{X}\in\mathcal{I}(F,n)}\sup_{\tau\in\mathcal{T}}\mathbb{E}[\boldsymbol{X}_{\tau}]. Because, for fixed n , the quantity \mathbb{E}[X_{\max}] is constant, if we assume the expectation of X_{\max} is finite, the inf-sup problem is equivalent to \inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\sup_{\tau\in\mathcal{T}}\;\frac{\mathbb{E}[\boldsymbol{X}_{\tau}]}{\mathbb{E}[X_{\max}]}. This is called a prophet inequality problem as it compares the expected payoff of a stopping rule against that of a “prophet” who knows the complete value sequence and can always stop at the maximum value. 1.1 Our contributions The main goal of our work is to understand the sup-inf problem above, which is formally stated in ( 2.3 ) in the next section. As a preliminary result, we show in Theorem 2.4 that the optimal deterministic stopping rule is a static threshold whose value is the monopoly price p^{*}=\text{argmax}_{p\geq 0}\;p\cdot\mathbb{P}(X_{\max}\geq p)=:\text{argmax}_{p\geq 0}\;\Pi(p). That is, we select the first offer whose value exceeds p^{*} . Under this stopping rule, the expected value of the sup-inf problem is equal to \Pi^{*}(F_{\max}):=p^{*}\cdot\mathbb{P}(X_{\max}\geq p^{*}), i.e., \Pi^{*}(F_{\max})=\sup_{\tau\in\mathcal{D}}\inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\mathbb{E}[\boldsymbol{X}_{\tau}], where \mathcal{D} is the set of all deterministic stopping rules. Motivated by Theorem 2.4 , we want to understand whether or not we can obtain a higher expected value by using a randomised stopping rule from \mathcal{T} . Determining the exact randomized stopping rule that maximizes the expected offer value at which we stop seems rather difficult and cumbersome. Therefore, we instead aim for bounds on the performance of randomized algorithms that capture their potential. In Section 3 we show in Theorem (a) that, under a mild differentiability assumption on the cumulative distribution function of F_{\max} , there exists a randomised stopping rule that outperforms the best deterministic strategy. In contrast, we show in Theorem (b) that for any F_{\max} , \left(\Pi^{*}(F_{\max})\leq\;\right)\;\;\sup_{\tau\in\mathcal{T}}\inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\mathbb{E}[\boldsymbol{X}_{\tau}]\leq\Pi^{*}(F_{\max})+\frac{\mathbb{E}[X_{\max}]}{n}. This means that as long as the expectation of X_{\max} grows sublinearly, the advantage of randomization disappears as n grows large. We regard this to be a reasonable assumption on X_{\max} . 1 1 1 A notable exception to this assumption could be the case in which the market of buyers represents a “stock market bubble” in which the maximum value for an item increases steeply as more buyers become interested in it. In Section 4 we tighten the results of Section 3 for distributions F_{\max} that are sufficiently smooth. In particular, we show in Theorem 4.1 that if F_{\max} is three times differentiable around p^{*} and independent of n , then \left(\Pi^{*}(F_{\max})\leq\;\right)\;\;\sup_{\tau\in\mathcal{T}}\inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\mathbb{E}[\boldsymbol{X}_{\tau}]\leq\Pi^{*}(F_{\max})+\Theta\left(n^{-2}\right). Well-known parametric distributions such as the exponential, (half)-normal, and gamma distribution satisfy the conditions of Theorem 4.1 . Finally, in Section 5 we investigate natural conditions on F_{\max} under which the prophet inequality inf-sup problem \inf_{\boldsymbol{X}\in\mathcal{I}(F,n)}\sup_{\tau\in\mathcal{T}}\;\mathbb{E}[\boldsymbol{X}_{\tau}]/\mathbb{E}[X_{\max}] yields a lower bound better than of the order 1/n , when F_{\max} is itself allowed to depend on n . Mechanism design implications. In all our results, the static monopoly threshold p^{*} arises (roughly speaking) as the asymptotically optimal stopping rule. From a mechanism design point of view this also has desirable implications. Consider the online mechanism design setting where we interpret the threshold as a price for the item, and the offer from a potential strategic buyer as the price they are willing to pay for it. When using a fixed threshold as selling price, an example of a so-called posted price mechanism , buyers have no incentive to misreport their (true) value for the item as this can never increase their utility (which is the maximum of their true value minus the paid price if they get the item, and zero otherwise). Such posted price mechanisms have close connections with prophet inequalities see, e.g., hajiaghayi2007automated ; chawla2010multi ; correa2019pricing . Our techniques. To establish our lower bound results, it turns out that we can employ stopping rules with uniformly random thresholds, i.e., we randomly choose a threshold from a given interval and accept the first offer exceeding that threshold. Such policies are analytically tractable and allow us to characterise the worst-case (increasing) value sequences against such a stopping policy. To make the computation of the expected stopping value under these worst-cases sequences tractable, we use (in Section 4 ) a Taylor approximation of the maximum value distribution, which is possible because the random threshold is chosen from a small interval surrounding p^{*} . For the upper bounds, we construct worst-case instances by partitioning the support of X_{\max} into n intervals. We then bound the expected payoff by factoring out the stopping rule, yielding a bound in terms of the partition only. Determining the optimal partition comes, roughly speaking, down to an application of the intermediate value theorem in Section 3 . In Section 4 we need a highly non-trivial recursive construction to determine the optimal partition. This construction (to be found in Appendix C ) might be of independent interest. 1.2 Related work The sup-inf stopping problem above can be interpreted as a robust stopping problem, in the sense that we first choose a stopping rule, after which our adversary nature chooses a worst-case correlation structure adhering to our choice of maximum value distribution. Boshuizen and Hill boshuizen1992moment consider a setting in which the offer values are independently distributed. Each offer comes from an unknown distribution of which only the mean and variance are known (the set of distributions adhering to the given mean and variance is called the mean-variance ambiguity set ). The goal is to design a stopping rule that maximizes the seller’s expected payoff assuming nature chooses a worst-case distribution adhering to the chosen means and variances. Kleer and Van Leeuwaarden kleer2022optimalstoppingtheorydistributionally generalize this setting to arbitrary ambiguity sets for the independent offers. (These problems can also be interpreted as robust Markov decision processes in the sense of, e.g., iyengar2005robust .) In both works boshuizen1992moment ; kleer2022optimalstoppingtheorydistributionally , the authors explicitly determine the optimal stopping rule, which has for every offer a threshold value for accepting it. These thresholds can be computed by means of a backward recursion. This results in a deterministic optimal stopping rule, as opposed to our worst-case correlated setting, where in most cases randomized stopping rules are optimal. The (in terms of value) equivalent inf-sup problem is closely related to the literature on prophet inequalities, where the complete correlation structure of the values is assumed to be known. Hill and Kertz hill1983stop show that without any further assumptions on the (known) correlation structure \sup_{\tau\in\mathcal{T}}\;\mathbb{E}[\boldsymbol{X}_{\tau}]/\mathbb{E}[X_{\max}]=\Theta(1/n) . 2 2 2 We write f(x)=O(g(x)) if f(x)\leq cg(x) for some constant c and all x , and f(x)=\Omega(g(x)) if f(x)\geq cg(x) for some constant c and all x . We write f(x)=\Theta(g(x)) if c_{1}g(x)\leq f(x)\leq c_{2}g(x) for constants c_{1},c_{2} and x\geq 0 . At the other extreme, if the offer values are completely independent, Krengel, Sucheston and Garling krengel1978semiamarts show that there is a 1/2 -competitive policy, i.e., \sup_{\tau\in\mathcal{T}}\;\mathbb{E}[\boldsymbol{X}_{\tau}]/\mathbb{E}[X_{\max}]\geq 1/2 . Samuel-Cahn samuel1984comparison showed that this guarantee can be achieved with a static threshold policy using as threshold the median of the distribution of the maximum of the independent values. Kleinberg and Weinberg kleinberg2012matroid showed that this guarantee can also be achieved with as threshold half the expectation of the maximum value. Our optimal policy is similar to these optimal policies, in the sense that both are static threshold policies based on the maximum value distribution. The advantage of the Kleinberg-Weinberg threshold for independent values is that it can be generalized to the setting where multiple offers can be accepted subject to a combinatorial matroid constraint; related to such multi-selection problems is also the setting of online combinatorial auctions , see, e.g., the recent work by Cristi and Correa correa2023constant , and references therein. The competitive guarantee of 1/2 can be improved under the additional assumption that the values are all drawn from the same distribution (the i.i.d. setting). For the case where the common distribution is known, Correa et al. correa2017posted have solved this problem by establishing a tight 0.745 competitive ratio. This result is generalised in correa2022prophet , by considering the setting of an unknown common distribution from which only a limited number of samples are available. For further literature with only sample access to the distribution, we refer to the recent work of Cristi and Ziliotto cristi2024prophet , and references therein. If the base distribution does not depend on n , Kennedy and Kertz kennedy1991asymptotic show that 0.745 can be beaten, and Correa et al. correa2021optimal show that there are also better threshold policies. To sensibly define this problem they make extreme value theory assumptions. For our problem such assumptions result in the monopoly price threshold being asymptotically optimal, since it implies smoothness and sublinear growth of \mathbb{E}[X_{\max}] (that we require for our results in Section 3 and 4 ). There are also works that interpolate between these two extremes of no dependence restrictions and independence. Immorlica et al. immorlica2023prophet consider a linear correlations model, where the n offers are random variables \mathbf{X}=(X_{1},\dots,X_{n}) which are a linear combination of m independent non-negative random variables \boldsymbol{Y}=(Y_{1},\dots,Y_{m}) , via \boldsymbol{X}=A\boldsymbol{Y} with A a non-negative matrix. Crucial to their work are the row-sparsity s_{\text{row}} , the maximum number of features Y_{j} that influence any offer X_{i} , and the column-sparsity s_{\text{col}} , the maximum amount offers X_{i} influenced by any feature Y_{j} . Their main result is that even with full knowledge of A and the distribution of \boldsymbol{Y} , no online algorithm can recover more than a fraction O(1/\min\{s_{\text{row}},s_{\text{col}})\}) of the maximum. This result therefore interpolates between the two extremes of independent and fully correlated values. Livanos et al. livanos2024improved obtain similar interpolation results for models graphical dependencies Caragiannis et al. caragiannis2021relaxing consider prophet inequalities with pairwise independent offer values, thereby also relaxing the independence assumption. The above exposition of prophet inequality literature is not meant to be exhaustive. We also refer to reader to, e.g., the survey of Lucier lucier2017economic for further prophet-related settings. Finally, in the context of revenue maximization in auction design there is also a line of work gravin2018 ; bei2019correlation ; babaioff2020escaping building on the correlation-robust framework of Carroll carroll2017robustness in which the seller has marginal distributional information about the items, but not about their correlation structure. Such settings might also be interesting to study in the context of online stopping. 2 Model We consider the problem where n unknown values v_{1},\dots,v_{n} are revealed sequentially. When a value is revealed an irrevocable decision has to be made whether to accept it, disregarding all future values, or continue to the next value. An algorithm for deciding at which value to stop is called a stopping rule (or policy). A randomised stopping rule \tau is a collection of functions (\tau_{i})_{i=1,\dots,n} , where \tau_{i} is a Bernoulli random variable that takes as inputs v_{1},\dots,v_{i} . Based on this input, the function \tau_{i} selects value v_{i} with probability r_{i}(v_{1},\dots,v_{i}) . To be precise, we have \displaystyle\tau_{i}(v_{1},\dots,v_{i})=\begin{cases}1,&\text{ w.p. }r_{i}(v_{1},\dots,v_{i}),\\ 0,&\text{ w.p. }1-r_{i}(v_{1},\dots,v_{i}),\end{cases} for i=1,\dots,n . This means that the probability offer i is selected is given by \displaystyle\mathbb{P}(\tau=i\ |\ v_{1},\dots,v_{i})=r_{i}(v_{1},\dots,v_{i})\prod_{j=1}^{i-1}(1-r_{j}(v_{1},\dots,v_{j})). A stopping rule is called deterministic if r_{i}(v_{1},\dots,v_{i})\in\{0,1\} for all (v_{1},\dots,v_{i}) and i , so for deterministic stopping rules \mathbb{P}(\tau=i|v_{1},\dots,v_{i})\in\{0,1\} . Randomised stopping rules are therefore a mixture, that is a convex combination, of deterministic stopping rules. We write \boldsymbol{v}_{\tau}:=\sum_{i=1}^{n}v_{i}\cdot\mathbb{P}(\tau=i|v_{1},\dots,v_{i}) for the expected value of the offer that the stopping rule \tau selects on the fixed tuple \boldsymbol{v} . Maximum value knowledge. We consider an optimal stopping problem with distributional knowledge about the maximum value of the sequence (v_{1},\dots,v_{n}) . Specifically, we assume that the tuple of values (v_{1},\dots,v_{n}) is the realization of a nonnegative random vector \mathbf{X}=(X_{1},\dots,X_{n}) that follows a joint distribution F_{\mathbf{X}} which we assume is given as a (joint) cumulative distribution function (CDF). We do not assume to know this joint distribution, but, instead, only the distribution F_{\max} of \max_{1\leq i\leq n}X_{i} . For a given F_{\max} , we denote with \mathcal{I}(F_{\max},n) the set of all joint distributions over n values whose maximum value follows F_{\max} , i.e., \displaystyle\mathcal{I}(F_{\max},n)=\{F_{\boldsymbol{X}}:\mathbb{R}^{n}_{+}\to[0,1]\;|\;F_{\boldsymbol{X}}\text{ a CDF and }\max_{1\leq i\leq n}\{X_{i}\}\sim F_{\max}\}. (2.1) With a slight abuse of notation, we sometimes write \boldsymbol{Y}\in\mathcal{I}(F,n) to indicate that the joint distribution F_{\mathbf{Y}} of \mathbf{Y} is in \mathcal{I}(F,n) . Fundamental in the optimal stopping problem with maximum value knowledge is the revenue function \Pi(p)=p\cdot\mathbb{P}(X_{\max}\geq p), where X_{\max} is a random variable with distribution F_{\max} . This notation will be used throughout. With the revenue function we can define the monopoly price of F_{\max} as \displaystyle p^{*}=\underset{p\geq 0}{\mathrm{argmax}}\{\Pi(p)\}\text{ with }\Pi^{*}=\Pi(p^{*}). (2.2) The monopoly price will be ubiquitous in our analysis. For a given distribution F_{\max} and set of admissible stopping rules \mathcal{T} , which without further specification is the set of randomised stopping rules, we want to find the stopping rule \tau\in\mathcal{T} that solves \displaystyle V^{*}(F_{\max},n):=\sup_{\tau\in\mathcal{T}}\inf_{F_{\boldsymbol{X}}\in\mathcal{I}(F_{\max},n)}\int_{R^{n}_{+}}\boldsymbol{v}_{\tau}\mathrm{d}F_{\boldsymbol{X}}(\boldsymbol{v})=\sup_{\tau\in\mathcal{T}}\inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\mathbb{E}[\boldsymbol{X}_{\tau}]. (2.3) That is, we first choose a stopping rule \tau , after which our adversary nature chooses a worst-case joint distribution from \mathcal{I}(F_{\max},n) whose maximum value follows F_{\max} . We then consider the expected performance of the stopping rule \tau under a tuple of values drawn from the worst-case distribution/instance, and the possible randomness of \tau . 2.1 Minimax equality The maximin problem described in ( 2.3 ) yields the same value as the minimax problem \displaystyle\inf_{\boldsymbol{X}\in\mathcal{I}(F,n)}\sup_{\tau\in\mathcal{T}}\mathbb{E}[\boldsymbol{X}_{\tau}] (2.4) This follows from the Von Neumann-Fan minimax theorem, as we illustrate in Theorem 2.1 . The proof is deferred to Appendix A . Theorem 2.1 . With \mathcal{T} the set of all randomised stopping rules, and \mathcal{I}(F,n) the set of all joint distributions over n values whose maximum follows F , we have \displaystyle\sup_{\tau\in\mathcal{T}}\inf_{\boldsymbol{X}\in\mathcal{I}(F,n)}\mathbb{E}[\boldsymbol{X}_{\tau}]=\inf_{\boldsymbol{X}\in\mathcal{I}(F,n)}\sup_{\tau\in\mathcal{T}}\mathbb{E}[\boldsymbol{X}_{\tau}]. (2.5) The intuition underlying Theorem 2.1 is that we do not impose any further restrictions on joint distributions X\in\mathcal{I}(F,n) , i.e., arbitrary correlations between values are allowed. This results in the set \mathcal{I}(F,n) being convex. This contrasts with settings that restrict correlation. Let \tilde{\mathcal{I}}(F,n)\subset\mathcal{I}(F,n) satisfy the additional condition that the joint distributions are a product distribution, meaning that the X_{i} are assumed to be independent, then \tilde{\mathcal{I}}(F,n) is (in general) not convex. Example 2.2 . Let F\sim\mathrm{Bernoulli}(\frac{1}{2}) and X_{i}\sim\mathrm{Bernoulli}(\frac{1}{2}) , then two independent instances in \tilde{\mathcal{I}}(F,2) are (0,X_{1}) and (X_{2},0) . Let the instance (Y_{1},Y_{2}) be a mixture which is the first instance with probability \frac{1}{2} and the second instance with probability \frac{1}{2} , then (Y_{1},Y_{2})=\begin{cases}(0,0),&\text{w.p. }\frac{1}{2},\\ (0,1),&\text{w.p. }\frac{1}{4},\\ (1,0),&\text{w.p. }\frac{1}{4}.\end{cases} We have that \max\{Y_{1},Y_{2}\}\sim F , but \mathbb{P}(Y_{1}=0)=\frac{3}{4} and \mathbb{P}(Y_{1}=0|Y_{2}=0)=\frac{2}{3} , so Y_{1} and Y_{2} are not independent. Therefore (Y_{1},Y_{2})\notin\tilde{\mathcal{I}}(F,2) . 2.2 Deterministic stopping rules Here we consider the setting where the set of admissible stopping rules is the set of deterministic stopping rules. A natural subset of deterministic stopping rules are (deterministic) threshold policies, which accept the first value exceeding a fixed threshold. Definition 2.3 (Deterministic threshold policy) . A threshold policy \tau with deterministic threshold t has the following stopping rule: \displaystyle\tau_{i}(v_{1},\dots,v_{i}) \displaystyle=\mathbbm{1}\!\!\left\{v_{i}\geq t\right\}\text{ for }i=1,\dots,n. We establish that a threshold policy is the best deterministic policy in Theorem 2.4 . Theorem 2.4 . For n\geq 2 the optimal deterministic stopping rule has a payoff of \Pi^{*}(F_{\max}) and is a threshold policy with the monopoly price as threshold. Proof. Let \mathcal{I}(p) denote the following family of instances (v_{1},\dots,v_{n})=\begin{cases}(p,v_{\max},0,\dots,0),&\text{ if }v_{\max}\geq p,\\ (v_{\max},0,0,\dots,0),&\text{ if }v_{\max}0 arbitrarily and choose x=x(\delta) with r_{1}(x)=1 , such that \mathbb{P}(\{v_{1}:v_{1}\leq x\text{ and }r_{1}(x)=1\})\leq\delta . Now for the instances \mathcal{I}(x) the payoff is at most x\cdot\mathbb{P}(X_{\max}\geq x)+x\cdot\delta\leq\Pi^{*}+x\cdot\delta . Letting \delta\to 0 yields the desired result, as x(\delta) can be chosen as a decreasing function of \delta . ∎ 3 Bounds for randomised stopping rules Deterministic stopping rules are not always optimal. For example, consider the case where n=2 and X_{\max} has an exponential distribution with mean 1 , i.e., its CDF is F(x)=1-e^{-x} for x\geq 0 . Then the worst-case expected value obtained by setting the monopoly price as a (deterministic) threshold is \Pi^{*}(F_{\max})=\frac{1}{e} , but picking one of the two values uniformly at random has an expected payoff of \frac{1}{2} , so here randomization clearly helps. In this section, we provide a natural condition under which a randomised stopping rule strictly outperforms any deterministic stopping rule. Additionally, we establish a universal upper bound on V^{*}(F_{\max},n) that shows this improvement is typically only marginal. These findings are Theorems (a) and (b) , respectively. For ease of readability, we repeat the definitions of \Pi^{*} and V^{*} in the theorem statements. Theorem 3.1 . Let n\in\mathbb{N} and let F_{\max} be a given probability distribution (possibly depending on n ). Define \Pi^{*}(F_{\max})=\max_{p\geq 0}p\cdot\mathbb{P}(X_{\max}\geq p)=p^{*}\cdot\mathbb{P}(X_{\max}\geq p^{*}) as the worst-case expected value of threshold algorithm using monopoly price p^{*} , and V^{*}(F_{\max},n)=\sup_{\tau\in\mathcal{T}}\inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\mathbb{E}[\boldsymbol{X}_{\tau}] the worst-case expected payoff of the optimal randomised rule for sequences of n (correlated) values whose maximum follows F_{\max} . (a) If F_{\max} is differentiable at p^{*} then V^{*}(F_{\max},n)>\Pi^{*}(F_{\max}) . (b) For any F_{\max} , the following upper bound holds: V^{*}(F_{\max},n)\leq\Pi^{*}(F_{\max})+\frac{\mathbb{E}[X_{\max}]}{n}. Theorem (a) is not true without any condition on F_{\max} . This is illustrated in the following lemma, where we show that that for discrete distributions with at most n support points, the monopoly price threshold algorithm remains optimal, even among all randomised stopping rules. Lemma 3.2 . If X_{\max} has at most n support points, then V^{*}(F_{\max},n)=\Pi^{*}(F_{\max}) with V^{*}(F_{\max},n) and \Pi^{*}(F_{\max}) as in Theorem 3.1 . Proof. Denote the support points of X_{\max} by x_{1}\leq\dots\leq x_{n} and suppose nature chooses for i=1,\dots,n the tuple (x_{1},\dots,x_{i},0,\dots,0) with probability \mathbb{P}(X_{\max}=x_{i}) . Then clearly the maximum of the tuple values follows the distribution F_{\max} , i.e., the distribution over the sequences is contained in \mathcal{I}(F_{\max},n) . The expected payoff can then be bounded by \displaystyle V^{*}(F_{\max},n) \displaystyle=\sum_{j=1}^{n}\mathbb{P}(X_{\max}=x_{j})\sum_{i=1}^{j}x_{i}\mathbb{P}(\tau=i|x_{1},\dots,x_{i}) \displaystyle=\sum_{i=1}^{n}\mathbb{P}(\tau=i|x_{1},\dots,x_{i})\sum_{j=i}^{n}x_{i}\mathbb{P}(X_{\max}=x_{j}) \displaystyle=\sum_{i=1}^{n}\mathbb{P}(\tau=i|x_{1},\dots,x_{i})\cdot x_{i}\mathbb{P}(X_{\max}\geq x_{i}) \displaystyle\leq\sum_{i=1}^{n}\mathbb{P}(\tau=i|x_{1},\dots,x_{i})\cdot\Pi^{*}(F_{\max})\leq\Pi^{*}(F_{\max}). In the last step we use the fact that the probabilities of stopping add up to at most 1 . Lastly, by Theorem 2.4 V^{*}(F_{\max},n)\geq\Pi^{*}(F_{\max}) , as deterministic stopping rules are a subset of randomised stopping rules, so V^{*}(F_{\max},n)=\Pi^{*}(F_{\max}) ∎ 3.1 Non-optimality deterministic stopping rules In this section we prove Theorem (a) , i.e., we show that, under a natural condition, randomised stopping rules can outperform deterministic ones. We do this by using a randomised threshold policy as defined in Definition 3.3 . Such a policy chooses a threshold at random according to a given distribution, and then selects the first value that exceeds the threshold. Structural properties of worst-case instances under random threshold policies are established in Lemmas 3.4 and 3.5 . Using these lemmas, the payoff for a class of simple random threshold policies is then computed in Lemma 3.6 , from which Theorem (a) follows directly. Definition 3.3 (Random threshold policy) . A random threshold policy \tau with the random variable T , with distribution G , as threshold has the following stopping rule: \displaystyle\tau_{i}(v_{1},\dots,v_{i};T) \displaystyle=\mathbbm{1}\!\!\left\{v_{i}\geq T\right\}\text{ for }i=1,\dots,n. When a random threshold policy is used not all instances need to be considered. Specifically, we only need to consider instances with increasing values restricted to the support of the random threshold. In the following two lemmas this is formalised and proven. Lemma 3.4 . If the stopping rule is a random threshold policy, then for a given realization v_{\max} of X_{\max} and instance (w_{1},\dots,w_{n}) , there exists an instance (v_{1},\dots,v_{n}) with v_{1}<\dots0 . Pick \varepsilon\geq 0 and let the random threshold be t_{i}=p^{*}-(n-i)\varepsilon with probability p_{i}=\frac{1}{n} for i=1,\dots,n . The case \varepsilon=0 corresponds to a deterministic policy using the monopoly price p^{*} as a (static) threshold. By Lemma 3.6 the expected payoff is at least \tilde{\Pi}(\varepsilon)=\frac{1}{n}\sum_{i=0}^{n-1}\Pi(p^{*}-i\varepsilon)+\frac{\varepsilon}{n}\mathbb{P}(X_{\max}\geq p^{*}+\varepsilon), where the third term, which is non-negative, is dropped. Now \tilde{\Pi}(0)=\Pi(p^{*}) , so \tilde{\Pi}^{\prime}(0)>0 implies that there exists an \varepsilon such that \tilde{\Pi}(\varepsilon)>\tilde{\Pi}(0) , proving the statement in Theorem (a) . We complete the proof by showing \tilde{\Pi}^{\prime}(0)>0 : \displaystyle\tilde{\Pi}^{\prime}(0) \displaystyle=\lim_{\varepsilon\to 0}\frac{1}{\varepsilon}(\tilde{\Pi}(\varepsilon)-\tilde{\Pi}(0))=\lim_{\varepsilon\to 0}\frac{1}{\varepsilon}\left(\frac{\varepsilon}{n}\mathbb{P}(X_{\max}\geq p^{*}+\varepsilon)+\frac{1}{n}\sum_{i=1}^{n}\left(\Pi(p^{*}-i\varepsilon)-\Pi(p^{*})\right)\right) \displaystyle=\frac{1}{n}\mathbb{P}(X_{\max}\geq p^{*})+\frac{1}{n}\lim_{\varepsilon\to 0}\sum_{i=1}^{n}(-i)\frac{\left(\Pi(p^{*}-i\varepsilon)-\Pi(p^{*})\right)}{-i\varepsilon} \displaystyle=\frac{1}{n}\mathbb{P}(X_{\max}\geq p^{*})+\frac{1}{n}\sum_{i=1}^{n}(-i)\underbrace{\lim_{\varepsilon\to 0}\frac{\left(\Pi(p^{*}-i\varepsilon)-\Pi(p^{*})\right)}{-i\varepsilon}}_{=\Pi^{\prime}(p^{*})=0} \displaystyle=\frac{1}{n}\mathbb{P}(X_{\max}\geq p^{*})>0.\qed 3.2 Universal upper bound Theorem (b) is self-contained and relies on a clever instance that reveals little information, making all stopping rules ineffective. Proof of (b) . We prove it here for continuous F_{\max} , in Appendix B the general case is proven. Let w_{0} and w_{n} denote the lower and upper bound of the support of X_{\max} . Consider a sequence w_{0}w_{i},\\ t,&\text{if }t\in[w_{i-1},w_{i}],\\ 0,&\text{if }tj\Rightarrow\text{ zero payoff}) \displaystyle= \displaystyle\sum_{i=1}^{n}\int_{w_{i-1}}^{w_{i}}v_{i}(t)\mathbb{P}(\tau=i|v_{1}(t),\dots,v_{i}(t))\mathrm{d}F_{\max}(t) \displaystyle+ \displaystyle\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\int_{w_{j-1}}^{w_{j}}v_{i}(t)\mathbb{P}(\tau=i|v_{1}(t),\dots,v_{i}(t))\mathrm{d}F_{\max}(t) (Sum decomposition) \displaystyle= \displaystyle\sum_{i=1}^{n}\int_{w_{i-1}}^{w_{i}}t\mathbb{P}(\tau=i|b_{1},\dots,b_{i-1},t)\mathrm{d}F_{\max}(t) \displaystyle+ \displaystyle\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\int_{w_{j-1}}^{w_{j}}b_{i}\mathbb{P}(\tau=i|b_{1},\dots,b_{i})\mathrm{d}F_{\max}(t) \displaystyle\text{(Definition }v_{i}(t)) \displaystyle= \displaystyle\sum_{i=1}^{n}\int_{w_{i-1}}^{w_{i}}t\mathbb{P}(\tau=i|b_{1},\dots,b_{i-1},t)\mathrm{d}F_{\max}(t) \displaystyle+ \displaystyle\sum_{i=1}^{n-1}\mathbb{P}(\tau=i|b_{1},\dots,b_{i})\cdot b_{i}\mathbb{P}(X_{\max}\geq w_{i}). By construction, \mathbb{P}(\tau=i|b_{1},\dots,b_{i-1},t)\leq\mathbb{P}(\tau=i|b_{1},\dots,b_{i}) for t\in[w_{i-1},w_{i}] , therefore, \displaystyle\sum_{i=1}^{n}\int_{w_{i-1}}^{w_{i}}t\mathbb{P}(\tau=i|b_{1},\dots,b_{i-1},t)\mathrm{d}F_{\max}(t)+\sum_{i=1}^{n-1}\mathbb{P}(\tau=i|b_{1},\dots,b_{i})\cdot b_{i}\mathbb{P}(X_{\max}\geq w_{i}) \displaystyle\leq \displaystyle\sum_{i=1}^{n}\mathbb{P}(\tau=i|b_{1},\dots,b_{i})\int_{w_{i-1}}^{w_{i}}t\mathrm{d}F_{\max}(t)+\sum_{i=1}^{n-1}\mathbb{P}(\tau=i|b_{1},\dots,b_{i})\cdot b_{i}\mathbb{P}(X_{\max}\geq w_{i}) \displaystyle\leq \displaystyle\max_{1\leq i\leq n}\left\{\int_{w_{i-1}}^{w_{i}}t\mathrm{d}F_{\max}(t)\right\}+\max_{1\leq i\leq n-1}\left\{b_{i}\mathbb{P}(X_{\max}\geq w_{i})\right\} \displaystyle\leq \displaystyle\max_{1\leq i\leq n}\left\{\int_{w_{i-1}}^{w_{i}}t\mathrm{d}F_{\max}(t)\right\}+\max_{1\leq i\leq n-1}\left\{b_{i}\mathbb{P}(X_{\max}\geq b_{i})\right\}\ \ \ \ \ \ \ \ \ \ \ \ \ (\text{using }b_{i}\leq w_{i}) \displaystyle\leq \displaystyle\max_{1\leq i\leq n}\left\{\int_{w_{i-1}}^{w_{i}}t\mathrm{d}F_{\max}(t)\right\}+\Pi^{*}(F_{\max}). This bound on the expected payoff holds for an arbitrary stopping rule, so also an optimal stopping rule. Lastly, because F_{\max} is continuous, there exists, by the intermediate value theorem, w_{i} ’s such that \int_{w_{i-1}}^{w_{i}}t\mathrm{d}F_{\max}(t)=\frac{1}{n}\mathbb{E}[X_{\max}] , yielding the desired result. ∎ 4 Stronger lower and upper bounds The results of Theorem 3.1 can be made tighter if F_{\max} is sufficiently smooth. Specifically, we prove the following theorem. Theorem 4.1 . Let n\in\mathbb{N} and let F_{\max} be a given probability distribution independent of n . Define \Pi^{*}(F_{\max})=\max_{p\geq 0}p\cdot\mathbb{P}(X_{\max}\geq p)=p^{*}\cdot\mathbb{P}(X_{\max}\geq p^{*}) as the worst-case expected value of threshold algorithm using monopoly price p^{*} , and V^{*}(F_{\max},n)=\sup_{\tau\in\mathcal{T}}\inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\mathbb{E}[\boldsymbol{X}_{\tau}] the worst-case expected payoff of the optimal randomised stopping algorithm for sequences of n (correlated) values whose maximum follows F_{\max} . If p^{*} is unique and F_{\max} is three times continuously differentiable at p^{*} , then V^{*}(F_{\max},n)=\Pi^{*}(F_{\max})+\Theta(n^{-2}). The above result generalises to settings where X_{\max} depends on n through scaling. Corollary 4.2 . Let F_{\mathrm{base}} be a distribution that satisfies the properties of Theorem 4.1 . If \frac{X_{\max}}{\mathbb{E}[X_{\max}]}\sim F_{\mathrm{base}}, that is, X_{\max} depends on n through scaling, but retains the same shape, then V^{*}(F_{\max},n)=\Pi^{*}(F_{\max})+\Theta\left(\frac{\mathbb{E}[X_{\max}]}{n^{2}}\right). Proof. As shorthand, let s(n)=\mathbb{E}[X_{\max}] . From the definition of V^{*} it follows that it has homogeneity. \displaystyle V^{*}(F_{\max},n) \displaystyle=\sup_{\tau\in\mathcal{T}}\inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\mathbb{E}[\boldsymbol{X}_{\tau}]=\sup_{\tau\in\mathcal{T}}\inf_{\frac{1}{s(n)}\boldsymbol{X}\in\mathcal{I}(F_{\mathrm{base}},n)}\mathbb{E}[\boldsymbol{X}_{\tau}] \displaystyle=s(n)\sup_{\tau\in\mathcal{T}}\inf_{\frac{1}{s(n)}\boldsymbol{X}\in\mathcal{I}(F_{\mathrm{base}},n)}\mathbb{E}\left[\frac{1}{s(n)}\boldsymbol{X}_{\tau}\right]=s(n)V^{*}(F_{\mathrm{base}},n). By Theorem 4.1 , V^{*}(F_{\mathrm{base}},n)=\Pi^{*}(F_{\mathrm{base}})+\Theta(n^{-2}) , so using the homogeneity we obtain that V^{*}(F_{\max},n)=s(n)V^{*}(F_{\mathrm{base}},n)=s(n)\Pi^{*}(F_{\mathrm{base}})+\Theta\left(\frac{s(n)}{n^{2}}\right)=\Pi^{*}(F_{\max})+\Theta\left(\frac{\mathbb{E}[X_{\max}]}{n^{2}}\right).\qed In the above proof it is not important that F_{\mathrm{base}} does not depend on n , only that the assumptions of Theorem 4.1 are satisfied. The result can therefore be generalised to F_{\mathrm{base},n} that depend on n , by having the F_{\mathrm{base},n} satisfy the conditions of the theorem in a uniform sense. 3 3 3 We require that the distributional constants in Lemmas 4.3 and 4.4 are uniformly bounded, for example, the C(F_{\mathrm{base},n}) are uniformly bounded. Theorem 4.1 follows from Lemmas 4.3 and 4.4 . Both use the following distributional constant C(F_{\max})=\frac{(1-F_{\max}(p^{*}))^{2}}{2F_{\max}^{\prime}(p^{*})+p^{*}F_{\max}^{\prime\prime}(p^{*})}. Because p^{*} is the unique maximiser, the second order condition \Pi^{\prime\prime}(p)<0 informs us that 2F^{\prime}_{\max}(p^{*})+p^{*}F^{\prime\prime}_{\max}(p^{*})>0 , so C(F_{\max}) is positive and finite. We now state the two lemmas. Lemma 4.3 . If p^{*} is unique, \varepsilon=\frac{3(1-F_{\max}(p^{*}))}{2F_{\max}^{\prime}(p^{*})+pF_{\max}^{\prime\prime}(p^{*})}\frac{1}{n}<1 , and the third derivative of F_{\max} is bounded on (p^{*}-\varepsilon,p^{*}+\varepsilon) , then V^{*}(F_{\max},n)\geq\Pi^{*}(F_{\max})+\frac{3}{2}C(F_{\max})n^{-2}+O(n^{-3}). Lemma 4.4 . If p^{*} is unique and F_{\max} is three times continuously differentiable at p^{*} , then there are constants C_{1} and C_{2} which depend on F_{\max} , such that for n>\max\{C_{1},C_{2}\} , V^{*}(F_{\max},n)\leq\Pi^{*}(F_{\max})+2\pi^{2}C(F_{\max})(n-C_{2})^{-2}+O(n^{-3}). Lemmas 4.3 and 4.4 both rely on Taylor’s theorem, so we state it here for completeness. Lemma 4.5 (Taylor’s theorem; rudin1976principles ) . Let f be a real-valued function that is n times differentiable on the interval [a,b] and suppose \alpha,\beta\in[a,b] . Then there exists a point x between \alpha and \beta such that f(\beta)=\sum_{k=0}^{n-1}\frac{f^{(k)}(\alpha)}{k!}(\beta-\alpha)^{k}+\frac{f^{(n)}(x)}{n!}(\beta-\alpha)^{n}. 4.1 Lower bound What is remarkable about Lemma 4.3 is that it achieves the optimal asymptotic order using a simple uniform random threshold policy. In Lemma 4.6 we identify the optimal instance against this policy using a geometric argument, circumventing difficult first order conditions. The uniformity of the policy allows for this argument. Lemma 4.7 provides a lower bound on the expected payoff for this optimal instance. Lemma 4.3 then follows by applying Lemma 4.7 alongside Taylor’s theorem. Let us start with the crucial result, the optimal instance against a uniformly random policy. Lemma 4.6 . For a random threshold policy \tau with a threshold uniformly distributed on (t_{1},t_{2}) , the tuple (v_{1},\dots,v_{n}) that minimises the payoff, given v_{\max} , is • v_{1}=v_{\max} and v_{i}=0 for i>1 if v_{\max}t_{2}+\frac{t_{2}-t_{1}}{n-1} . Proof. Denote the CDF of the random threshold by F_{T} . The payoff given a tuple \boldsymbol{v} is \displaystyle\boldsymbol{v}_{\tau} \displaystyle=v_{1}\cdot\mathbb{P}(T\leq v_{1})+\sum_{i=2}^{n}v_{i}\mathbb{P}(v_{i-1}1 results in an expected payoff of zero, so it is optimal. For the other two cases Lemmas 3.4 and 3.5 inform us that there is an optimal tuple \boldsymbol{v} which satisfies t_{1}\leq v_{1}t_{2} (right) with n=5 . Observe that for a given v_{\max} the v_{i} ’s only influence the striped area. If v_{\max}\leq t_{2} the total area of these triangles is minimised if the v_{i} ’s for it_{2} the striped area is one quadrilateral and n-1 triangles. Given v_{n-1} the area of the triangles is minimised if the other v_{i} ’s have an equal spacing, that is, v_{i}=t_{1}+\frac{i}{n-1}(v_{n-1}-t_{1}) for it_{2}+\frac{t_{2}-t_{1}}{n-1}\right) \displaystyle\geq\mathbb{E}[f_{1}(X_{\max})\mathbbm{1}\!\!\left\{t_{1}\leq X_{\max}\leq t_{2}\right\}]+f_{2}(t_{2})\mathbb{P}\left(X_{\max}>t_{2}\right), where \displaystyle f_{1}(s)=\frac{s-t_{1}}{t_{2}-t_{1}}\left(t_{1}+\frac{n+1}{2n}(s-t_{1})\right)\text{ and }f_{2}(s)=s-\frac{n-1}{2n}\frac{(s-t_{1})^{2}}{t_{2}-t_{1}}. Proof. Denote the optimal v_{i} ’s from Lemma 4.6 , given v_{\max} , by \boldsymbol{v}^{*}(v_{\max}) . If v_{\max}t_{2}+\frac{t_{2}-t_{1}}{n-1} then \boldsymbol{v}_{\tau}^{*}(v_{\max})=\boldsymbol{v}_{\tau}^{*}(t_{2}) , since then v_{n-1}=t_{2} , so one of the first n-1 values is accepted. Taking the expectation yields the exact result. The lower bound result follows from the fact that f_{2} is an increasing function (higher v_{\max} means a higher payoff). Therefore, \displaystyle\mathbb{E}\left[f_{2}(X_{\max})\mathbbm{1}\!\!\left\{t_{2}\leq X_{\max}f_{2}\left(t_{2}+\frac{t_{2}-t_{1}}{n-1}\right)\mathbb{P}\left(X_{\max}\geq t_{2}+\frac{t_{2}-t_{1}}{n-1}\right) \displaystyle\geq \displaystyle\>\mathbb{E}\left[f_{2}(t_{2})\mathbbm{1}\!\!\left\{t_{2}\leq X_{\max}f_{2}\left(t_{2}\right)\mathbb{P}\left(X_{\max}\geq t_{2}+\frac{t_{2}-t_{1}}{n-1}\right) \displaystyle=\> \displaystyle f_{2}(t_{2})\mathbb{P}\left(X_{\max}\geq t_{2}\right).\qed We obtain an informative lower bound by using an appropriate Taylor series to the above result. Proof of Lemma 4.3 . Consider a random threshold that is uniform on (p^{*}-\varepsilon,p^{*}+\varepsilon) . Then the functions f_{i} as defined in Lemma 4.7 simplify to \displaystyle f_{1}(p^{*}+s) \displaystyle=\frac{s+\varepsilon}{2\varepsilon}\left(p^{*}-\varepsilon+\frac{n+1}{2n}(s+\varepsilon)\right), \displaystyle=\underbrace{\frac{1}{2}p^{*}-\frac{1}{2}\varepsilon+\frac{n+1}{4n}\varepsilon}_{a(\varepsilon)}+\underbrace{\left(\frac{p^{*}}{2\varepsilon}-\frac{1}{2}+\frac{n+1}{2n}\right)}_{b(\varepsilon)}s+\underbrace{\frac{n+1}{4n\varepsilon}}_{c(\varepsilon)}s^{2} \displaystyle f_{2}(p^{*}+\varepsilon) \displaystyle=p^{*}+\frac{\varepsilon}{n}. Moreover, Lemma 4.7 informs us that \displaystyle V^{*}(F_{\max},n) \displaystyle\geq\mathbb{E}[f_{1}(X_{\max})\mathbbm{1}\!\!\left\{p^{*}-\varepsilon\leq X_{\max}\leq p^{*}+\varepsilon\right\}]+f_{2}(p^{*}+\varepsilon)\mathbb{P}\left(X_{\max}>p^{*}+\varepsilon\right) \displaystyle=\int_{-\varepsilon}^{\varepsilon}(a(\varepsilon)+b(\varepsilon)s+c(\varepsilon)s^{2})F_{\max}^{\prime}(p^{*}+s)\mathrm{d}s+\left(p^{*}+\frac{\varepsilon}{n}\right)\left(1-F_{\max}(p^{*}+\varepsilon)\right). (4.1) Now, F^{\prime\prime\prime}_{\max}(p^{*}+s) exists for |s|\leq\varepsilon , because it is bounded, so by Taylor’s Theorem F^{\prime}_{\max}(p^{*}+s)=F^{\prime}_{\max}(p^{*})+F^{\prime\prime}_{\max}(p^{*})s+\frac{1}{2}F^{\prime\prime\prime}_{\max}(p^{*}+\xi(s))s^{2}, where \xi(s)\in(0,s) . Let M=\sup\{|F^{\prime\prime\prime}_{\max}(p^{*}+s)|:|s|\leq\varepsilon\} and notice that M\geq\sup\{|F^{\prime\prime\prime}_{\max}(p^{*}+\xi(s))|:|s|\leq\varepsilon\} and that M is bounded. Substituting the Taylor expansion into the first term of ( 4.1 ) yields \displaystyle\int_{-\varepsilon}^{\varepsilon}(a(\varepsilon)+b(\varepsilon)s+c(\varepsilon)s^{2})F_{\max}^{\prime}(p^{*}+s)\mathrm{d}s \displaystyle= \displaystyle\int_{-\varepsilon}^{\varepsilon}(a(\varepsilon)+b(\varepsilon)s+c(\varepsilon)s^{2})(F^{\prime}_{\max}(p^{*})+F^{\prime\prime}_{\max}(p^{*})s)\mathrm{d}s \displaystyle+ \displaystyle\int_{-\varepsilon}^{\varepsilon}(a(\varepsilon)+b(\varepsilon)s+c(\varepsilon)s^{2})\left(\frac{1}{2}F^{\prime\prime\prime}_{\max}(p^{*}+\xi(s))s^{2}\right)\mathrm{d}s. Integration reveals that the first term is equal to \displaystyle 2a(\varepsilon)F^{\prime}_{\max}(p^{*})\varepsilon+\frac{2}{3}\left(c(\varepsilon)F^{\prime}_{\max}(p^{*})+b(\varepsilon)F^{\prime\prime}_{\max}(p^{*})\right)\varepsilon^{3} \displaystyle= \displaystyle p^{*}F^{\prime}_{\max}(p^{*})\varepsilon+\left(\frac{2-n}{3n}F^{\prime}_{\max}(p^{*})+\frac{1}{3}p^{*}F^{\prime\prime}_{\max}(p^{*})\right)\varepsilon^{2}+O(\varepsilon^{3}). (4.2) The absolute value of the second term can be bounded as follows \displaystyle\left|\int_{-\varepsilon}^{\varepsilon}(a(\varepsilon)+b(\varepsilon)s+c(\varepsilon)s^{2})\left(\frac{1}{2}F^{\prime\prime\prime}_{\max}(p^{*}+\xi(s))s^{2}\right)\mathrm{d}s\right| \displaystyle\leq \displaystyle\int_{-\varepsilon}^{\varepsilon}(|a(\varepsilon)|+|b(\varepsilon)|\cdot|s|+|c(\varepsilon)|s^{2})\left|\frac{1}{2}F^{\prime\prime\prime}_{\max}(p^{*}+\xi(s))\right|s^{2}\mathrm{d}s \displaystyle\leq \displaystyle\frac{M}{2}\int_{-\varepsilon}^{\varepsilon}(|a(\varepsilon)|+|b(\varepsilon)|\cdot|s|+|c(\varepsilon)|s^{2})s^{2}\mathrm{d}s \displaystyle= \displaystyle M\left(\frac{1}{3}|a(\varepsilon)|\varepsilon^{3}+\frac{1}{4}|b(\varepsilon)|\varepsilon^{4}+\frac{1}{5}|c(\varepsilon)|\varepsilon^{5}\right). The above is O(\varepsilon^{3}) , since \varepsilon<1 , so it gets absorbed in the previous O(\varepsilon^{3}) term. Substituting the Taylor expansion into the second term of ( 4.1 ) yields \displaystyle\left(p^{*}+\frac{\varepsilon}{n}\right)\left(1-F_{\max}(p^{*}+\varepsilon)\right) \displaystyle= \displaystyle\left(p^{*}+\frac{\varepsilon}{n}\right)\left(1-F_{\max}(p^{*})-F_{\max}^{\prime}(p^{*})\varepsilon-\frac{1}{2}F_{\max}^{\prime\prime}(p^{*})\varepsilon^{2}+O(\varepsilon^{3})\right) \displaystyle= \displaystyle\Pi^{*}(F_{\max})-p^{*}(F_{\max}^{\prime}(p^{*})\varepsilon+\frac{1}{2}F^{\prime\prime}_{\max}(p^{*})\varepsilon^{2})+\frac{\varepsilon}{n}(1-F_{\max}(p^{*})-F_{\max}^{\prime}(p^{*})\varepsilon)+O(\varepsilon^{3}). (4.3) The sum of ( 4.2 ) and ( 4.3 ) gives the asymptotics of ( 4.1 ), \Pi^{*}(F_{\max})+\frac{1-F_{\max}(p^{*})}{n}\varepsilon-\frac{1}{6}\left(\frac{2n+2}{n}F_{\max}^{\prime}(p^{*})+p^{*}F_{\max}^{\prime\prime}(p^{*})\right)\varepsilon^{2}+O(\varepsilon^{3}). The above expression has a maximum at \varepsilon^{*}=\frac{3(1-F_{\max}(p^{*}))}{(2F_{\max}^{\prime}(p^{*})+pF_{\max}^{\prime\prime}(p^{*}))n+2F_{\max}^{\prime}(p^{*})} , but for simplicity we pick our \varepsilon=\frac{3(1-F_{\max}(p^{*}))}{2F_{\max}^{\prime}(p^{*})+pF_{\max}^{\prime\prime}(p^{*})}\frac{1}{n} . Substituting this \varepsilon into the above expression gives the result of the theorem. ∎ 4.2 Upper bound Lemma 4.4 relies on the same instance as Theorem (b) and with it we show in Lemma 4.8 that for a smart choice of w_{n-1} that V^{*}(F_{\max},n)\leq\max_{0\leq i\leq n-2}\{w_{i+1}\mathbb{P}(X_{\max}\geq w_{i})\} . Iteratively setting w_{i+1} such that w_{i+1}\mathbb{P}(X_{\max}\geq w_{i})=\Pi^{*}(F_{\max})+\varepsilon until w_{i+1} surpasses w_{n-1} ensures that V^{*}(F_{\max},n)\leq\Pi^{*}(F_{\max})+\varepsilon . Lemma 4.4 informs us which \varepsilon is possible for a given n . The technical arguments of Lemma 4.4 are in Appendix C . Let us first derive a general upper bound from Theorem (b) . Lemma 4.8 . Let w_{0} and w_{n} denote the lower and upper bound of the support of X_{\max} then for any sequence w_{0}0 will be chosen to have several nice properties. This is encapsulated in Lemma 4.9 below. Lemma 4.9 . Let M(t;\varepsilon):=\frac{\Pi^{*}+\varepsilon}{\mathbb{P}(X_{\max}\geq t)} , f(t;\varepsilon)=M(t;\varepsilon)-t and \bar{p}(\varepsilon) the minimiser of f . If F_{\max} is continuously differentiable at p^{*} , then there exist \varepsilon_{0}^{\prime}>0 and \delta>0 (independent of \varepsilon ) such that for \varepsilon<\varepsilon_{0}^{\prime} the following holds: M is increasing and continuous on (p^{*}-\delta,p^{*}+\delta) , and f is non-negative, decreasing on (p^{*}-\delta,\bar{p}(\varepsilon)] and increasing on [\bar{p}(\varepsilon),p^{*}+\delta) Proof. See Appendix C . ∎ We have to choose \delta in this way to later derive ( 4.5 ), moreover \delta can only be chosen this way if \varepsilon is small enough, therefore we require n to be larger than some constant C_{1} . Now, the first and third terms of ( 4.4 ) can be bounded by a simple argument. Observe that f(t;0)>0 if |t-p^{*}|>\delta for \delta>0 , so k(0,p^{*}-\delta;0)\leq 1+\frac{p^{*}-\delta}{\inf_{t\in[0,p^{*}-\delta]}\{f(t;\varepsilon)\}}<\infty. Analogously, k(p^{*}+\delta,\beta;0) can be bounded. The second term of ( 4.4 ) depends on \varepsilon and diverges as \varepsilon\to 0 , but we have the following result \lim_{\varepsilon\to 0}\varepsilon^{\frac{1}{2}}k(p^{*}-\delta,p^{*}+\delta;\varepsilon)\leq\sqrt{2\pi^{2}\frac{(1-F_{\max}(p^{*}))^{2}}{p^{*}F^{\prime\prime}_{\max}(p^{*})+2F^{\prime}_{\max}(p^{*})}}. (4.5) The proof of this statement is rather technical and therefore relegated to Lemma C.5 in the appendix. As a consequence of the above result, k(0,\beta;\varepsilon)\leq C_{2}+\sqrt{2}\pi\left(\frac{(1-F_{\max}(p^{*}))^{2}}{p^{*}F^{\prime\prime}_{\max}(p^{*})+2F^{\prime}_{\max}(p^{*})}\right)^{\frac{1}{2}}\varepsilon^{-\frac{1}{2}}, where C_{2}=k(0,p^{*}-\delta;0)+k(p^{*}+\delta,\beta;0) is a constant that does not depend on n . The above expression relates n , the left hand side, to the possible error. Rewriting yields that n points can attain an error of 2\pi^{2}\frac{(1-F_{\max}(p^{*}))^{2}}{2F^{\prime}_{\max}(p^{*})+p^{*}F^{\prime\prime}_{\max}(p^{*})}(n-C_{2})^{-2}, which proves the theorem. ∎ 5 Convergence and prophet inequalities In this section we will do two things. First, we will walk through a numerical example to highlight our results in Section 3 and 4 . Secondly, we compare the payoff of the online policy to the payoff of the offline optimum, namely, the expected value of the maximum value. This comparison is captured by the ratio r(F_{\max},n)=\frac{V^{*}(F_{\max},n)}{\mathbb{E}[X_{\max}]}. Without any assumptions regarding X_{\max} we cannot obtain meaningful results regarding the performance, because in hill1983stop it is shown that for any n there is a sequence of distributions F_{k,n} such that \lim_{k\to\infty}r(F_{k,n},n)=1/n . This demonstrates that the online policy can perform arbitrarily worse than the offline optimum. We will however show that r(F_{\max},n) has a lower bound independent of n under a natural assumption on X_{\max} . 5.1 Numerical example We will consider our results through the lens of an example. Let X_{\max}=\sqrt{n}X_{\mathrm{base}} , where X_{\mathrm{base}} has a Fréchet distribution with a mean of 1 and variance of 3 . The distribution function of X_{\mathrm{base}} is therefore given by F_{\text{base}}(x)=\exp\left(-\left(x/s\right)^{-\gamma}\right), with s=0.613 and \gamma=2.197 to have the prescribed mean and variance (in this section decimals are truncated to three places). The choice of a sublinear mean of X_{\max} is motivated by the idea that, while each additional buyer added to the market, that is, the group of all potential buyers, may increase the maximum valuation, the larger the market becomes the less likely it is that a new buyer will significantly raise the current maximum. The Fréchet distribution was chosen, because it belongs to the family of generalised extreme value (GEV) distributions. In extreme value theory, which concerns the study of the maximum of random variables, the GEV distribution is a key concept and is often used to model the distribution of maxima. This intersection between extreme value theory and prophet inequality type problems has already been observed before by kennedy1991asymptotic ; correa2021optimal ; livanos2024minimization . The distribution F_{\text{base}} has a unique monopoly price p^{*}=0.524 and is three times continuously differentiable at p^{*} . \Pi^{*}(F_{\max})=0.396\sqrt{n} , so by Corollary 4.2 V^{*}(F_{\max},n)=0.396\sqrt{n}+\Theta(n^{-3/2}) . In Figure 2 we have computed the precise bounds on V^{*}(F_{\max},n) by computing the constants of Lemmas 4.3 and 4.4 . 4 4 4 For Lemma 4.3 , \varepsilon=0.826<1 . For Lemma 4.4 , \beta=1.398 , there is no restriction on \delta , so C_{1}=1 , for \delta=0.1 we find C_{2}=10 . Lastly, C(F_{\mathrm{base}})=0.208 for both lemmas. Moreover, we have also computed the bound that results from Lemma 4.8 when the w_{i} ’s are chosen iteratively. 2 15 30 45 0 1 2 3 n V^{*}(F_{\max},n) Lemma 4.4 Lemma 4.8 Theorem (b) Lemma 4.3 300 600 900 0 1 2 3 4 5 n \Theta(n^{-3/2}) constant Lemma 4.4 Lemma 4.8 Lemma 4.3 Figure 2 : Explicit lower (blue) and upper (black) bounds on V^{*}(F_{\max},n) (left) and the constant associated with \Theta(n^{-3/2}) (right). We see that the gap between the lower and upper bounds of V^{*}(F_{\max},n) decreases very quickly, like we would expect from our results. We also observe that the constants associated with our lower and upper bound converge quickly, indicating that the asymptotic result kicks in early. 5.2 Prophet inequality Because V^{*}(F_{\max},n) is lower bounded by and converges to \Pi^{*}(F_{\max}) , it suffices to consider the ratio \Pi^{*}(F_{\max})/\mathbb{E}[X_{\max}] in order to establish a performance guarantee. As noted before, no non-trivial performance guarantees are possible without additional assumptions due to hill1983stop their result. However, the construction used to demonstrate this impossibility result is highly pathological. This is because the coefficient of variation of the maximum valuation, which is given by \mathrm{CV}(X_{\max})=\sqrt{\text{var}(X_{\max})}/\mathbb{E}[X_{\max}], tends to infinity in the construction. The construction would therefore imply that the market becomes increasingly volatile as it grows, which contradicts the standard economic intuition that larger markets tend to be more stable. This therefore motivates the assumption that \mathrm{CV}(X_{\max}) does not grow too strongly. The ratio between \Pi^{*}(F_{\max}) and \mathbb{E}[X_{\max}] has already been studied under limited distributional information, such as a known mean and maximal dispersion; see also, e.g., van2024robust for other choices of limited information. Tight (implicit) lower bounds for this ratio have been established in terms of the mean and variance. In particular, Lemma 2.3 in giannakopoulos2023robust shows that this ratio is asymptotically bounded from below by (1+\log(1+\mathrm{CV}(X_{\max})^{2}))^{-1} . We extend this result by providing a non-asymptotic lower bound of the same order, leading to the following result on the performance of the monopoly price threshold policy. Theorem 5.1 . Let n\in\mathbb{N} and \mu,\sigma>0 (possibly depending on n ). Suppose F_{\max} has mean \mu>0 and variance \sigma^{2} . Then for any \beta>1 , there exists a constant c(\beta) such that \inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\sup_{\tau\in\mathcal{T}}\;\frac{\mathbb{E}[\boldsymbol{X}_{\tau}]}{\mathbb{E}[X_{\max}]}\geq\left(c(\beta)+\beta\log\left(1+\frac{\sigma^{2}}{\mu^{2}}\right)\right)^{-1}. Proof. Let \mathcal{P}(\mu,\sigma) denote the set of distributions with mean \mu and variance \sigma^{2} . We have that \displaystyle\inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\sup_{\tau\in\mathcal{T}}\;\frac{\mathbb{E}[\boldsymbol{X}_{\tau}]}{\mathbb{E}[X_{\max}]} \displaystyle\geq\inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\frac{\mathbb{E}[\Pi^{*}(F_{\max})]}{\mathbb{E}[X_{\max}]} \displaystyle=\inf_{\boldsymbol{X}\in\mathcal{I}(F_{\max},n)}\sup_{p}\frac{p\cdot\mathbb{P}(X_{\max}\geq p)}{\mathbb{E}[X_{\max}]} \displaystyle\geq\inf_{X_{\max}\in\mathcal{P}(\mu,\sigma)}\sup_{p}\frac{p\cdot\mathbb{P}(X_{\max}\geq p)}{\mathbb{E}[X_{\max}]}. In chen2024screening an implicit expression for the final quantity is given under an additional support upper bound constraint. Letting this upper bound tend to infinity results in the following worst-case distribution for our problem F(x)=\begin{cases}0,&\text{if }x\leq\pi,\\ 1-\frac{\pi}{x},&\text{if }\pik,\end{cases} where \pi is the optimal value of p\cdot\mathbb{P}(X_{\max}\geq p) and solves \pi+\pi\log\left(\frac{k}{\pi}\right)=\mu and k is such that the variance is \sigma^{2} . The former condition yields k=\pi\exp\left(\frac{\mu}{\pi}-1\right) and the latter 2\pi k-\pi^{2}=\sigma^{2}+\mu^{2} . Taken together we obtain the following implicit expression, 2z^{2}\exp\left(z^{-1}-1\right)-z^{2}=1+\frac{\sigma^{2}}{\mu^{2}}, where z=\frac{\pi}{\mu} is the quantity of interest. Let g(t)=t^{-2}\left(2\exp\left(t-1\right)-1\right) . Observe that our implicit expression becomes g(1/z)=1+\sigma^{2}/\mu^{2} . Now, for x\geq 0 , g^{-1}(e^{x}) is concave. This can be shown as follows: g^{-1}(e^{x}) is concave for x\geq 0 if \{(x,y)\in\mathbb{R}_{+}\times\mathbb{R}:y\leq g^{-1}(e^{x})\}=\{(x,y)\in\mathbb{R}_{+}\times\mathbb{R}:\log(g(y))\leq x\} is convex, which is the case since \log(g(y)) is a convex function when it is non-negative ( y\geq 1 ). Because g^{-1}(e^{x}) is concave it lies below its tangent lines. To compute the tangent we make use of \{(x,y)\in\mathbb{R}_{+}\times\mathbb{R}:y\leq g^{-1}(e^{x})\}=\{(x,y)\in\mathbb{R}_{+}\times\mathbb{R}:\log(g(y))\leq x\} . Using it we obtain that g^{-1}(e^{x})\leq\alpha+\frac{g\left(\alpha\right)}{g^{\prime}\left(\alpha\right)}\left(x-\log\left(g\left(\alpha\right)\right)\right) for \alpha\geq 1 . With this result we can go back to g(1/z)=1+\sigma^{2}/\mu^{2} . Observe that we have z=\frac{1}{g^{-1}(1+\sigma^{2}/\mu^{2})}, so by our inequality, z\geq\left(\alpha+\frac{g\left(\alpha\right)}{g^{\prime}\left(\alpha\right)}\left(\log\left(1+\sigma^{2}/\mu^{2}\right)-\log\left(g\left(\alpha\right)\right)\right)\right)^{-1}=(c(\beta)+\beta\log(1+\sigma^{2}/\mu^{2}))^{-1}, where \beta>1 and c(\beta) a constant that depends only on \beta . ∎ Note that, given \mu and \sigma one could optimise over \beta to obtain the best bound, however, the resulting problem has no closed form solution, so one might as well use the already known tight implicit lower bound. The above result informs us that we already improve on the ratio of \frac{1}{n} if \mathrm{CV}(X_{\max}) grows sub-exponentially, and that we recover a constant factor lower bound if we are in a typical market where \mathrm{CV}(X_{\max}) is uniformly bounded. It would be interesting to establish similar bounds, e.g., when marginal distributional information of the buyers is known. Appendix A Proof minimax equality Before proving Theorem 2.1 we provide several definitions and supporting results for completeness. We begin with the definition of a tight family of measures. Definition A.1 (Tightness of measures; p. 59 [ 3 ] ) . Let S be a separable metric space and \mathcal{P}(S) the collection of all probability measures on (S,\mathcal{B}(S)) . A family of probability measures \mathcal{I}\subset\mathcal{P}(S) is tight if for all \varepsilon>0 there exists a compact K_{\varepsilon}\subset S such that \mu(K_{\varepsilon})>1-\varepsilon for all \mu\in\mathcal{I} . We now recall several concepts related to compactness relevant for our setting. A set is sequentially compact if every sequence has a convergent subsequence. In metrizable spaces, sequential compactness is equivalent to compactness. Since \mathcal{P}(S) is metrizable (as S is a separable metric space), compactness and sequential compactness coincide in our setting. A set is relatively compact if its closure is compact. Lastly, we say a set is weakly compact if it is compact with respect to the weak topology. This clarifies the following two theorem statements. Lemma A.2 (Prokhorov’s theorem; Theorem 5.1 [ 3 ] ) . Let S be a separable metric space and \mathcal{I} a family of probability measures on (S,\mathcal{B}(S)) . If \mathcal{I} is tight then is relatively (sequentially) compact in the weak topology. Lemma A.3 (Von Neumann-Fan minimax theorem; Theorem 2 [ 4 ] ) . Let X be nonempty and convex, and let Y be nonempty, weakly compact and convex. Let g:X\times Y\to\mathbb{R} be a bilinear 5 5 5 Bilinearity is not strictly necessary. Specifically, it is sufficient for g to be convex with respect to x\in X and concave and upper-semicontinuous with respect to y\in Y , and weakly continuous in y when restricted to Y . These conditions are, however, implied by bilinearity. function. Then, the following minimax equality holds \sup_{x\in X}\inf_{y\in Y}g(x,y)=\sup_{x\in X}\min_{y\in Y}g(x,y)=\min_{y\in Y}\sup_{x\in X}g(x,y)=\inf_{y\in Y}\sup_{x\in X}g(x,y). Theorem 2.1 is now a relatively straightforward application of the above two theorems. Proof of Theorem 2.1 . Let X_{\max}\sim F . If E[X_{\max}]=\infty then the result holds trivially. Now the case for E[X_{\max}]<\infty . Recall that a randomised stopping rule randomises over deterministic stopping rules, therefore a convex combination of stopping rules is a mixture. More explicitly, if \tau_{\lambda} is a convex combination of \tau_{1} and \tau_{2} , then \mathbb{P}(\tau_{\lambda}=i|v_{1},\dots,v_{i})=\lambda\mathbb{P}(\tau_{1}=i|v_{1},\dots,v_{i})+(1-\lambda)\mathbb{P}(\tau_{2}=i|v_{1},\dots,v_{i}). Such a convex combination is still a stopping rule, so \mathcal{T} is convex. To show \mathcal{I}(F,n) is weakly compact and convex we first give an equivalent definition, \mathcal{I}(F,n)=\{F_{\boldsymbol{X}}:\mathbb{R}^{n}_{+}\to[0,1]\;|\;F_{\boldsymbol{X}}\text{ a CDF and }F_{\boldsymbol{X}}(t,\dots,t)=F(t),\forall t\in\mathbb{R}_{+}\}. Let F_{\boldsymbol{X}_{1}},F_{\boldsymbol{X}_{2}}\in\mathcal{I}(F,n) and \lambda\in(0,1) , then the convex combination F_{\boldsymbol{X}_{\lambda}} is still a CDF and F_{\boldsymbol{X}_{\lambda}}(t,\dots,t)=F(t) , so \mathcal{I}(F,n) is convex. Let K_{\varepsilon}=[0,1+F^{-1}(1-\varepsilon)]^{n} , because E[X_{\max}]<\infty , F^{-1}(1-\varepsilon) is finite, so K_{\varepsilon} is compact. Let \mu\in\mathcal{I}(F,n) , then \mu(K_{\varepsilon})=F(1+F^{-1}(1-\varepsilon))>1-\varepsilon , so \mathcal{I}(F,n) is tight. By Lemma A.2 , \mathcal{I}(F,n) is relatively compact in the weak topology, and because \mathcal{I}(F,n) is its own closure, \mathcal{I}(F,n) is compact in the weak topology, that is, \mathcal{I}(F,n) is weakly compact. Let \tau\in\mathcal{T},F_{\boldsymbol{X}}\in\mathcal{I}(F,n) and define g(\tau,F_{\boldsymbol{X}})=\mathbb{E}[\boldsymbol{X}_{\tau}]=\int_{\mathbb{R}_{+}^{n}}\sum_{i=1}^{n}v_{i}\cdot\mathbb{P}(\tau=i|v_{1},\dots,v_{i})\mathrm{d}F_{\boldsymbol{X}}(\boldsymbol{v}). By linearity of summation and integration \displaystyle g(\lambda\tau_{1}+(1-\lambda)\tau_{2},F_{\boldsymbol{X}}) \displaystyle=\lambda g(\tau_{1},F_{\boldsymbol{X}})+(1-\lambda)g(\tau_{2},F_{\boldsymbol{X}}) \displaystyle g(\tau,\lambda F_{\boldsymbol{X}_{1}}+(1-\lambda)F_{\boldsymbol{X}_{2}}) \displaystyle=\lambda g(\tau,F_{\boldsymbol{X}_{1}})+(1-\lambda)g(\tau,F_{\boldsymbol{X}_{2}}), so g is bilinear. The result now follows Lemma A.3 . ∎ Appendix B Proof Theorem (b) general case In the main text Theorem (b) is proven for continuous F_{\max} . Here we prove it in generality. The proof is similar, but a more careful construction is required, since the intermediate value theorem cannot be applied. Let I(A)=\mathbb{P}(X_{\max}\in A)\mathbb{E}[X_{\max}|X_{\max}\in A] and denote by w_{0} and w_{n} the lower and upper bound of the support of F_{\max} . Define w_{1}=\inf\{w:I([w_{0},w_{1}])\geq\frac{1}{n}\mathbb{E}[X_{\max}]\} . Because F_{\max} may not be continuous it can occur that \int_{w_{0}}^{w_{1}}t\mathrm{d}F_{\max}(t)>\frac{1}{n}\mathbb{E}[X_{\max}] , however in this case it must be that \mathbb{P}(X_{\max}=w_{1})>0 . To recover equality, the point mass at w_{1} is only taken into the first partition with a probability p_{1} . Specifically, p_{1}=\inf\{p\geq 0:I([w_{0},w_{1}))+pI(\{w_{1}\})\geq\frac{1}{n}\mathbb{E}[X_{\max}]\} . we determine w_{2} and p_{2} in an analogous fashion. Let w_{2}=\inf\{w:(1-p_{1})I(\{w_{1}\})+I((w_{1},w])\geq\frac{1}{n}\mathbb{E}[X_{\max}]\}, and let p_{2}=\inf\{p\geq 0:(1-p_{1})I(\{w_{1}\})+I((w_{1},w_{2}))+pI(\{w_{2}\})\geq\frac{1}{n}\mathbb{E}[X_{\max}]\}. This procedure can be applied recursively to obtain w_{1},\dots,w_{n-1},p_{1},\dots,p_{n-1} . Lastly, let p_{0}=0 and p_{n}=1 . From these values, random variables X_{1},\dots,X_{n} with distributions F_{1},\dots,F_{n} can be constructed that satisfy \displaystyle\xi_{i}= \displaystyle(1-p_{i-1})\mathbb{P}(X_{\max}=w_{i-1})+\mathbb{P}(X_{\max}\in(w_{i-1},w_{i}))+p_{i}\mathbb{P}(X_{\max}=w_{i}), \displaystyle\mathbb{P}(X_{i}\in A)= \displaystyle\frac{1-p_{i-1}}{\xi_{i}}\mathbb{P}(X_{\max}\in\{w_{i-1}\}\cap A)+\frac{1}{\xi_{i}}\mathbb{P}(X_{\max}\in(w_{i-1},w_{i})\cap A) \displaystyle+\frac{p_{i}}{\xi_{i}}\mathbb{P}(X_{\max}\in\{w_{i}\}\cap A). By construction these random variables have the following properties. Firstly, \xi_{i}\mathbb{E}[X_{i}]=\xi_{i}\int_{\mathbb{R}}t\mathrm{d}F_{i}(t)=\frac{1}{n}\mathbb{E}[X_{\max}] . Secondly, by telescoping, \sum_{j=i+1}^{n}\xi_{j}=(1-p_{i})\mathbb{P}(X_{\max}=w_{i})+\mathbb{P}(X_{\max}>w_{i})\leq\mathbb{P}(X_{\max}\geq w_{i}) . Now, recursively define b_{i}=\mathrm{argmax}_{x\in[w_{i-1},w_{i}]}\{r_{i}(b_{1},\dots,b_{i-1},x)\} for i=1,\dots,n . By construction, \mathbb{P}(\tau=i|b_{1},\dots,b_{i-1},t)\leq\mathbb{P}(\tau=i|b_{1},\dots,b_{i}) for t\in[w_{i-1},w_{i}] . With this the instance can be defined. Let (v_{1},\dots,v_{n}) be (b_{1},\dots,b_{j-1},X_{j},0,\dots,0) with probability \xi_{j} . Let \tau be an optimal stopping rule for this instance, then \displaystyle V^{*}(F_{\max},n) \displaystyle=\sum_{j=1}^{n}\xi_{j}\int_{\mathbb{R}}\sum_{i=1}^{n}v_{i}(t)\mathbb{P}(\tau=i|v_{1}(t),\dots,v_{i}(t))\mathrm{d}F_{j}(t) \displaystyle(\text{Definition}) \displaystyle=\sum_{j=1}^{n}\sum_{i=1}^{j}\xi_{j}\int_{\mathbb{R}}v_{i}(t)\mathbb{P}(\tau=i|v_{1}(t),\dots,v_{i}(t))\mathrm{d}F_{j}(t) \displaystyle(i>j\ \Rightarrow\text{zero payoff}) \displaystyle=\sum_{i=1}^{n}\xi_{i}\int_{\mathbb{R}}v_{i}(t)\mathbb{P}(\tau=i|v_{1}(t),\dots,v_{i}(t))\mathrm{d}F_{i}(t) \displaystyle+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\xi_{j}\int_{\mathbb{R}}v_{i}(t)\mathbb{P}(\tau=i|v_{1}(t),\dots,v_{i}(t))\mathrm{d}F_{j}(t) \displaystyle(\text{Sum decomposition}) \displaystyle=\sum_{i=1}^{n}\xi_{i}\int_{\mathbb{R}}t\mathbb{P}(\tau=i|b_{1},\dots,b_{i-1},t)\mathrm{d}F_{i}(t) \displaystyle+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\xi_{j}\int_{\mathbb{R}}b_{i}\mathbb{P}(\tau=i|b_{1},\dots,b_{i})\mathrm{d}F_{j}(t) \displaystyle(\text{Definition }v_{i}(t)) \displaystyle\leq\sum_{i=1}^{n}\xi_{i}\int_{\mathbb{R}}t\mathbb{P}(\tau=i|b_{1},\dots,b_{i})\mathrm{d}F_{i}(t) \displaystyle(\text{Property }b_{i}\text{'s}) \displaystyle+\sum_{i=1}^{n-1}w_{i}\mathbb{P}(\tau=i|b_{1},\dots,b_{i})\sum_{j=i+1}^{n}\xi_{j} \displaystyle(b_{i}\leq w_{i}\text{ and}\int_{\mathbb{R}}\mathrm{d}F_{j}(t)=1) \displaystyle\leq\max_{1\leq i\leq n}\left\{\xi_{i}\int_{\mathbb{R}}t\mathrm{d}F_{i}(t)\right\}+\max_{1\leq i\leq n}\left\{w_{i}\sum_{j=i+1}^{n}\xi_{j}\right\} \displaystyle(\text{Convex combination}) \displaystyle\leq\max_{1\leq i\leq n}\left\{\xi_{i}\int_{\mathbb{R}}t\mathrm{d}F_{i}(t)\right\}+\max_{1\leq i\leq n}\left\{w_{i}\mathbb{P}(X_{\max}\geq w_{i})\right\} \displaystyle(\text{Telescoping}) \displaystyle\leq\Pi^{*}(F_{\max})+\frac{1}{n}\mathbb{E}[X_{\max}]. ∎ Appendix C Proofs of technical lemmas for Lemma 4.4 Proof of Lemma 4.9 . Because F_{\max} is continuously differentiable at p^{*} there exists a \delta_{0}>0 such that f(\cdot;\varepsilon) is differentiable on (p^{*}-\delta_{0},p^{*}+\delta_{0}) . Let \bar{p}(\varepsilon) be the minimiser of f(\cdot;\varepsilon) . \bar{p}(\varepsilon) converges to p^{*} as \varepsilon\to 0 , so there is an \varepsilon_{0} such that for \varepsilon<\varepsilon_{0} , \bar{p}(\varepsilon)\in(p^{*}-\delta_{0},p^{*}+\delta_{0}) . Moreover, for \varepsilon<\varepsilon_{0} f(\cdot;\varepsilon) is differentiable around \bar{p}(\varepsilon) , and since \bar{p}(\varepsilon) is a minimiser there is a non-empty interval (l(\varepsilon),r(\varepsilon)) such that f(\cdot;\varepsilon) is decreasing on (l(\varepsilon),\bar{p}(\varepsilon)] and increasing on [\bar{p}(\varepsilon),r(\varepsilon)) . We pick l and r such that (l(\varepsilon),r(\varepsilon)) is the largest such interval contained in (p^{*}-\delta_{0},p^{*}+\delta_{0}) . l and r are continuous in \varepsilon and (l(0),r(0)) is non-empty, so there exists an \varepsilon_{0}^{\prime} such that \bigcap\limits_{\varepsilon<\varepsilon_{0}^{\prime}}(l(\varepsilon),r(\varepsilon)) is non-empty and has p^{*} in its interior. Therefore there is a \delta>0 such that (p^{*}-\delta,p^{*}+\delta)\subset\bigcap\limits_{\varepsilon<\varepsilon_{0}^{\prime}}(l(\varepsilon),r(\varepsilon)) . For such a \delta and \varepsilon<\varepsilon_{0}^{\prime} , M is increasing ( \mathbb{P}(X_{\max}\geq t) is decreasing)), continuous on [p^{*}-\delta,p^{*}+\delta] (Because it is differentiable), f is non-negative, decreasing on (p^{*}-\delta,\bar{p}(\varepsilon)] and increasing on [\bar{p}(\varepsilon),p^{*}+\delta) . ∎ Remark C.1 . The essence of Lemma 4.9 is encapsulated in Figure 3 . \varepsilon p^{*}+\delta_{0} p^{*}+\delta p^{*} p^{*}-\delta p^{*}-\delta_{0} \varepsilon_{0}^{\prime} r(\varepsilon) l(\varepsilon) Figure 3 : The essence of Lemma 4.9 What the lemma shows is that the dashed rectangle around p^{*} between l(\varepsilon) and r(\varepsilon) exists. Lemma C.2 . Let I be a continuous and increasing function which can be written as I(t)=t+f(t) where f is a decreasing and non-negative function on [a,b] and let I^{k}=I\circ I^{k-1} , then \inf\{k\in\mathbb{N}:I^{k}(a)\geq b\}\leq 1+\int_{a}^{b}f(t)^{-1}\mathrm{d}t. Proof. Let \tilde{I}(t;\delta)=t+\delta f(t) and \tilde{I}^{k}=\tilde{I}\circ\tilde{I}^{k-1} . For t such that t\geq a and t+\delta f(t)\leq b , we have t+\delta f(t)\geq t\geq a by the non-negativity of f , and f(t)\geq f(t+\delta f(t)) since f is decreasing on [a,b] and t+\delta f(t)\in[a,b] . Therefore, \displaystyle\tilde{I}^{2}(t;\delta) \displaystyle=\tilde{I}(\tilde{I}(t;\delta);\delta)=\tilde{I}(t;\delta)+\delta f(\tilde{I}(t;\delta))=t+\delta f(t)+\delta f(t+\delta f(t)) \displaystyle\leq t+2\delta f(t)=\tilde{I}(t;2\delta). Iterative application yields that \tilde{I}^{m}(t;\delta)\leq\tilde{I}(t;m\delta) . Put differently, for \delta^{-1}\in\mathbb{N} , I(t)=\tilde{I}(t;1)\geq\tilde{I}^{1/\delta}(t;\delta) . We now show I^{k}(t)\geq\tilde{I}^{k/\delta}(t;\delta) by induction. It is true for k=1 and I^{k+1}(t)=I^{k}(I(t))\geq I^{k}(\tilde{I}^{1/\delta}(t;\delta)) , because I^{k} is increasing, now I^{k}(\tilde{I}^{1/\delta}(t;\delta))\geq\tilde{I}^{k/\delta}(\tilde{I}^{1/\delta}(t;\delta);\delta)=\tilde{I}^{(k+1)/\delta}(t;\delta) . Let x_{\delta}(s;a)=\tilde{I}^{s/\delta}(a;\delta) with s an integer multiple of \delta , then x_{\delta}(s+\delta;a)=\tilde{I}^{1+s/\delta}(a;\delta)=\tilde{I}(x_{\delta}(s;a);\delta) , therefore \frac{1}{\delta}(x_{\delta}(s+\delta;a)-x_{\delta}(s;a))=f(x_{\delta}(s;a)) . Let x(s;a)=\lim_{\delta\to 0}x_{\delta}(s;a) , where the limit is over \delta such that s/\delta is an integer. By continuity of I , x satisfies x^{\prime}(s;a)=f(x(s;a)) and x(0;a)=a , moreover x(k;a)\leq I^{k}(a) for k\in\mathbb{N} . Lastly, observe that \frac{\mathrm{d}}{\mathrm{d}s}x^{-1}(s;a)=f(s)^{-1} and that x^{-1}(a;a)=0 . The result now follows, \displaystyle\inf\{k\in\mathbb{N}:I^{k}(a)\geq b\}\leq\inf\{k\in\mathbb{N}:x(k;a)\geq b\} \displaystyle\leq \displaystyle 1+\inf\{t\in\mathbb{R}:x(t;a)\geq b\}=1+x^{-1}(b;a)=1+\int_{a}^{b}f(t)^{-1}\mathrm{d}t.\qed Remark C.3 . The intuition behind Lemma C.2 is that if I satisfies the conditions, then more frequent updates of the difference equation w_{i+1}=I(w_{i}) , that is a smaller \delta , monotonically decreases the trajectory. In Figure 4 this is illustrated for a specific example, namely I(t)=\frac{9}{10(1+t)e^{-t}} , a=0 and b=3/2 . 1 2 3 4 5 6 0.5 1 1.5 k \delta=1 \delta=\frac{1}{2} \delta=\frac{1}{4} \delta\to 0 Figure 4 : The processes \{\tilde{I}^{k/\delta}(a;\delta)\}_{k=0}^{\infty} Lemma C.4 . Let I be a continuous and increasing function which can be written as I(t)=t+f(t) where f is an increasing and non-negative function on [a,b] . Let I^{k}=I\circ I^{k-1} and \tilde{f}(t)=t-I^{-1}(t) , then \inf\{k\in\mathbb{N}:I^{k}(a)\geq b\}\leq 1+\int_{a}^{b}\tilde{f}(t)^{-1}\mathrm{d}t. Proof. Let I^{-k}=I^{-1}\circ I^{-(k-1)} . Observe that \inf\{k:I^{k}(a)\geq b\}=\inf\{k:I^{-k}(b)\leq a\} . Because f is increasing, the sequence \{I^{-k}(b)\} decreases with decreasing increments, therefore I^{-1}(t)=t-\tilde{f}(t) with \tilde{f} an increasing function. The remainder of the proof is analogous to Lemma C.2 , so the details are omitted. Let \tilde{I}(t;\delta)=t-\delta\tilde{f}(t) and \tilde{I}^{k}=\tilde{I}\circ\tilde{I}^{k-1} then, \displaystyle\tilde{I}^{2}(t;\delta) \displaystyle=\tilde{I}(\tilde{I}(t;\delta);\delta)=\tilde{I}(t;\delta)-\delta f(\tilde{I}(t;\delta))=t-\delta f(t)-\delta f(t-\delta f(t)) \displaystyle\geq t-2\delta f(t)=\tilde{I}(t;2\delta). From this inequality we obtain I^{-k}(t)=\tilde{I}^{k}(t;1)\leq x(k;t) where x satisfies x^{\prime}(s;t)=\tilde{f}(x(s;t)) and x(0;t)=t . Consequently, \displaystyle\inf\{k\in\mathbb{N}:I^{k}(a)\geq b\}=\inf\{k\in\mathbb{N}:I^{-k}(b)\leq a\}\leq\inf\{k\in\mathbb{N}:x(k;b)\leq a\} \displaystyle\leq \displaystyle 1+\inf\{t\in\mathbb{R}:x(t;b)\leq a\}=1+x^{-1}(a;b)=1-\int_{b}^{a}\tilde{f}(t)^{-1}\mathrm{d}t=1+\int_{a}^{b}\tilde{f}(t)^{-1}\mathrm{d}t.\quad\qed Lemma C.5 . Let \Pi^{*}=\Pi^{*}(F_{\max}) , M(t;\varepsilon):=\frac{\Pi^{*}+\varepsilon}{\mathbb{P}(X_{\max}\geq t)} , M^{k}=M\circ M^{k-1} , k(a,b;\varepsilon)=\inf\{k:M^{k}(a;\varepsilon)\geq b\} and \delta chosen according to Lemma 4.9 , then \lim_{\varepsilon\to 0}\varepsilon^{\frac{1}{2}}k(p^{*}-\delta,p^{*}+\delta;\varepsilon)\leq\sqrt{2\pi^{2}\frac{(1-F_{\max}(p^{*}))^{2}}{p^{*}F^{\prime\prime}_{\max}(p^{*})+2F^{\prime}_{\max}(p^{*})}}. Proof. Let f(t;\varepsilon)=M(t;\varepsilon)-t and \bar{p} be the minimiser of f . By the triangle like inequality, k(p^{*}-\delta,p^{*}+\delta;\varepsilon)\leq k(p^{*}-\delta,\bar{p};\varepsilon)+k(\bar{p},p^{*}+\delta;\varepsilon). Choosing \delta according to Lemma 4.9 allows us to apply Lemmas C.2 and C.4 , which give us the following upper bounds on the above two terms \displaystyle k(p^{*}-\delta,\bar{p};\varepsilon) \displaystyle\leq 1+\int_{p^{*}-\delta}^{\bar{p}}f(t;\varepsilon)^{-1}\mathrm{d}t, (C.1) \displaystyle k(\bar{p},p^{*}+\delta;\varepsilon) \displaystyle\leq 1+\int_{\bar{p}}^{p^{*}+\delta}\left(t-M^{-1}(t;\varepsilon)\right)^{-1}\mathrm{d}t. (C.2) f(t;\varepsilon) is known and t-M^{-1}(t;\varepsilon)=t-F^{-1}_{\max}\left(1-\frac{\Pi^{*}+\varepsilon}{t}\right) . We now proceed with the limit argument. Let \zeta_{1}(t;\varepsilon)=f(t;\varepsilon) and \zeta_{2}(t;\varepsilon)=t-M^{-1}(t;\varepsilon) . For |s|\leq\delta we have by Taylor’s theorem that, \zeta_{i}(p^{*}+s)\geq\xi_{i}(p^{*}+s;\varepsilon):=\zeta_{i}(p^{*})+\zeta_{i}^{\prime}(p^{*})s+\frac{1}{2}\zeta_{i}^{\prime\prime}(p^{*})s^{2}-L|s|^{3}, where L=\max\{L_{1},L_{2}\} and L_{i}=\sup\{|\frac{1}{6}\zeta_{i}^{\prime\prime\prime}(p^{*}+s)|:|s|\leq\delta\} . The \xi_{i} ’s can be written as \xi_{i}(p^{*}+s;\varepsilon):=a_{i}+b_{i}s+c_{i}s^{2}-L|s|^{3}, where \displaystyle a_{1} \displaystyle=\frac{\Pi^{*}+\varepsilon}{1-F_{\max}(p^{*})}-p^{*}=\frac{\varepsilon}{1-F_{\max}(p^{*})}, \displaystyle a_{2} \displaystyle=p^{*}-F^{-1}_{\max}\left(1-\frac{\Pi^{*}+\varepsilon}{p^{*}}\right), \displaystyle b_{1} \displaystyle=\frac{(\Pi^{*}+\varepsilon)F^{\prime}_{\max}(p^{*})}{(1-F_{\max}(p^{*}))^{2}}-1, \displaystyle b_{2} \displaystyle=1-\frac{\Pi^{*}+\varepsilon}{(p^{*})^{2}F^{\prime}_{\max}\left(F^{-1}_{\max}\left(1-\frac{\Pi^{*}+\varepsilon}{p^{*}}\right)\right)}, \displaystyle c_{1} \displaystyle=(\Pi^{*}+\varepsilon)\frac{F^{\prime\prime}_{\max}(p^{*})(1-F_{\max}(p^{*}))+2F^{\prime}_{\max}(p^{*})^{2}}{2(1-F_{\max}(p^{*}))^{3}}, \displaystyle c_{2} \displaystyle=\frac{(\Pi^{*}+\varepsilon)}{(p^{*})^{3}F^{\prime}_{\max}\left(F^{-1}_{\max}\left(1-\frac{\Pi^{*}+\varepsilon}{p^{*}}\right)\right)}+\frac{(\Pi^{*}+\varepsilon)^{2}F^{\prime\prime}_{\max}\left(F^{-1}_{\max}\left(1-\frac{\Pi^{*}+\varepsilon}{p^{*}}\right)\right)}{2(p^{*})^{4}F^{\prime}_{\max}\left(F^{-1}_{\max}\left(1-\frac{\Pi^{*}+\varepsilon}{p^{*}}\right)\right)^{3}}. We will now show that a_{i}=a\varepsilon+O(\varepsilon^{2}) , b_{i}=O(\varepsilon) and c_{i}=c+O(\varepsilon) where a=(1-F_{\max}(p^{*}))^{-1} and c=\frac{p^{*}F^{\prime\prime}_{\max}(p^{*})+2F^{\prime}_{\max}(p^{*})}{2(1-F_{\max}(p^{*}))} . Recall that 1-F_{\max}(p^{*})=p^{*}F^{\prime}_{\max}(p^{*}) , since p^{*} solves the first order condition. Firstly, a_{1}=a\varepsilon and a_{2}=a\varepsilon+O(\varepsilon^{2}) follows from the fact that a_{2}=0 for \varepsilon=0 and that \displaystyle\left.\frac{\mathrm{d}a_{2}}{\mathrm{d}\varepsilon}\right|_{\varepsilon=0} \displaystyle=\left.\left(p^{*}F^{\prime}_{\max}\left(F^{-1}_{\max}\left(1-\frac{\Pi^{*}+\varepsilon}{p^{*}}\right)\right)\right)^{-1}\right|_{\varepsilon=0} \displaystyle=(p^{*}F^{\prime}_{\max}(p^{*}))^{-1}=(1-F_{\max}(p^{*}))^{-1}. Secondly, for \varepsilon=0 \displaystyle b_{1} \displaystyle=\frac{(\Pi^{*})F^{\prime}_{\max}(p^{*})}{(1-F_{\max}(p^{*}))^{2}}-1=\frac{p^{*}F^{\prime}_{\max}\left(p^{*}\right)}{1-F_{\max}(p^{*})}-1=0, \displaystyle b_{2} \displaystyle=1-\frac{\Pi^{*}}{(p^{*})^{2}F^{\prime}_{\max}\left(F^{-1}_{\max}\left(1-\frac{\Pi^{*}}{p^{*}}\right)\right)}=1-\frac{1-F_{\max}(p^{*})}{p^{*}F^{\prime}_{\max}\left(p^{*}\right)}=0. Therefore b_{1} and b_{2} are O(\varepsilon) . Lastly, for \varepsilon=0 \displaystyle c_{1} \displaystyle=(\Pi^{*})\frac{F^{\prime\prime}_{\max}(p^{*})(1-F_{\max}(p^{*}))+2F^{\prime}_{\max}(p^{*})^{2}}{2(1-F_{\max}(p^{*}))^{3}} \displaystyle=\frac{p^{*}F^{\prime\prime}_{\max}(p^{*})(1-F_{\max}(p^{*}))+2p^{*}F^{\prime}_{\max}(p^{*})^{2}}{2(1-F_{\max}(p^{*}))^{2}} \displaystyle=\frac{p^{*}F^{\prime\prime}_{\max}(p^{*})+2F^{\prime}_{\max}(p^{*})}{2(1-F_{\max}(p^{*}))}, \displaystyle c_{2} \displaystyle=\frac{\Pi^{*}}{(p^{*})^{3}F^{\prime}_{\max}\left(F^{-1}_{\max}\left(1-\frac{\Pi^{*}}{p^{*}}\right)\right)}+\frac{(\Pi^{*})^{2}F^{\prime\prime}_{\max}\left(F^{-1}_{\max}\left(1-\frac{\Pi^{*}}{p^{*}}\right)\right)}{2(p^{*})^{4}F^{\prime}_{\max}\left(F^{-1}_{\max}\left(1-\frac{\Pi^{*}}{p^{*}}\right)\right)^{3}} \displaystyle=\frac{1-F_{\max}(p^{*})}{(p^{*})^{2}F^{\prime}_{\max}\left(p^{*}\right)}+\frac{(1-F_{\max}(p^{*}))^{2}F^{\prime\prime}_{\max}\left(p^{*}\right)}{2(p^{*})^{2}F^{\prime}_{\max}\left(p^{*}\right)^{3}} \displaystyle=\frac{1}{p^{*}}+\frac{F^{\prime\prime}_{\max}\left(p^{*}\right)}{2F^{\prime}_{\max}\left(p^{*}\right)}=\frac{p^{*}F^{\prime\prime}_{\max}(p^{*})+2F^{\prime}_{\max}(p^{*})}{2p^{*}F^{\prime}_{\max}(p^{*})}=\frac{p^{*}F^{\prime\prime}_{\max}(p^{*})+2F^{\prime}_{\max}(p^{*})}{2(1-F_{\max}(p^{*}))}. Therefore, c_{i}=c+O(\varepsilon) . From ( C.1 ) and ( C.2 ) and the fact that \zeta_{i} is lower bounded by \xi_{i} we obtain that \displaystyle\lim_{\varepsilon\to 0}\varepsilon^{\frac{1}{2}}\left(k(p^{*}-\delta,\bar{p};\varepsilon)+k(\bar{p},p^{*}+\delta;\varepsilon)\right) \displaystyle\leq\lim_{\varepsilon\to 0}\varepsilon^{\frac{1}{2}}\left(\int_{p^{*}-\delta}^{\bar{p}}\frac{\mathrm{d}t}{\zeta_{1}(t;\varepsilon)}+\int_{\bar{p}}^{p^{*}+\delta}\frac{\mathrm{d}t}{\zeta_{2}(t;\varepsilon)}\right) \displaystyle\leq\lim_{\varepsilon\to 0}\varepsilon^{\frac{1}{2}}\left(\int_{p^{*}-\delta}^{\bar{p}}\frac{\mathrm{d}t}{\xi_{1}(t;\varepsilon)}+\int^{p^{*}+\delta}_{\bar{p}}\frac{\mathrm{d}t}{\xi_{2}(t;\varepsilon)}\right). The value of the right-hand side is driven by the first order dependence of a_{i},b_{i} and c_{i} on \varepsilon . Since these are the same for i=1 and i=2 , we have that for \xi_{0}(p^{*}+s;\varepsilon):=a_{0}+b_{0}s+c_{0}s^{2}-L|s|^{3} with a_{0}=a\varepsilon+O(\varepsilon^{2}) , b_{0}=O(\varepsilon) and c_{0}=c+O(\varepsilon) that \displaystyle\lim_{\varepsilon\to 0}\varepsilon^{\frac{1}{2}}\left(\int_{p^{*}-\delta}^{\bar{p}}\frac{\mathrm{d}t}{\xi_{1}(t;\varepsilon)}+\int^{p^{*}+\delta}_{\bar{p}}\frac{\mathrm{d}t}{\xi_{2}(t;\varepsilon)}\right)=\lim_{\varepsilon\to 0}\varepsilon^{\frac{1}{2}}\int_{p^{*}-\delta}^{p^{*}+\delta}\frac{\mathrm{d}t}{\xi_{0}(t;\varepsilon)}. (C.3) The function \xi_{0} has roots above and below p^{*} , so \delta needs to be small enough such that there are no roots in the interval (p^{*}-\delta,p^{*}+\delta) . To do so we make use of two facts. Firstly, as \varepsilon decreases so does \xi_{0} , resulting in roots closer to p^{*} . For \varepsilon=0 , \xi_{0} has roots at p^{*}\pm\frac{c}{L} , so \delta<\frac{c}{L} is necessary. Moreover, for \varepsilon=0 , \xi_{0} has local maxima at p^{*}\pm\frac{2}{3}\frac{c}{L} , so we pick \delta\leq\frac{2}{3}\frac{c}{L} . Such a \delta exists, since L is continuous in \delta at zero, because F_{\max} is three times continuously differentiable at p^{*} . This is not in conflict with Lemma 4.9 , since \delta can always be chosen smaller. Denote the unique real root of a_{0}+b_{0}t+c_{0}t^{2}+Lt^{3}=0 by r_{1} and the unique real root of a_{0}+b_{0}t+c_{0}t^{2}-Lt^{3}=0 by r_{2} . We have that r_{1}=-\frac{c}{L}+O(\varepsilon) and r_{2}=\frac{c}{L}+O(\varepsilon) . Partial fraction decomposition yields that \frac{1}{\xi_{0}(p^{*}+s;\varepsilon)}=\begin{cases}\lambda_{1}\left(\frac{1}{s-r_{1}}-\frac{Ls+c_{0}+2r_{1}L}{Ls^{2}+\left(c_{0}+r_{1}L\right)s-a_{0}/r_{1}}\right),&\text{if }s\leq 0,\\ \lambda_{2}\left(\frac{1}{s-r_{2}}-\frac{Ls+2r_{2}L-c_{0}}{Ls^{2}+\left(r_{2}L-c_{0}\right)s+a_{0}/r_{2}}\right),&\text{if }s>0,\end{cases} where \lambda_{1}=\frac{r_{1}}{r_{1}^{2}\left(c_{0}+2r_{1}L\right)-a_{0}} and \lambda_{2}=\frac{r_{2}}{r_{2}^{2}\left(c_{0}-2r_{2}L\right)-a_{0}} . ( C.3 ) can now be evaluated, \displaystyle\int_{p^{*}-\delta}^{p^{*}+\delta}\frac{\mathrm{d}s}{\xi_{0}(s;\varepsilon)}= \displaystyle\lambda_{1}\int_{-\delta}^{0}\left(\frac{1}{s-r_{1}}-\frac{Ls+c_{0}+2r_{1}L}{Ls^{2}+\left(c_{0}+r_{1}L\right)s-a_{0}/r_{1}}\right)\mathrm{d}s \displaystyle+ \displaystyle\lambda_{2}\int_{0}^{\delta}\left(\frac{1}{s-r_{2}}-\frac{Ls+2r_{2}L-c_{0}}{Ls^{2}+\left(r_{2}L-c_{0}\right)s+a_{0}/r_{2}}\right)\mathrm{d}s \displaystyle= \displaystyle\lambda_{1}\log\left|r_{1}\right|-\lambda_{1}\log\left|r_{1}+\delta\right|-\lambda_{1}\frac{1}{2}\log\left|\frac{a_{0}}{r_{1}}\right| \displaystyle- \displaystyle\lambda_{1}\frac{2(c_{0}+2r_{1}L)-\left(c_{0}+r_{1}L\right)}{\sqrt{-4L\frac{a_{0}}{r_{1}}-\left(c_{0}+r_{1}L\right)^{2}}}\arctan\left(\frac{\left(c_{0}+r_{1}L\right)}{\sqrt{-4L\frac{a_{0}}{r_{1}}-\left(c_{0}+r_{1}L\right)^{2}}}\right) \displaystyle+ \displaystyle\lambda_{1}\frac{1}{2}\log\left|L\delta^{2}-\left(c_{0}+r_{1}L\right)\delta-\frac{a_{0}}{r_{1}}\right| \displaystyle+ \displaystyle\lambda_{1}\frac{2(c_{0}+2r_{1}L)-\left(c_{0}+r_{1}L\right)}{\sqrt{-4L\frac{a_{0}}{r_{1}}-\left(c_{0}+r_{1}L\right)^{2}}}\arctan\left(\frac{-2L\delta+\left(c_{0}+r_{1}L\right)}{\sqrt{-4L\frac{a_{0}}{r_{1}}-\left(c_{0}+r_{1}L\right)^{2}}}\right) \displaystyle+ \displaystyle\lambda_{2}\left(\log\left|\delta-r_{2}\right|-\log\left|r_{2}\right|+\frac{1}{2}\log\left|\frac{a_{0}}{r_{2}}\right|\right) \displaystyle+ \displaystyle\lambda_{2}\frac{2\left(2r_{2}L-c_{0}\right)-\left(r_{2}L-c_{0}\right)}{\sqrt{4L\frac{a_{0}}{r_{2}}-\left(r_{2}L-c_{0}\right)^{2}}}\arctan\left(\frac{\left(r_{2}L-c_{0}\right)}{\sqrt{4L\frac{a_{0}}{r_{2}}-\left(r_{2}L-c_{0}\right)^{2}}}\right) \displaystyle- \displaystyle\lambda_{2}\frac{1}{2}\log\left|L\delta^{2}+\left(r_{2}L-c_{0}\right)\delta+\frac{a_{0}}{r_{2}}\right| \displaystyle- \displaystyle\lambda_{2}\frac{2\left(2r_{2}L-c_{0}\right)-\left(r_{2}L-c_{0}\right)}{\sqrt{4L\frac{a_{0}}{r_{2}}-\left(r_{2}L-c_{0}\right)^{2}}}\arctan\left(\frac{2L\delta+\left(r_{2}L-c_{0}\right)}{\sqrt{4L\frac{a_{0}}{r_{2}}-\left(r_{2}L-c_{0}\right)^{2}}}\right) Every term except the fourth and eighth vanishes when we multiply with \varepsilon^{\frac{1}{2}} and take the limit. The arctans converge to \pm\pi , as their arguments diverge, leaving only simple terms. Rudimentary calculus reveals that \varepsilon^{\frac{1}{2}}\int_{p^{*}-\delta}^{p^{*}+\delta}\frac{\mathrm{d}s}{\xi_{0}(s;\varepsilon)} converges to \pi(ac)^{-\frac{1}{2}} . Substituting the expressions of a and c yields the result. ∎