AFTD Auto-Formalizing Theoretical Domains

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

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