spi_accept_prob_mem_Icc
lemmaverified
Acceptance probabilities of valid schemes on two-point rewards lie in [0, 1].
Statement
open Finset in lemma spi_accept_prob_mem_Icc {N S : ℕ} (x w : Fin N → Fin 2 → ℝ) (φ : Fin N → Fin 2 → Fin S → ℝ) (T : ℝ) (i : Fin N) (hw : ∀ k, 0 ≤ w i k) (hsum : w i 0 + w i 1 = 1) (hφ : spi_is_scheme (φ i)) : 0 ≤ spi_accept_prob x w φ T i ∧ spi_accept_prob x w φ T i ≤ 1
- 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 3
- spi_accept_probProbability that the searcher accepts player i when she reaches it.
- spi_is_schemeA signaling scheme of one player: for every support point a probability distribution over the S signals.
- spi_accept_reductionThe acceptance probability, accepted value and posterior-mean constraint of any scheme depend only on accepted masses A_k in [0, w_ik]…
- Used by 2
- spi_two_point_aboveAbove its high value (T > h) a two-point player is never accepted, whatever its scheme.
- spi_reach_prob_nonnegReach probabilities are nonnegative in a two-point instance under valid schemes.
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/-- Acceptance probabilities are probabilities: for a scheme and probability weights, `0 ≤ P_i ≤ 1` (stated for two-point rewards). -/lemma spi_accept_prob_mem_Icc {N S : ℕ} (x w : Fin N → Fin 2 → ℝ) (φ : Fin N → Fin 2 → Fin S → ℝ) (T : ℝ) (i : Fin N) (hw : ∀ k, 0 ≤ w i k) (hsum : w i 0 + w i 1 = 1) (hφ : spi_is_scheme (φ i)) : 0 ≤ spi_accept_prob x w φ T i ∧ spi_accept_prob x w φ T i ≤ 1 := by obtain ⟨A, hA, hP, -, -⟩ := spi_accept_reduction x w φ T i hw hφ rw [hP, Fin.sum_univ_two] constructor <;> linarith [hA 0, hA 1]