Optimisation for prophet inequalities

Brüstle, Johannes (2025) Optimisation for prophet inequalities. PhD thesis, London School of Economics and Political Science.

Text - Submitted Version Download (898kB)

Abstract

Prophet inequalities have been extensively studied within optimal stopping theory, in part for their applicability to many online decision-making processes. In this thesis, we explore the benefits of viewing prophet inequalities as optimisation problems. We present three main results. First, we study the classic single-choice prophet inequality problem through a resource augmentation lens. In this setting, the algorithm faces an additional number of online independent and identically distributed (i.i.d.) bidders compared to the prophet. The optimal algorithm has a simple description as it sets carefully chosen thresholds T(j) for each incoming bidder j and accept a given value from the distribution if and only if it surpasses T(j). Our goal is to analyse the competition complexity, which relates to the number of extra resources required in order to approximate the benchmark by a given factor. Next, we generalise to arbitrary, independent distributions. Now, the metric asks for the smallest k such that the expected value of the online algorithm on k copies of the original instance is at least a (1−ε)-approximation to the expected offline optimum on a single copy. We show that block threshold algorithms, which set one threshold per copy, are optimal and give a tight bound of k = Θ(log(log1/ε)). This shows that block threshold algorithms approach the offline optimum doubly-exponentially fast. For single threshold algorithms, which set the same threshold throughout, we give a tight bound of k = Θ(log(1/ε)) establishing an exponential gap between block and single threshold algorithms. Finally, we move on to the i.i.d. k-selection prophet inequality problem, which is a different extension of the single choice setting in the case of i.i.d. distributions. At each time step, a decision is made to accept or reject the value, under the constraint of accepting at most k in total. Our work proposes an infinite-dimensional linear programming formulation that fully characterises the worst-case tight approximation ratio of the k-selection prophet inequality problem, complementing the recent semiinfinite linear programming general approach by Jiang et al. [EC 2023]. Notably, we introduce a nonlinear system of differential equations that generalises Hill and Kertz’s equation. For small k, we observe that this approach yields the best approximation ratios to date.

Item Type:	Thesis (PhD)
Additional Information:	© 2025 Johannes Brüstle
Library of Congress subject classification:	Q Science > QA Mathematics
Sets:	Departments > Mathematics
Supervisor:	Dütting, Paul and Végh, László A.
URI:	http://etheses.lse.ac.uk/id/eprint/4808

Actions (login required)

Record administration - authorised staff only