AFTD Auto-Formalizing Theoretical Domains

spx_searcher_payoff_le

theoremverifiedoriginal

In the four-player instance, for every static threshold T, every S >= 2 and every equilibrium, the searcher's expected payoff is at most 721/150.

Statement

open Finset in
theorem spx_searcher_payoff_le {S : ℕ} (hS : 2 ≤ S) (T : ℝ) (φ : Fin 4 → Fin 2 → Fin S → ℝ)
    (heq : spi_is_equilibrium spx_x spx_w T φ) :
    spi_searcher_payoff spx_x spx_w φ T ≤ 721 / 150
Related work
operator (Claude), 2026-10-04: negative answer to the open question of Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling, NeurIPS 2024 (arXiv:2409.18269), Sec. 2-3 (model, Definition 2.4, Proposition 3.1), Remark 4.1 and Sec. 6 whether a static threshold stopping policy can be 1/2-robust; four-player two-point instance found by numerical search (after a five-player instance from a search subagent), every equilibrium of every threshold gives the searcher at most 721/150 < OPT/2 = 155039/31250, checked by the Lean kernel
Verified
03 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 14
  • 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_lowIf T <= E[X], a two-point player's optimal acceptance probability is 1 and its contribution is E[X].
  • 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.
  • 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 =…
Used by 1

Lean source view module on GitHub

open Finset in/-- In the four-player instance, for every static threshold `T`, every number `S ≥ 2` of signals and every equilibrium of the players' signaling game, the searcher's expected payoff is at most `721/150`. -/theorem spx_searcher_payoff_le {S : ℕ} (hS : 2 ≤ S) (T : ℝ) (φ : Fin 4 → Fin 2 → Fin S → ℝ)    (heq : spi_is_equilibrium spx_x spx_w T φ) :    spi_searcher_payoff spx_x spx_w φ T ≤ 721 / 150 := by  obtain ⟨r0, r1, r2, r3⟩ := spi_reach_prob_fin_four spx_x spx_w φ T  have p0 := spi_two_point_equilibrium_pinned hS spx_x spx_w spx_instance T φ heq 0 (by rw [r0]; norm_num)  obtain ⟨x00, x01, w00, x10, x11, w10, x20, x21, w20, x30, x31, w30⟩ := spx_vals  by_cases hA : T ≤ 24 / 5  · have low0 := spi_two_point_max_low (24 / 5) 0 1 T (by norm_num; linarith)    have hm0 : spi_two_point_max_prob (spx_x 0 0) (spx_x 0 1) (spx_w 0 0) T = 1 := by      rw [x00, x01, w00, low0.1]    have hv0 : spi_two_point_max_value (spx_x 0 0) (spx_x 0 1) (spx_w 0 0) T = 24 / 5 := by      rw [x00, x01, w00, low0.2]; norm_num    simp only [spi_searcher_payoff, Fin.sum_univ_four, r0, r1, r2, r3, p0.1, p0.2, hm0, hv0]    norm_num  push Not at hA  by_cases hB : T ≤ 9  · rw [spx_payoff_mid hS T φ heq hA hB]    have hT3 : 0 < T - 3 := by linarith    have hT0 : 0 < T := by linarith    have key : T * ((3 / 5) / (T - 3)) + (1 - (3 / 5) / (T - 3)) * (10 / 3 + (1 - (10 / 3) / T) * (8 / 5)) =        721 / 150 - (9 - T) * (109 * T - 320) / (150 * T * (T - 3)) := by      field_simp; ring    have hnn : 0 ≤ (9 - T) * (109 * T - 320) / (150 * T * (T - 3)) := by      apply div_nonneg      · apply mul_nonneg <;> linarith      · positivity    linarith  push Not at hB  have a0 := spi_two_point_above spx_x spx_w spx_instance T φ (i := 0) (heq.1 0) (by simp [spx_x]; linarith)  have a1 := spi_two_point_above spx_x spx_w spx_instance T φ (i := 1) (heq.1 1) (by simp [spx_x]; linarith)  by_cases hC : T ≤ 1000  · have p2 := spi_two_point_equilibrium_pinned hS spx_x spx_w spx_instance T φ heq 2      (by rw [r2, a0.1, a1.1]; norm_num)    have mid2 := spi_two_point_max_mid 1000 0 (1 / 300) T (by norm_num; linarith) hC    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      have hT0' : T ≠ 0 := by linarith      rw [x20, x21, w20, mid2.2]; field_simp; try ring    have hT0 : 0 < T := by linarith    by_cases hD : T ≤ 40    · have p3 := spi_two_point_equilibrium_pinned hS spx_x spx_w spx_instance T φ heq 3        (by          rw [r3, a0.1, a1.1, p2.1, hm2]          have hP2 : (10 / 3) / T < 1 := by rw [div_lt_one hT0]; linarith          simp only [sub_zero, one_mul]; linarith)      have mid3 := spi_two_point_max_mid 40 0 (1 / 25) T (by norm_num; linarith) hD      have hv3 : spi_two_point_max_value (spx_x 3 0) (spx_x 3 1) (spx_w 3 0) T = 8 / 5 := by        have hT0' : T ≠ 0 := by linarith        rw [x30, x31, w30, mid3.2]; field_simp; try ring      simp only [spi_searcher_payoff, Fin.sum_univ_four, r0, r1, r2, r3, a0.1, a0.2, a1.1, a1.2, p2.1, p2.2,        p3.2, hm2, hv2, hv3]      have : (10 / 3) / T ≥ 1 / 12 := by rw [ge_iff_le, le_div_iff₀ hT0]; linarith      nlinarith    · push Not at hD      have a3 := spi_two_point_above spx_x spx_w spx_instance T φ (i := 3) (heq.1 3) (by simp [spx_x]; linarith)      simp only [spi_searcher_payoff, Fin.sum_univ_four, r0, r1, r2, r3, a0.1, a0.2, a1.1, a1.2, p2.1, p2.2,        a3.2, hv2]      norm_num  · push Not at hC    have a2 := spi_two_point_above spx_x spx_w spx_instance T φ (i := 2) (heq.1 2) (by simp [spx_x]; linarith)    have a3 := spi_two_point_above spx_x spx_w spx_instance T φ (i := 3) (heq.1 3) (by simp [spx_x]; linarith)    simp only [spi_searcher_payoff, Fin.sum_univ_four, r0, r1, r2, r3, a0.2, a1.2, a2.2, a3.2]    norm_num
See it in the graphDiscuss this resultChallenge it