AFTD Auto-Formalizing Theoretical Domains

spi_two_point_above

lemmaverified

Above its high value (T > h) a two-point player is never accepted, whatever its scheme.

Statement

lemma spi_two_point_above {N S : ℕ} (x w : Fin N → Fin 2 → ℝ) (hinst : spi_is_two_point_instance x w)
    (T : ℝ) (φ : Fin N → Fin 2 → Fin S → ℝ) {i : Fin N} (hφ : spi_is_scheme (φ i)) (hT : x i 0 < T) :
    spi_accept_prob x w φ T i = 0 ∧ spi_accept_value x w φ T i = 0
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 8
  • spi_accept_probProbability that the searcher accepts player i when she reaches it.
  • spi_accept_valueExpected reward collected from player i on the event that it is reached and accepted.
  • spi_is_schemeA signaling scheme of one player: for every support point a probability distribution over the S signals.
  • spi_two_point_max_probProposition 3.1 for a two-point reward (h with probability q, else l): the largest acceptance probability achievable under threshold T (1…
  • spi_two_point_max_valueThe searcher's expected reward from a two-point player using an optimal scheme (E[X] if T <= E[X], T times the pooling probability if E[X]…
  • spi_accept_prob_mem_IccAcceptance probabilities of valid schemes on two-point rewards lie in [0, 1].
  • spi_two_point_boundFor a two-point reward, every scheme's acceptance probability is at most spi_two_point_max_prob, and if it attains it the accepted value…
  • 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.
Used by 2
  • 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…

Lean source view module on GitHub

/-- Above the high value (`T > h`) a two-point player is never accepted, whatever its scheme. -/lemma spi_two_point_above {N S : ℕ} (x w : Fin N → Fin 2 → ℝ) (hinst : spi_is_two_point_instance x w)    (T : ℝ) (φ : Fin N → Fin 2 → Fin S → ℝ) {i : Fin N} (hφ : spi_is_scheme (φ i)) (hT : x i 0 < T) :    spi_accept_prob x w φ T i = 0 ∧ spi_accept_value x w φ T i = 0 := by  obtain ⟨-, hlh, h0, h1, hw1⟩ := hinst i  have hb := spi_two_point_bound x w φ T i hlh h0 h1 hw1 hφ  have hw : ∀ k, 0 ≤ w i k := by    intro k; fin_cases k    · exact h0    · simp only [Fin.mk_one, hw1]; linarith  have hP := (spi_accept_prob_mem_Icc x w φ T i hw (by rw [hw1]; ring) hφ).1  have hm : spi_two_point_max_prob (x i 0) (x i 1) (w i 0) T = 0 := by    unfold spi_two_point_max_prob    rw [if_neg (by nlinarith), if_neg (by linarith)]  have hv : spi_two_point_max_value (x i 0) (x i 1) (w i 0) T = 0 := by    unfold spi_two_point_max_value    rw [if_neg (by nlinarith), if_neg (by linarith)]  rw [hm] at hb  have hP0 : spi_accept_prob x w φ T i = 0 := le_antisymm hb.1 hP  exact ⟨hP0, by rw [hb.2 hP0.ge, hv]⟩
See it in the graphDiscuss this resultChallenge it