AFTD Auto-Formalizing Theoretical Domains

spi_is_equilibrium

def

Nash equilibrium of the players' signaling game induced by a static threshold T: no player can raise its selection probability by unilaterally switching schemes.

Statement

def spi_is_equilibrium {N K S : ℕ} (x w : Fin N → Fin K → ℝ) (T : ℝ) (φ : Fin N → Fin K → Fin S → ℝ) : Prop
Defined in
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; formalized by the operator (Claude), 2026-10-04, for finite reward supports and finite signal sets
Verified
03 Oct 2026
Axioms
none listed
Built on 2
  • 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.
Used by 6
  • 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…
  • 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…
  • spx_searcher_payoff_at_nineWith threshold T = 9, every equilibrium of the four-player instance gives the searcher exactly 721/150.
  • spi_two_point_equilibrium_existsExistence of equilibrium (Proposition 3.1 for two-point rewards): for every static threshold and S >= 2 signals, all players using the…
  • spi_two_point_equilibrium_pinnedIn every equilibrium of a two-point instance, every player reached with positive probability is accepted with probability…

Lean source view module on GitHub

/-- Nash equilibrium of the players' signaling game induced by the static threshold `T`: no player can raise its selection probability by switching to another scheme. -/
def spi_is_equilibrium {N K S : ℕ} (x w : Fin N → Fin K → ℝ) (T : ℝ) (φ : Fin N → Fin K → Fin S → ℝ) : Prop :=
  (∀ i, spi_is_scheme (φ i)) ∧
    ∀ i (ψ : Fin K → Fin S → ℝ), spi_is_scheme ψ →
      spi_player_payoff x w (Function.update φ i ψ) T i ≤ spi_player_payoff x w φ T i
See it in the graphDiscuss this resultChallenge it