AFTD Auto-Formalizing Theoretical Domains

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

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