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
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.
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]