spi_two_point_bound
lemmaverifiedformalization
For a two-point reward, every scheme's acceptance probability is at most spi_two_point_max_prob, and if it attains it the accepted value equals spi_two_point_max_value.
Statement
open Finset in lemma spi_two_point_bound {N S : ℕ} (x w : Fin N → Fin 2 → ℝ) (φ : Fin N → Fin 2 → Fin S → ℝ) (T : ℝ) (i : Fin N) (hlh : x i 1 ≤ x i 0) (hq0 : 0 ≤ w i 0) (hq1 : w i 0 ≤ 1) (hw1 : w i 1 = 1 - w i 0) (hφ : spi_is_scheme (φ i)) : spi_accept_prob x w φ T i ≤ spi_two_point_max_prob (x i 0) (x i 1) (w i 0) T ∧ (spi_two_point_max_prob (x i 0) (x i 1) (w i 0) T ≤ spi_accept_prob x w φ T i → spi_accept_value x w φ T i = spi_two_point_max_value (x i 0) (x i 1) (w i 0) T)
- Formalizes
- Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling, NeurIPS 2024 (arXiv:2409.18269), Proposition 3.1 (optimal information revealing strategy under threshold T); special case of two-point rewards, finite signal sets
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- spi_accept_probProbability that the searcher accepts player i when she reaches it.
- spi_accept_valueExpected reward collected from player i on the event that it is reached and accepted.
- spi_is_schemeA signaling scheme of one player: for every support point a probability distribution over the S signals.
- spi_two_point_max_probProposition 3.1 for a two-point reward (h with probability q, else l): the largest acceptance probability achievable under threshold T (1…
- spi_two_point_max_valueThe searcher's expected reward from a two-point player using an optimal scheme (E[X] if T <= E[X], T times the pooling probability if E[X]…
- 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]…
- spi_two_point_coreReal-arithmetic core of Proposition 3.1 for two-point rewards: accepted masses with posterior mean at least T have total at most…
- Used by 3
- spi_two_point_aboveAbove its high value (T > h) a two-point player is never accepted, whatever its scheme.
- 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…
- spi_two_point_equilibrium_pinnedIn every equilibrium of a two-point instance, every player reached with positive probability is accepted with probability…
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 a two-point reward (`x i 0 = h ≥ x i 1 = l`, `w i 0 = q`, `w i 1 = 1 - q`), every scheme's acceptance probability is at most `spi_two_point_max_prob`, and if it attains it the accepted value equals `spi_two_point_max_value`. -/lemma spi_two_point_bound {N S : ℕ} (x w : Fin N → Fin 2 → ℝ) (φ : Fin N → Fin 2 → Fin S → ℝ) (T : ℝ) (i : Fin N) (hlh : x i 1 ≤ x i 0) (hq0 : 0 ≤ w i 0) (hq1 : w i 0 ≤ 1) (hw1 : w i 1 = 1 - w i 0) (hφ : spi_is_scheme (φ i)) : spi_accept_prob x w φ T i ≤ spi_two_point_max_prob (x i 0) (x i 1) (w i 0) T ∧ (spi_two_point_max_prob (x i 0) (x i 1) (w i 0) T ≤ spi_accept_prob x w φ T i → spi_accept_value x w φ T i = spi_two_point_max_value (x i 0) (x i 1) (w i 0) T) := by have hw : ∀ k, 0 ≤ w i k := by intro k; fin_cases k · exact hq0 · simp only [Fin.mk_one, hw1]; linarith obtain ⟨A, hA, hP, hV, hc⟩ := spi_accept_reduction x w φ T i hw hφ simp only [Fin.sum_univ_two] at hP hV hc have hA1 := hA 1 rw [hw1] at hA1 have core := spi_two_point_core (x i 0) (x i 1) (w i 0) T (A 0) (A 1) hlh hq0 hq1 (hA 0).1 (hA 0).2 hA1.1 hA1.2 hc rw [hP, hV] exact core