We study a variant of the prophet inequality with limited information, where the decision maker has access only to the first k moments of each random variable, rather than their full distributions. In this work, we show that even with full moment knowledge (i.e., k=∞), the best possible competitive ratio is Θ(1/ logn), and that this can already be achieved with only knowledge of the first moment. While the lower bound is simple and is attained by a standard exponential bucketing algorithm, the upper bound requires a subtle construction. This involves using Vandermonde matrices first to construct a parametrized family of distributions for which the first k moments coincide, and for which the expected maximum of n such copies varies widely across different parameter choices. Using Prokhorov’s theorem, we establish the existence of limit distributions, which we show have all their moments equal. Finally, we describe a construction where an adversary can select equally looking instances combining these distributions, making it impossible for the decision maker to obtain a factor better than O(1/ logn) of the expected maximum.

The I.I.D. Prophet Inequality is a fundamental problem in optimal stopping theory where, given n independent random variables X1, ..., Xn drawn from a known distribution D, one has to decide at every step i whether to stop and accept Xi; or discard it forever and continue. The goal is to maximize (or minimize) the selected value and compete against the all-knowing prophet. For the maximization setting, a tight constant-competitive guarantee of ≈ 0.745 is well-known [Correa, Foncea, Hoeksma, Oosterwijk, Vredeveld, 2019], whereas the minimization setting is qualitatively different: the optimal constant is distribution-dependent and can be arbitrarily large [Livanos and Mehta, 2024].

In the classical prophet inequality setting, a gambler is given a sequence of n random variables X₁, … , X_n, taken from known distributions, observes their values in adversarial order and selects one of them, immediately after it is being observed, aiming to select a value that is as high as possible. The classical prophet inequality shows a strategy that guarantees a value at least half of the value of an omniscience prophet that always picks the maximum, and this ratio is optimal. Here, we generalize the prophet inequality, allowing the gambler some additional information about the future that is otherwise privy only to the prophet. Specifically, at any point in the process, the gambler is allowed to query an oracle 𝒪. The oracle responds with a single bit answer: YES if the current realization is greater than the remaining realizations, and NO otherwise. We show that the oracle model with m oracle calls is equivalent to the Top-1-of-(m+1) model when the objective is maximizing the probability of selecting the maximum. This equivalence fails to hold when the objective is maximizing the competitive ratio, but we still show that any algorithm for the oracle model implies an equivalent competitive ratio for the Top-1-of-(m+1) model. We resolve the oracle model for any m, giving tight lower and upper bound on the best possible competitive ratio compared to an almighty adversary. As a consequence, we provide new results as well as improvements on known results for the Top-1-of-m model.

Over the past two decades, significant strides have been made in stochastic problems such as revenue-optimal auction design and prophet inequalities, traditionally modeled with n independent random variables to represent the values of n items. However, in many applications, this assumption of independence often diverges from reality. Given the strong impossibility results associated with arbitrary correlations, recent research has pivoted towards exploring these problems under models of mild dependency.

We study I.I.D. prophet inequalities for cost minimization, where the problem is to pick a cost from a sequence X1,…, Xn drawn independently from a known distribution in an online manner, and compete against the prophet who can see all the realizations upfront and select the minimum. In contrast to the well-studied rewards maximization setting where a simple threshold strategy achieves a competitive ratio of ≈ 0.745 for all distributions, the cost minimization setting turns out to be much more complex.

Matching based markets, like ad auctions, ride-sharing, and eBay, are inherently online and combinatorial, and therefore have been extensively studied under the lens of online stochastic combinatorial optimization models. The general framework that has emerged uses Contention Resolution Schemes (CRSs) introduced by Chekuri, Vondrák, and Zenklusen for combinatorial problems, where one first obtains a fractional solution to a (continuous) relaxation of the objective, and then proceeds to round it. When the order of rounding is controlled by an adversary, it is called an Online Contention Resolution Scheme (OCRSs), which has been successfully applied in online settings such as posted-price mechanisms, prophet inequalities and stochastic probing.The study of greedy OCRSs against an almighty adversary has emerged as one of the most interesting problems since it gives a simple-to-implement scheme against the worst possible scenario. Intuitively, a greedy OCRS has to make all its decisions before the online process starts. We present simple $1/e$ - selectable greedy OCRSs for the single-item setting, partition matroids, and transversal matroids. This improves upon the previous state-of-the-art greedy OCRSs of [FSZ16] that achieves $1/4$ for these constraints. Finally, we show that no better competitive ratio than $1/e$ is possible, making our greedy OCRSs the best possible.