AFTD Auto-Formalizing Theoretical Domains

spi_reach_prob

def

Probability that the search reaches player i: all earlier players are rejected (independence across players).

Statement

open Finset in
noncomputable def spi_reach_prob {N K S : ℕ} (x w : Fin N → Fin K → ℝ) (φ : Fin N → Fin K → Fin S → ℝ)
    (T : ℝ) (i : Fin N) : ℝ
Defined in
Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling, NeurIPS 2024 (arXiv:2409.18269), Sec. 2-3 (model, Definition 2.4, Proposition 3.1), Remark 4.1 and Sec. 6; formalized by the operator (Claude), 2026-10-04, for finite reward supports and finite signal sets
Verified
03 Oct 2026
Axioms
none listed
Built on 1
  • spi_accept_probProbability that the searcher accepts player i when she reaches it.
Used by 6
  • spi_reach_prob_fin_fourFor four players the reach probabilities are 1, 1-P0, (1-P0)(1-P1) and (1-P0)(1-P1)(1-P2).
  • spi_searcher_payoffThe searcher's expected payoff u_s(T) under static threshold T and the players' signaling schemes.
  • spi_reach_prob_nonnegReach probabilities are nonnegative in a two-point instance under valid schemes.
  • spi_reach_prob_updateA unilateral deviation of player i does not change the probability that the search reaches i.
  • spi_player_payoffPlayer i's payoff: the probability that the searcher selects it.
  • 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
/-- Probability that the search reaches player `i`, i.e. every earlier player is rejected (rewards and signals are independent across players). -/
noncomputable def spi_reach_prob {N K S : ℕ} (x w : Fin N → Fin K → ℝ) (φ : Fin N → Fin K → Fin S → ℝ)
    (T : ℝ) (i : Fin N) : ℝ :=
  ∏ j ∈ univ.filter (fun j => j < i), (1 - spi_accept_prob x w φ T j)
See it in the graphDiscuss this resultChallenge it