AFTD Auto-Formalizing Theoretical Domains

spi_two_point_equilibrium_pinned

lemmaverifiedformalization

In every equilibrium of a two-point instance, every player reached with positive probability is accepted with probability spi_two_point_max_prob and contributes spi_two_point_max_value.

Statement

lemma spi_two_point_equilibrium_pinned {N S : ℕ} (hS : 2 ≤ S) (x w : Fin N → Fin 2 → ℝ)
    (hinst : spi_is_two_point_instance x w) (T : ℝ) (φ : Fin N → Fin 2 → Fin S → ℝ)
    (heq : spi_is_equilibrium x w T φ) (i : Fin N) (hr : 0 < spi_reach_prob x w φ T i) :
    spi_accept_prob x w φ T i = spi_two_point_max_prob (x i 0) (x i 1) (w i 0) T ∧
      spi_accept_value x w φ T i = spi_two_point_max_value (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 (equilibrium play is the optimal threshold signaling); 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_accept_valueExpected reward collected from player i on the event that it is reached and accepted.
  • spi_reach_probProbability that the search reaches player i: all earlier players are rejected (independence across players).
  • spi_player_payoffPlayer i's payoff: the probability that the searcher selects it.
  • 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_max_valueThe searcher's expected reward from a two-point player using an optimal scheme (E[X] if T <= E[X], T times the pooling probability if E[X]…
  • 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_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.
Used by 2
  • spx_payoff_midFor 24/5 < T <= 9, every equilibrium of the four-player instance gives the searcher T p1 + (1-p1)(10/3 + (1-p2) 8/5) with p1 =…
  • spx_searcher_payoff_leIn the four-player instance, for every static threshold T, every S >= 2 and every equilibrium, the searcher's expected payoff is at most…

Lean source view module on GitHub

/-- In every equilibrium of a two-point instance, every player that is reached with positive probability gets accepted with probability `spi_two_point_max_prob` and contributes accepted value `spi_two_point_max_value` (the equilibrium outcome of Prop. 3.1). -/lemma spi_two_point_equilibrium_pinned {N S : ℕ} (hS : 2 ≤ S) (x w : Fin N → Fin 2 → ℝ)    (hinst : spi_is_two_point_instance x w) (T : ℝ) (φ : Fin N → Fin 2 → Fin S → ℝ)    (heq : spi_is_equilibrium x w T φ) (i : Fin N) (hr : 0 < spi_reach_prob x w φ T i) :    spi_accept_prob x w φ T i = spi_two_point_max_prob (x i 0) (x i 1) (w i 0) T ∧      spi_accept_value x w φ T i = spi_two_point_max_value (x i 0) (x i 1) (w i 0) T := by  obtain ⟨-, hlh, h0, h1, hw1⟩ := hinst i  have hb := spi_two_point_bound x w φ T i hlh h0 h1 hw1 (heq.1 i)  obtain ⟨hsch, hval⟩ := spi_two_point_scheme_spec hS x w T i _ _ _ rfl rfl rfl hw1 hlh h0 h1  have hdev := heq.2 i _ hsch  unfold spi_player_payoff at hdev  rw [spi_reach_prob_update, hval _ (Function.update_self i _ φ)] at hdev  have hge : spi_two_point_max_prob (x i 0) (x i 1) (w i 0) T ≤ spi_accept_prob x w φ T i :=    le_of_mul_le_mul_left hdev hr  exact ⟨le_antisymm hb.1 hge, hb.2 hge⟩
See it in the graphDiscuss this resultChallenge it