AFTD Auto-Formalizing Theoretical Domains

spx_instance

lemmaverified

The four-player instance is a two-point instance.

Statement

lemma spx_instance : spi_is_two_point_instance spx_x spx_w
Source
step towards strategic_prophet_no_half_robust_static_threshold (no static threshold is 1/2-robust, open in Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling, NeurIPS 2024 (arXiv:2409.18269), Remark 4.1 and Sec. 6)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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.
  • 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.
Used by 3
  • 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 =…
  • 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…
  • 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

/-- The four-player instance is a two-point instance. -/lemma spx_instance : spi_is_two_point_instance spx_x spx_w := by  intro i; fin_cases i <;> norm_num [spx_x, spx_w]
See it in the graphDiscuss this resultChallenge it