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
- strategic_prophet_no_half_robust_static_thresholdNegative answer to the open question of arXiv:2409.18269: in a four-player two-point instance, equilibria exist for every static…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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