pith. sign in

arxiv: 2606.21524 · v1 · pith:NBKRY6LMnew · submitted 2026-06-19 · 💻 cs.GT

Prophet Inequalities under Local Differential Privacy

Achraf Azize , Mathieu Molina , Hugo Richard , Vianney Perchet This is my paper

Pith reviewed 2026-06-26 12:31 UTC · model grok-4.3

classification 💻 cs.GT
keywords prophet inequalitieslocal differential privacyoptimal stoppingcompetitive ratiorandomized responseonline algorithmsprivacy-preserving decision making
0
0 comments X

The pith

Under local differential privacy, the optimal online stopping rule for prophet inequalities achieves a tight competitive ratio of e^ε/(n-1+e^ε) against the non-private benchmark.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to solve optimal stopping problems when each arriving value is seen only through an ε-local differentially private report that the decision maker designs. It proves that binary randomized response reports plus a dynamic programming threshold rule are optimal, and derives tight competitive ratios against both the non-private online optimum and an LDP-aware prophet. A reader would care because many real platforms must protect sensitive data like valuations or test scores while still making good irrevocable decisions online. The results demonstrate that the performance loss from privacy is quantifiable and that the gap between online and offline shrinks with stronger privacy.

Core claim

The decision maker designs ε-LDP mechanisms for n independent values and chooses a stopping time to maximize expected selected true value. The optimal rule uses binary mechanisms and DP thresholds. The worst-case competitive ratio versus the optimal non-private online policy is e^ε/(n-1 + e^ε), and versus an LDP prophet it is (1 + e^{-ε})/2. These ratios are tight and interpolate between the extreme privacy regimes.

What carries the argument

ε-LDP reporting mechanisms designed by the decision maker, implemented as randomized-response binary reports with dynamic-programming thresholds.

If this is right

  • The competitive ratio e^ε/(n-1+e^ε) is tight in the worst case against the non-private online optimum.
  • The competitive ratio (1+e^{-ε})/2 is tight against an LDP prophet who sees the full privatized sequence.
  • Binary randomized-response reports suffice to implement the optimal LDP stopping rule.
  • Increasing the privacy parameter ε reduces the LDP prophet's advantage over the online rule faster than it degrades absolute online performance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Platforms facing untrusted curators may achieve relatively better online performance under stronger privacy constraints than under weaker ones.
  • The characterization could be tested by simulating small-n instances with fixed versus designer-chosen mechanisms to isolate the design power effect.
  • The binary mechanism sufficiency suggests that more complex LDP reports add little value for this class of stopping problems.

Load-bearing premise

The decision maker can design the ε-LDP mechanisms used to report the arriving values.

What would settle it

A counter-example instance of value distributions where some other LDP mechanism yields a strictly higher competitive ratio than e^ε/(n-1+e^ε) against the optimal non-private online policy.

read the original abstract

Many online decision platforms, from hiring marketplaces to auctions, face a tension between efficient decision-making and the protection of participants' privacy. Personal information, such as a candidate's test score or a bidder's valuation linked to protected data, is sensitive, and fear of data resale or reputational harm can make participants reluctant to share it. Furthermore, platforms can be untrusted or even incentivized to resell data, making local privacy guarantees that do not rely on a trusted centralized curator preferable. We initiate the study of optimal stopping and prophet inequalities under local differential privacy (LDP). Each of $n$ independent arriving values is observed only through reports generated by an $\varepsilon$-LDP mechanism. The decision maker must design the $\varepsilon$-LDP mechanisms, and choose an irrevocable stopping time to maximise the expected selected true value. We characterize the optimal online stopping rule under LDP and show that simple binary mechanisms suffice: an optimal LDP stopping rule can be implemented via a randomized-response-type report and a dynamic-programming threshold rule. We then quantify performance via tight competitive ratios against two benchmarks. Relative to the optimal non-private online policy, we prove a tight worst-case competitive ratio of $e^{\varepsilon}/(n - 1 + e^{\varepsilon})$, interpolating between $1/n$ (full privacy) and $1$ (no privacy). Relative to an LDP prophet, who designs $\varepsilon$-LDP mechanisms but observes the full privatized sequence before deciding what to select, we prove a tight competitive ratio of $(1 + e^{-\varepsilon})/2$, interpolating between $1$ (full privacy) and the classical $1/2$ bound (no privacy). Notably, increasing privacy shrinks the LDP prophet's advantage faster than it degrades online performance, closing the performance gap.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper initiates the study of prophet inequalities and optimal stopping under local differential privacy (LDP). The decision maker designs the ε-LDP reporting mechanisms for n arriving values and selects an irrevocable stopping time to maximize expected true value. It characterizes the optimal online policy as using binary randomized-response mechanisms together with dynamic-programming thresholds, and proves two tight competitive ratios: e^ε/(n-1+e^ε) against the optimal non-private online policy, and (1+e^{-ε})/2 against an LDP prophet who sees the full privatized sequence.

