AFTD Auto-Formalizing Theoretical Domains

spi_reach_prob_nonneg

lemmaverified

Reach probabilities are nonnegative in a two-point instance under valid schemes.

Statement

open Finset in
lemma spi_reach_prob_nonneg {N S : ℕ} (x w : Fin N → Fin 2 → ℝ) (hinst : spi_is_two_point_instance x w)
    (φ : Fin N → Fin 2 → Fin S → ℝ) (hφ : ∀ i, spi_is_scheme (φ i)) (T : ℝ) (i : Fin N) :
    0 ≤ spi_reach_prob x w φ T i
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 4
  • spi_reach_probProbability that the search reaches player i: all earlier players are rejected (independence across players).
  • spi_is_schemeA signaling scheme of one player: for every support point a probability distribution over the S signals.
  • spi_accept_prob_mem_IccAcceptance probabilities of valid schemes on two-point rewards lie in [0, 1].
  • 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 1
  • 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…

Lean source view module on GitHub

open Finset in/-- Reach probabilities are nonnegative in a two-point instance under valid schemes. -/lemma spi_reach_prob_nonneg {N S : ℕ} (x w : Fin N → Fin 2 → ℝ) (hinst : spi_is_two_point_instance x w)    (φ : Fin N → Fin 2 → Fin S → ℝ) (hφ : ∀ i, spi_is_scheme (φ i)) (T : ℝ) (i : Fin N) :    0 ≤ spi_reach_prob x w φ T i := by  unfold spi_reach_prob  refine Finset.prod_nonneg fun j _ => ?_  obtain ⟨-, -, h0, h1, hw1⟩ := hinst j  have hw : ∀ k, 0 ≤ w j k := by    intro k; fin_cases k    · exact h0    · simp only [Fin.mk_one, hw1]; linarith  have := spi_accept_prob_mem_Icc x w φ T j hw (by rw [hw1]; ring) (hφ j)  linarith [this.2]
See it in the graphDiscuss this resultChallenge it