spi_reach_prob_fin_four
lemmaverified
For four players the reach probabilities are 1, 1-P0, (1-P0)(1-P1) and (1-P0)(1-P1)(1-P2).
Statement
open Finset in lemma spi_reach_prob_fin_four {K S : ℕ} (x w : Fin 4 → Fin K → ℝ) (φ : Fin 4 → Fin K → Fin S → ℝ) (T : ℝ) : spi_reach_prob x w φ T 0 = 1 ∧ spi_reach_prob x w φ T 1 = 1 - spi_accept_prob x w φ T 0 ∧ spi_reach_prob x w φ T 2 = (1 - spi_accept_prob x w φ T 0) * (1 - spi_accept_prob x w φ T 1) ∧ spi_reach_prob x w φ T 3 = (1 - spi_accept_prob x w φ T 0) * (1 - spi_accept_prob x w φ T 1) * (1 - spi_accept_prob x w φ T 2)
- 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 2
- spi_accept_probProbability that the searcher accepts player i when she reaches it.
- spi_reach_probProbability that the search reaches player i: all earlier players are rejected (independence across players).
- 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
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/-- For four players, the reach probabilities are `1`, `1 - P₀`, `(1 - P₀)(1 - P₁)` and `(1 - P₀)(1 - P₁)(1 - P₂)`. -/lemma spi_reach_prob_fin_four {K S : ℕ} (x w : Fin 4 → Fin K → ℝ) (φ : Fin 4 → Fin K → Fin S → ℝ) (T : ℝ) : spi_reach_prob x w φ T 0 = 1 ∧ spi_reach_prob x w φ T 1 = 1 - spi_accept_prob x w φ T 0 ∧ spi_reach_prob x w φ T 2 = (1 - spi_accept_prob x w φ T 0) * (1 - spi_accept_prob x w φ T 1) ∧ spi_reach_prob x w φ T 3 = (1 - spi_accept_prob x w φ T 0) * (1 - spi_accept_prob x w φ T 1) * (1 - spi_accept_prob x w φ T 2) := by simp [spi_reach_prob, Finset.prod_filter, Fin.prod_univ_four]