Significance. If the stated characterizations and tightness results hold, the work is a meaningful contribution at the intersection of differential privacy and online algorithms. It supplies explicit mechanisms, recovers the classical 1/n and 1/2 limits at the privacy extremes, and shows that the online-to-prophet gap closes under increasing privacy. The explicit interpolation formulas and the sufficiency of binary reports are concrete strengths.

minor comments (1)
  1. The abstract asserts that the ratios are tight and that binary mechanisms suffice, but does not indicate where in the manuscript the dynamic program is written or where the tightness arguments appear; adding one-sentence pointers to the relevant sections or theorems would improve readability for readers who begin with the abstract.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the paper, the recognition of its contribution at the intersection of differential privacy and online algorithms, and the recommendation for minor revision. We are pleased that the explicit mechanisms, tightness results, and interpolation between classical bounds are viewed as concrete strengths.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper defines a new model in which the decision maker designs the ε-LDP mechanisms for arriving values and derives the optimal online stopping rule (via binary randomized-response reports and dynamic-programming thresholds) plus two tight competitive ratios directly from that model. The ratios e^ε/(n-1+e^ε) and (1+e^{-ε})/2 are presented as fresh characterizations that correctly recover the classical 1/n and 1/2 limits at the privacy extremes; no equation, parameter, or benchmark reduces by construction to a fitted input, self-citation chain, or renamed known result. The derivation therefore remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard prophet-inequality modeling assumptions (independent arrivals, known distributions or worst-case analysis) together with the ability of the decision maker to choose the LDP mechanisms; no new entities or fitted parameters are introduced in the abstract.

axioms (2)
  • domain assumption Arriving values are independent.
    Standard modeling choice in prophet inequalities; invoked implicitly when defining the online stopping problem.
  • domain assumption The decision maker designs the ε-LDP reporting mechanisms.
    Explicitly stated in the problem setup (abstract paragraph 3).

