Research map / Reinforcement learning / MDPs and planning
Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies prophet inequality when each reward distribution is a strategic player who selectively signals its realized reward to maximize its selection probability, and characterizes threshold policies that stay 1/2-approximate without strategy yet achieve a robust ratio under strategic signaling.
Problem
Classic prophet inequality assumes rewards are fully disclosed, but in many economic settings each reward distribution is a strategic player who can selectively disclose its realized reward to the searcher to maximize its chance of being selected. The question is how robust threshold stopping polici
Approach
Characterizes each player's optimal signaling as a threshold (pooling) scheme that pools high rewards so the posterior mean equals the searcher's threshold, reducing the strategic game to a prophet problem with binary-support rewards; then shows which thresholds (half expected max, the k-approximation spectrum, median-based) are alpha-robust for arbitrary, IID, and log-concave distributions.
Key results
- For arbitrary distributions, the half-expected-max threshold is (1-1/e)/2 ≈ 0.316-robust, and no threshold from the 1/2-approximation spectrum can exceed (1-1/e)/2 under strategic signaling (tight).
- For i.i.d. distributions, a threshold T* is 1/2-robust, and no threshold policy can exceed 1/2+ε robustness.
- For log-concave heterogeneous distributions with N ≥ 1+β/α², any threshold in [2·HalfMax, median upper bound] is 1/2-robust.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the half expected max threshold | Threshold stopping policy · Arbitrary reward distributions with strategic signaling | competitive ratio: at least \frac{1-\sfrac{1}{e}}{2} | Helped |
| Use the half expected max threshold | Threshold stopping policy · Arbitrary reward distributions without strategic signaling | competitive ratio: \sfrac{1}{2} | Helped |
| Restrict to thresholds in the classic 1/2-approximation spectrum | Threshold stopping policy · Some arbitrary reward distributions with strategic signaling | robustness ratio: no threshold ... can achieve an alpha-robustness where alpha > \frac{1-(1 - 1/(N-1))^{N-1}}{2} | Hurt |
| Use threshold T = T* | Threshold stopping policy · IID reward distributions with strategic signaling | competitive ratio: \frac{1}{2} | Helped |
| Use threshold T = T* | Threshold stopping policy · IID reward distributions without strategic signaling | competitive ratio: \sfrac{1}{2} | Helped |
| Allow any threshold stopping policy while retaining the non-strategic 1/2 guarantee | Threshold stopping policy · Some IID reward distributions with strategic signaling | robustness ratio: no threshold stopping policy ... can achieve alpha-robustness where alpha > \frac{1}{2} + \varepsilon | Hurt |
| Use any threshold in [2 · half expected max, median threshold UB] under the stated regularity assumptions | Threshold stopping policy · Log-concave heterogeneous distributions with N ≥ 1 + β/α² | competitive ratio: \sfrac{1}{2} | Helped |
| Drop the requirement to retain a 1/2 guarantee in the non-strategic setting | Threshold stopping policy · IID reward distributions with strategic signaling | competitive ratio: (1-\sfrac{1}{e}) | Helped |
Surprising findings
- Strategic signaling can reduce the achievable ratio: for arbitrary distributions, no threshold in the 1/2-approximation spectrum exceeds (1-1/e)/2 under strategic signaling.
- Dropping the non-strategic 1/2 requirement, a threshold can reach (1-1/e) under strategic signaling for IID distributions.
Limitations
- Results restrict to static threshold policies with deterministic tie-breaking; dynamic or non-threshold policies are not covered.
- Log-concave 1/2-robustness requires the number of players to be large (N ≥ 1+β/α²) and regularity assumptions on density at endpoint 1.
- Whether a threshold outside the 1/2-approximation spectrum can achieve 1/2-robustness for arbitrary distributions remains open.
Experimental setup
Metrics: competitive ratio
Baselines: half expected max threshold median threshold expected-max-based thresholds (T*)
Builds on: prophet inequality (Samuel-Cahn) Bayesian persuasion mean-preserving contraction
Closest papers by meaning
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.86)
- Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness (NeurIPS 2025 · similarity 0.86)
- Is O(log N) practical? Near-Equivalence Between Delay Robustness and Bounded Regret in Bandits and RL (NeurIPS 2024 · similarity 0.86)
- Lookback Prophet Inequalities (NeurIPS 2024 · similarity 0.86)
- Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.85)
- Thresholds for sensitive optimality and Blackwell optimality in stochastic games (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.