spi_accept_reduction
lemmaverified
The acceptance probability, accepted value and posterior-mean constraint of any scheme depend only on accepted masses A_k in [0, w_ik] satisfying T sum A_k <= sum A_k x_ik.
Statement
open Finset in lemma spi_accept_reduction {N K S : ℕ} (x w : Fin N → Fin K → ℝ) (φ : Fin N → Fin K → Fin S → ℝ) (T : ℝ) (i : Fin N) (hw : ∀ k, 0 ≤ w i k) (hφ : spi_is_scheme (φ i)) : ∃ A : Fin K → ℝ, (∀ k, 0 ≤ A k ∧ A k ≤ w i k) ∧ spi_accept_prob x w φ T i = ∑ k, A k ∧ spi_accept_value x w φ T i = ∑ k, A k * x i k ∧ T * ∑ k, A k ≤ ∑ k, A k * x i k
- 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 6
- spi_signal_massProbability of signal s of player i in the prophet search game with strategic reward signaling: sum over support points k of w_ik phi_ik(s).
- spi_signal_valueReward-weighted probability of signal s of player i: probability of s times the searcher's posterior mean reward given s.
- spi_acceptedThe signals of player i on which the static-threshold searcher with threshold T stops: those with posterior mean at least T.
- 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.
- Used by 2
- spi_two_point_boundFor 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…
- spi_accept_prob_mem_IccAcceptance probabilities of valid schemes on two-point rewards lie in [0, 1].
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/-- The accepted probability, accepted value and the posterior-mean constraint of any scheme only depend on the accepted mass `A k ∈ [0, w i k]` of every support point. -/lemma spi_accept_reduction {N K S : ℕ} (x w : Fin N → Fin K → ℝ) (φ : Fin N → Fin K → Fin S → ℝ) (T : ℝ) (i : Fin N) (hw : ∀ k, 0 ≤ w i k) (hφ : spi_is_scheme (φ i)) : ∃ A : Fin K → ℝ, (∀ k, 0 ≤ A k ∧ A k ≤ w i k) ∧ spi_accept_prob x w φ T i = ∑ k, A k ∧ spi_accept_value x w φ T i = ∑ k, A k * x i k ∧ T * ∑ k, A k ≤ ∑ k, A k * x i k := by refine ⟨fun k => ∑ s ∈ spi_accepted x w φ T i, w i k * φ i k s, fun k => ⟨?_, ?_⟩, ?_, ?_, ?_⟩ · exact Finset.sum_nonneg fun s _ => mul_nonneg (hw k) (hφ.1 k s) · show (∑ s ∈ spi_accepted x w φ T i, w i k * φ i k s) ≤ w i k rw [← Finset.mul_sum] calc w i k * ∑ s ∈ spi_accepted x w φ T i, φ i k s ≤ w i k * ∑ s, φ i k s := by apply mul_le_mul_of_nonneg_left _ (hw k) exact Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ _) fun s _ _ => hφ.1 k s _ = w i k := by rw [hφ.2 k, mul_one] · simp only [spi_accept_prob, spi_signal_mass] exact Finset.sum_comm · simp only [spi_accept_value, spi_signal_value, Finset.sum_mul] exact Finset.sum_comm · have h1 : T * ∑ k, ∑ s ∈ spi_accepted x w φ T i, w i k * φ i k s = ∑ s ∈ spi_accepted x w φ T i, T * spi_signal_mass w φ i s := by rw [Finset.sum_comm, Finset.mul_sum]; rfl have h2 : ∑ k, (∑ s ∈ spi_accepted x w φ T i, w i k * φ i k s) * x i k = ∑ s ∈ spi_accepted x w φ T i, spi_signal_value x w φ i s := by simp only [spi_signal_value, Finset.sum_mul]; exact Finset.sum_comm rw [h1, h2] exact Finset.sum_le_sum fun s hs => (Finset.mem_filter.mp hs).2