pith-pipeline@v0.9.1-grok · 5863 in / 1373 out tokens · 32558 ms · 2026-06-26T12:31:19.166517+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 1 canonical work pages

  1. [1]

    David Assaf, Larry Goldstein, and Ester Samuel-Cahn

    Comprehensive survey on privacy-preserving protocols for sealed-bid auctions.Computers & Security(2020). David Assaf, Larry Goldstein, and Ester Samuel-Cahn

    2020

  2. [2]

    A statistical version of prophet inequalities.Annals of Statistics 26 (1998), 1190–1197. Pablo D. Azar, Robert Kleinberg, and S. Matthew Weinberg. 2014.Prophet Inequalities with Limited Information. Achraf Azize and Debabrota Basu

    1998

  3. [3]

    Achraf Azize, Marc Jourdan, Aymen Al Marjani, and Debabrota Basu

    When privacy meets partial information: A refined analysis of differentially private bandits.Advances in Neural Information Processing Systems35 (2022), 32199–32210. Achraf Azize, Marc Jourdan, Aymen Al Marjani, and Debabrota Basu

    2022

  4. [4]

    Achraf Azize, Marc Jourdan, Aymen Al Marjani, and Debabrota Basu

    On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence.arXiv preprint arXiv:2309.02202(2023). Achraf Azize, Marc Jourdan, Aymen Al Marjani, and Debabrota Basu

    arXiv 2023

  5. [5]

    arXiv preprint arXiv:2406.06408(2024)

    Differentially private best-arm identification. arXiv preprint arXiv:2406.06408(2024). Achraf Azize, Yulian Wu, Junya Honda, Francesco Orabona, Shinji Ito, and Debabrota Basu

    Pith/arXiv arXiv 2024

  6. [6]

    Yuan Shih Chow, Herbert E

    Differential privacy in the shuffle model: A survey of separations.arXiv preprint arXiv:2107.11839(2021). Yuan Shih Chow, Herbert E. Robbins, and David O. Siegmund. 1971.Great expectations: The theory of optimal stopping. Houghton Mifflin. José Correa, Patricio Foncea, Dana Pizarro, and Victor Verdugo

    arXiv 2021

  7. [7]

    Emily Diana, Hadi Elzayn, Michael Kearns, Aaron Roth, Saeed Sharifi-Malvajerdi, and Juba Ziani

    From pricing to prophets, and back!Operations Research Letters(2019). Emily Diana, Hadi Elzayn, Michael Kearns, Aaron Roth, Saeed Sharifi-Malvajerdi, and Juba Ziani

    2019

  8. [8]

    Minimax Optimal Procedures for Locally Private Estimation.J. Amer. Statist. Assoc.(2016). Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith

    2016

  9. [9]

    Ran Eilat, Kfir Eliaz, and Xiaosheng Mu

    The algorithmic foundations of differential privacy.Foundations and Trends®in Theoretical Computer Science9, 3–4 (2014), 211–407. Ran Eilat, Kfir Eliaz, and Xiaosheng Mu

    2014

  10. [10]

    Math.125, 1 (1992),

    A survey of prophet inequalities in optimal stopping theory.Contemp. Math.125, 1 (1992),

    1992

  11. [11]

    Xutong Jiang, Yuhu Sun, Bowen Liu, and Wanchun Dou

    A Small-Scale Restricted Double Auction Mechanism Based on Local Differential Privacy.IEEE Internet of Things Journal(2025). Xutong Jiang, Yuhu Sun, Bowen Liu, and Wanchun Dou

    2025

  12. [12]

    Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth

    Combinatorial double auction for resource allocation with differential privacy in edge computing.Computer Communications(2022). Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth

    2022

  13. [13]

    In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)

    The role of interactivity in local differential privacy. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 94–105. Marc Jourdan and Achraf Azize

    2019

  14. [14]

    Peter Kairouz, Keith Bonawitz, and Daniel Ramage

    Optimal Best Arm Identification under Differential Privacy.The Thirty-ninth Annual Conference on Neural Information Processing Systems(2025). Peter Kairouz, Keith Bonawitz, and Daniel Ramage. 2016a. Discrete distribution estimation under local privacy. InInterna- tional Conference on Machine Learning. PMLR, 2436–2444. Peter Kairouz, Sewoong Oh, and Pramod...

    2025

  15. [15]

    InInternational conference on machine learning

    The composition theorem for differential privacy. InInternational conference on machine learning. PMLR, 1376–1385. Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2016b. Extremal mechanisms for local differential privacy.Journal of Machine Learning Research17, 17 (2016), 1–51. Alexander Kent, Thomas B Berrett, and Yi Yu

    2016

  16. [16]

    Ulrich Krengel and Louis Sucheston

    Rate optimality and phase transition for user-level local differential privacy.arXiv preprint arXiv:2405.11923(2024). Ulrich Krengel and Louis Sucheston

    arXiv 2024

  17. [17]

    Semiamarts and Finite Values.Bull. Amer. Math. Soc.83 (1977), 745–747. Brendan Lucier

    1977

  18. [18]

    Min Lyu, Dong Su, and Ninghui Li

    An economic view of prophet inequalities.SIGecom Exch.(2017). Min Lyu, Dong Su, and Ninghui Li

    2017

  19. [19]

    VLDB Endow.(2016)

    Understanding the Sparse Vector Technique for Differential Privacy.Proc. VLDB Endow.(2016). Moni Naor, Benny Pinkas, and Reuban Sumner

    2016

  20. [20]

    Aviad Rubinstein, Jack Z

    Multi-armed bandits with local differential privacy.arXiv preprint arXiv:2007.03121(2020). Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg

    arXiv 2007

  21. [21]

    Stanley L Warner

    Comparison of threshold stop rules and maximum for independent nonnegative random variables.The Annals of Probability(1984). Stanley L Warner

    1984

  22. [22]

    Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang

    Randomized response: A survey technique for eliminating evasive answer bias.Journal of the American statistical association(1965), 63–69. Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang

    1965

  23. [23]

    https://doi.org/10.48550/ARXIV.2006.00701 Azize, Molina, Richard, and Perchet21 A Missing proofs of Section 4 A.1 Proof of Theorem 4.2 Proof

    Locally Differentially Private (Contextual) Bandits Learning. https://doi.org/10.48550/ARXIV.2006.00701 Azize, Molina, Richard, and Perchet21 A Missing proofs of Section 4 A.1 Proof of Theorem 4.2 Proof. Let 𝐹 be the distribution of 𝑋 and 𝑄 be an 𝜀-LDP mechanism. The joint distribution of (𝑍, 𝑋)is𝜋=𝑄⊗𝐹. We are going to construct ˜𝜋, such that 𝜋𝑋 = ˜𝜋𝑋 =𝐹 ...

    work page doi:10.48550/arxiv.2006.00701 2006

  24. [24]

    We can compute𝑊𝑖 as the maximum of three terms

    Now assuming that 𝑊𝑖+1 = 1and using the recursion of Theorem 4.4, we will prove this holds for𝑊 𝑖. We can compute𝑊𝑖 as the maximum of three terms. Because E[𝑋𝑖 ] ≤ 1 =𝑊 𝑖+1, we only need to compare𝑊 𝑖+1 with the last term. We first compute each part: E[max(E[𝑋 𝑖 |𝑍 𝑖 ],𝑊 𝑖+1 )]=Pr(𝑍 𝑖 =1)max(E[𝑋 𝑖 |𝑍 𝑖 =1],1) +Pr(𝑍 𝑖 =0)max(E[𝑋 𝑖 |𝑍 𝑖 =0],1) =max(E[𝑋 𝑖 1[...

    1992