spi_reach_prob_update
lemmaverified
A unilateral deviation of player i does not change the probability that the search reaches i.
Statement
open Finset in lemma spi_reach_prob_update {N K S : ℕ} (x w : Fin N → Fin K → ℝ) (φ : Fin N → Fin K → Fin S → ℝ) (T : ℝ) (i : Fin N) (ψ : Fin K → Fin S → ℝ) : spi_reach_prob x w (Function.update φ i ψ) T i = spi_reach_prob x w φ T i
- 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 2
- spi_reach_probProbability that the search reaches player i: all earlier players are rejected (independence across players).
- spi_accept_congrAcceptance probability and accepted value of player i depend only on player i's own scheme.
- Used by 2
- 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/-- A unilateral deviation of player `i` does not change the probability that the search reaches `i`. -/lemma spi_reach_prob_update {N K S : ℕ} (x w : Fin N → Fin K → ℝ) (φ : Fin N → Fin K → Fin S → ℝ) (T : ℝ) (i : Fin N) (ψ : Fin K → Fin S → ℝ) : spi_reach_prob x w (Function.update φ i ψ) T i = spi_reach_prob x w φ T i := by unfold spi_reach_prob refine Finset.prod_congr rfl fun j hj => ?_ have hji : j ≠ i := ne_of_lt (Finset.mem_filter.mp hj).2 rw [(spi_accept_congr x w (Function.update φ i ψ) φ T j (Function.update_of_ne hji ψ φ)).1]