spx_payoff_mid
lemmaverified
For 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 = (3/5)/(T-3), p2 = (10/3)/T.
Statement
open Finset in lemma spx_payoff_mid {S : ℕ} (hS : 2 ≤ S) (T : ℝ) (φ : Fin 4 → Fin 2 → Fin S → ℝ) (heq : spi_is_equilibrium spx_x spx_w T φ) (hT1 : 24 / 5 < T) (hT2 : T ≤ 9) : spi_searcher_payoff spx_x spx_w φ T = T * ((3 / 5) / (T - 3)) + (1 - (3 / 5) / (T - 3)) * (10 / 3 + (1 - (10 / 3) / T) * (8 / 5))
- Source
- step towards strategic_prophet_no_half_robust_static_threshold (no static threshold is 1/2-robust, open in Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling, NeurIPS 2024 (arXiv:2409.18269), Remark 4.1 and Sec. 6)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- spi_searcher_payoffThe searcher's expected payoff u_s(T) under static threshold T and the players' signaling schemes.
- 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_equilibrium_pinnedIn every equilibrium of a two-point instance, every player reached with positive probability is accepted with probability…
- spi_two_point_aboveAbove its high value (T > h) a two-point player is never accepted, whatever its scheme.
- spi_two_point_max_midIf E[X] < T <= h, a two-point player's optimal acceptance probability is q(h-l)/(T-l), at posterior mean exactly T.
- 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).
- spx_xSupport values of the four-player instance: X0 = 24/5 surely; X1 in {9, 3}; X2 in {1000, 0}; X3 in {40, 0}.
- spx_wProbabilities of the four-player instance: 1; 1/10 for 9; 1/300 for 1000; 1/25 for 40.
- spx_instanceThe four-player instance is a two-point instance.
- spx_valsThe support values and probabilities of the four-player instance, entry by entry.
- Used by 2
- 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…
- spx_searcher_payoff_at_nineWith threshold T = 9, every equilibrium of the four-player instance gives the searcher exactly 721/150.
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.
open Finset in/-- In any equilibrium with threshold `24/5 < T ≤ 9`, the searcher's payoff in the four-player instance is `T p₁ + (1 - p₁)(10/3 + (1 - p₂) 8/5)` with `p₁ = (3/5)/(T - 3)` and `p₂ = (10/3)/T`. -/lemma spx_payoff_mid {S : ℕ} (hS : 2 ≤ S) (T : ℝ) (φ : Fin 4 → Fin 2 → Fin S → ℝ) (heq : spi_is_equilibrium spx_x spx_w T φ) (hT1 : 24 / 5 < T) (hT2 : T ≤ 9) : spi_searcher_payoff spx_x spx_w φ T = T * ((3 / 5) / (T - 3)) + (1 - (3 / 5) / (T - 3)) * (10 / 3 + (1 - (10 / 3) / T) * (8 / 5)) := by obtain ⟨r0, r1, r2, r3⟩ := spi_reach_prob_fin_four spx_x spx_w φ T have a0 := spi_two_point_above spx_x spx_w spx_instance T φ (i := 0) (heq.1 0) (by simp [spx_x]; linarith) have p1 := spi_two_point_equilibrium_pinned hS spx_x spx_w spx_instance T φ heq 1 (by rw [r1, a0.1]; norm_num) have hT3 : 0 < T - 3 := by linarith obtain ⟨x00, x01, w00, x10, x11, w10, x20, x21, w20, x30, x31, w30⟩ := spx_vals have mid1 := spi_two_point_max_mid 9 3 (1 / 10) T (by norm_num; linarith) hT2 have hm1 : spi_two_point_max_prob (spx_x 1 0) (spx_x 1 1) (spx_w 1 0) T = (3 / 5) / (T - 3) := by rw [x10, x11, w10, mid1.1]; ring have hv1 : spi_two_point_max_value (spx_x 1 0) (spx_x 1 1) (spx_w 1 0) T = T * ((3 / 5) / (T - 3)) := by rw [x10, x11, w10, mid1.2]; ring have hP1 : (3 / 5) / (T - 3) < 1 := by rw [div_lt_one hT3]; linarith have p2 := spi_two_point_equilibrium_pinned hS spx_x spx_w spx_instance T φ heq 2 (by rw [r2, a0.1, p1.1, hm1]; nlinarith) have mid2 := spi_two_point_max_mid 1000 0 (1 / 300) T (by norm_num; linarith) (by linarith) have hm2 : spi_two_point_max_prob (spx_x 2 0) (spx_x 2 1) (spx_w 2 0) T = (10 / 3) / T := by rw [x20, x21, w20, mid2.1]; ring have hv2 : spi_two_point_max_value (spx_x 2 0) (spx_x 2 1) (spx_w 2 0) T = 10 / 3 := by rw [x20, x21, w20, mid2.2]; have hT0' : T ≠ 0 := by linarith field_simp; try ring have hP2 : (10 / 3) / T < 1 := by rw [div_lt_one (by linarith)]; linarith have p3 := spi_two_point_equilibrium_pinned hS spx_x spx_w spx_instance T φ heq 3 (by rw [r3, a0.1, p1.1, p2.1, hm1, hm2]; apply mul_pos <;> nlinarith) have mid3 := spi_two_point_max_mid 40 0 (1 / 25) T (by norm_num; linarith) (by linarith) have hv3 : spi_two_point_max_value (spx_x 3 0) (spx_x 3 1) (spx_w 3 0) T = 8 / 5 := by rw [x30, x31, w30, mid3.2]; have hT0' : T ≠ 0 := by linarith field_simp; try ring simp only [spi_searcher_payoff, Fin.sum_univ_four, r0, r1, r2, r3, a0.1, a0.2, p1.1, p1.2, p2.1, p2.2, p3.2, hm1, hv1, hm2, hv2, hv3] ring