AFTD Auto-Formalizing Theoretical Domains

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

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