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
- strategic_prophet_no_half_robust_static_thresholdNegative answer to the open question of arXiv:2409.18269: in a four-player two-point instance, equilibria exist for every static…
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.
/-- 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)