AFTD Auto-Formalizing Theoretical Domains

strategic_prophet_no_half_robust_static_threshold

theoremverifiedoriginal

Negative answer to the open question of arXiv:2409.18269: in a four-player two-point instance, equilibria exist for every static threshold, every equilibrium gives the searcher at most 721/150 < OPT/2 with OPT = 155039/15625, and T = 9 attains 721/150 = (450625/930234) OPT ~ 0.4844 OPT; so no static threshold is 1/2-robust.

Statement

theorem strategic_prophet_no_half_robust_static_threshold :
    spi_is_two_point_instance spx_x spx_w ∧
    @spi_prophet_value 3 2 spx_x spx_w = 155039 / 15625 ∧
    (∀ S, 2 ≤ S → ∀ T : ℝ, ∃ φ : Fin 4 → Fin 2 → Fin S → ℝ, spi_is_equilibrium spx_x spx_w T φ) ∧
    (∀ S, 2 ≤ S → ∀ (T : ℝ) (φ : Fin 4 → Fin 2 → Fin S → ℝ), spi_is_equilibrium spx_x spx_w T φ →
      spi_searcher_payoff spx_x spx_w φ T ≤ 721 / 150 ∧
      spi_searcher_payoff spx_x spx_w φ T < @spi_prophet_value 3 2 spx_x spx_w / 2) ∧
    (∀ S, 2 ≤ S → ∀ φ : Fin 4 → Fin 2 → Fin S → ℝ, spi_is_equilibrium spx_x spx_w 9 φ →
      spi_searcher_payoff spx_x spx_w φ 9 = 450625 / 930234 * @spi_prophet_value 3 2 spx_x spx_w)
Related work
operator (Claude), 2026-10-04: negative answer to the open question of Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling, NeurIPS 2024 (arXiv:2409.18269), Sec. 2-3 (model, Definition 2.4, Proposition 3.1), Remark 4.1 and Sec. 6 whether a static threshold stopping policy can be 1/2-robust; four-player two-point instance found by numerical search (after a five-player instance from a search subagent), every equilibrium of every threshold gives the searcher at most 721/150 < OPT/2 = 155039/31250, checked by the Lean kernel
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
  • spi_searcher_payoffThe searcher's expected payoff u_s(T) under static threshold T and the players' signaling schemes.
  • spi_is_equilibriumNash equilibrium of the players' signaling game induced by a static threshold T: no player can raise its selection probability by…
  • spi_prophet_valueThe prophet benchmark OPT = E[max_i X_i] for independent finite-support rewards.
  • spi_is_two_point_instanceTwo-point instances: every player's reward is x_i0 with probability w_i0 and x_i1 otherwise, with 0 <= x_i1 <= x_i0.
  • spi_two_point_equilibrium_existsExistence of equilibrium (Proposition 3.1 for two-point rewards): for every static threshold and S >= 2 signals, all players using the…
  • spx_xSupport values of the four-player instance: X0 = 24/5 surely; X1 in {9, 3}; X2 in {1000, 0}; X3 in {40, 0}.
  • spx_wProbabilities of the four-player instance: 1; 1/10 for 9; 1/300 for 1000; 1/25 for 40.
  • spx_instanceThe four-player instance is a two-point instance.
  • spx_prophet_valueThe prophet value of the four-player instance is E[max] = 155039/15625.
  • spx_searcher_payoff_leIn the four-player instance, for every static threshold T, every S >= 2 and every equilibrium, the searcher's expected payoff is at most…
  • spx_searcher_payoff_at_nineWith threshold T = 9, every equilibrium of the four-player instance gives the searcher exactly 721/150.

Lean source view module on GitHub

/-- Negative answer to the open question of arXiv:2409.18269 (NeurIPS 2024, Remark 4.1 and Sec. 6) on whether a static threshold stopping policy can be 1/2-robust under strategic reward signaling: in a four-player two-point instance, for every threshold `T` equilibria exist, and in every equilibrium the searcher gets at most `721/150`, while `OPT/2 = 155039/31250 > 721/150`; the best static threshold (`T = 9`) attains exactly `721/150 = (450625/930234) · OPT ≈ 0.4844 · OPT`. -/theorem strategic_prophet_no_half_robust_static_threshold :    spi_is_two_point_instance spx_x spx_w ∧    @spi_prophet_value 3 2 spx_x spx_w = 155039 / 15625 ∧    (∀ S, 2 ≤ S → ∀ T : ℝ, ∃ φ : Fin 4 → Fin 2 → Fin S → ℝ, spi_is_equilibrium spx_x spx_w T φ) ∧    (∀ S, 2 ≤ S → ∀ (T : ℝ) (φ : Fin 4 → Fin 2 → Fin S → ℝ), spi_is_equilibrium spx_x spx_w T φ →      spi_searcher_payoff spx_x spx_w φ T ≤ 721 / 150 ∧      spi_searcher_payoff spx_x spx_w φ T < @spi_prophet_value 3 2 spx_x spx_w / 2) ∧    (∀ S, 2 ≤ S → ∀ φ : Fin 4 → Fin 2 → Fin S → ℝ, spi_is_equilibrium spx_x spx_w 9 φ →      spi_searcher_payoff spx_x spx_w φ 9 = 450625 / 930234 * @spi_prophet_value 3 2 spx_x spx_w) := by  refine ⟨spx_instance, spx_prophet_value, fun S hS T => ⟨_, spi_two_point_equilibrium_exists hS _ _ spx_instance T⟩,    fun S hS T φ heq => ⟨spx_searcher_payoff_le hS T φ heq, ?_⟩, fun S hS φ heq => ?_⟩  · rw [spx_prophet_value]; linarith [spx_searcher_payoff_le hS T φ heq]  · rw [spx_searcher_payoff_at_nine hS φ heq, spx_prophet_value]; norm_num
See it in the graphDiscuss this resultChallenge it