AFTD Auto-Formalizing Theoretical Domains

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

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]
See it in the graphDiscuss this resultChallenge it