AFTD Auto-Formalizing Theoretical Domains

spi_two_point_equilibrium_exists

theoremverifiedformalization

Existence of equilibrium (Proposition 3.1 for two-point rewards): for every static threshold and S >= 2 signals, all players using the two-point scheme is an equilibrium.

Statement

theorem spi_two_point_equilibrium_exists {N S : ℕ} (hS : 2 ≤ S) (x w : Fin N → Fin 2 → ℝ)
    (hinst : spi_is_two_point_instance x w) (T : ℝ) :
    spi_is_equilibrium x w T (fun i => spi_two_point_scheme S (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 with Remark 3.2 (each player's equilibrium strategy depends only on T, so the profile of optimal schemes is an equilibrium); special case of two-point rewards, finite signal sets
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
  • spi_accept_probProbability that the searcher accepts player i when she reaches it.
  • spi_player_payoffPlayer i's payoff: the probability that the searcher selects it.
  • spi_is_schemeA signaling scheme of one player: for every support point a probability distribution over the S signals.
  • spi_is_equilibriumNash equilibrium of the players' signaling game induced by a static threshold T: no player can raise its selection probability by…
  • 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_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_two_point_schemeThe optimal scheme of Proposition 3.1 for a two-point reward embedded in S signals: high value sends signal 0, low value sends signal 0…
  • spi_two_point_scheme_specFor S >= 2 the two-point scheme is a valid scheme and a player using it is accepted with probability exactly spi_two_point_max_prob.
  • spi_reach_prob_updateA unilateral deviation of player i does not change the probability that the search reaches i.
  • spi_is_two_point_instanceTwo-point instances: every player's reward is x_i0 with probability w_i0 and x_i1 otherwise, with 0 <= x_i1 <= x_i0.
  • spi_reach_prob_nonnegReach probabilities are nonnegative in a two-point instance under valid schemes.
Used by 1

Lean source view module on GitHub

/-- Existence of equilibrium (Prop. 3.1 of arXiv:2409.18269, for two-point rewards): for every static threshold `T` and `S ≥ 2` signals, the profile in which every player uses `spi_two_point_scheme` is an equilibrium. -/theorem spi_two_point_equilibrium_exists {N S : ℕ} (hS : 2 ≤ S) (x w : Fin N → Fin 2 → ℝ)    (hinst : spi_is_two_point_instance x w) (T : ℝ) :    spi_is_equilibrium x w T (fun i => spi_two_point_scheme S (x i 0) (x i 1) (w i 0) T) := by  set φ : Fin N → Fin 2 → Fin S → ℝ := fun i => spi_two_point_scheme S (x i 0) (x i 1) (w i 0) T with hφdef  have spec : ∀ i, spi_is_scheme (φ i) ∧ ∀ φ' : Fin N → Fin 2 → Fin S → ℝ, φ' i = φ i →      spi_accept_prob x w φ' T i = spi_two_point_max_prob (x i 0) (x i 1) (w i 0) T := by    intro i    obtain ⟨-, hlh, h0, h1, hw1⟩ := hinst i    exact spi_two_point_scheme_spec hS x w T i _ _ _ rfl rfl rfl hw1 hlh h0 h1  refine ⟨fun i => (spec i).1, fun i ψ hψ => ?_⟩  obtain ⟨-, hlh, h0, h1, hw1⟩ := hinst i  unfold spi_player_payoff  rw [spi_reach_prob_update, (spec i).2 φ rfl]  have hb := (spi_two_point_bound x w (Function.update φ i ψ) T i hlh h0 h1 hw1    (by rw [Function.update_self]; exact hψ)).1  exact mul_le_mul_of_nonneg_left hb (spi_reach_prob_nonneg x w hinst φ (fun j => (spec j).1) T i)
See it in the graphDiscuss this resultChallenge it