Researchers achieve optimal privacy-preserving decisions with prophet inequalities

A new paper from Achraf Azize, Mathieu Molina, Hugo Richard, and Vianney Perchet (accepted at EC'26) tackles the fundamental tension between efficient online decision-making and participant privacy. The authors consider a classic prophet inequality setting where n values arrive sequentially, but each value is only observed through an ε-LDP (local differential privacy) report generated by a randomized mechanism. The decision maker must design both the privacy mechanism and an irrevocable stopping rule to maximize the expected true value selected.

Key results show that simple binary mechanisms—specifically randomized response—are optimal under LDP. The paper provides tight competitive ratios against two natural benchmarks: vs. the optimal non-private online policy, the ratio is e^ε/(n-1+e^ε) (ranging from 1/n at full privacy to 1 at no privacy); vs. an LDP prophet who sees all privatized values before choosing, the ratio is (1+e^{-ε})/2 (interpolating between 1 and the classical 1/2 bound). Notably, increasing privacy shrinks the prophet's advantage faster than it degrades online performance, effectively closing the gap between online and offline decision-making under strong privacy guarantees.