Prophet Inequalities over Time

ACM Conference on Economics and Computation (EC), pp. 1–20

Abstract

In this paper, we introduce an over-time variant of the well-known prophet inequality with i.i.d. random variables. Instead of stopping with one realized value at some point in the process, we decide for each step how long we select the value. Then we cannot select another value until this period is over. The goal is to maximize the expectation of the sum of selected values. We describe the structure of the optimal stopping rule and give upper and lower bounds on the prophet inequality. In online algorithms terminology, this corresponds to bounds on the competitive ratio of an online algorithm.

Authors 3

1. Andreas Abels Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

2. Elias Pitschmann

   University of Bremen

   Affiliation as printed

   University of Bremen, Bremen, Germany

3. Daniel Schmand

   University of Bremen

   Affiliation as printed

   University of Bremen, Bremen, Germany