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
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.
/-- 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⟩