Private Prophets

Prophet inequalities are a basic problem in decision making: values drawn independently from fixed distributions arrive sequentially and a mechanism must irrevocably select one while competing with the expected maximum. In the learning version of the problem, distributions are unknown, but we are given independently drawn samples from each distribution from which a mechanism is learned. Our focus is differentially private learning, requiring the learned decision rule to be insensitive to any single training sample. We study two natural notions of privacy. First, we consider public threshold mechanisms, which release a collection of thresholds and accept the first value exceeding its corresponding decision threshold. Second, we consider index-private mechanisms where only the identity of the selected element is released. For both privacy notions, we obtain essentially tight sample-privacy-utility tradeoffs.