AFTD Auto-Formalizing Theoretical Domains

spx_searcher_payoff_at_nine

theoremverifiedoriginal

With threshold T = 9, every equilibrium of the four-player instance gives the searcher exactly 721/150.

Statement

theorem spx_searcher_payoff_at_nine {S : ℕ} (hS : 2 ≤ S) (φ : Fin 4 → Fin 2 → Fin S → ℝ)
    (heq : spi_is_equilibrium spx_x spx_w 9 φ) :
    spi_searcher_payoff spx_x spx_w φ 9 = 721 / 150
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
03 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • 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_payoff_midFor 24/5 < T <= 9, every equilibrium of the four-player instance gives the searcher T p1 + (1-p1)(10/3 + (1-p2) 8/5) with p1 =…
Used by 1

Lean source view module on GitHub

/-- The bound `721/150` is attained: with threshold `T = 9`, every equilibrium gives the searcher exactly `721/150`. -/theorem spx_searcher_payoff_at_nine {S : ℕ} (hS : 2 ≤ S) (φ : Fin 4 → Fin 2 → Fin S → ℝ)    (heq : spi_is_equilibrium spx_x spx_w 9 φ) :    spi_searcher_payoff spx_x spx_w φ 9 = 721 / 150 := by  rw [spx_payoff_mid hS 9 φ heq (by norm_num) le_rfl]  norm_num
See it in the graphDiscuss this resultChallenge it