p. 47 — f_{i,x}(t) = 1 has a unique solution t_i
ProvedFixpNash.DivFree.threshold_specfixed-pointgame-theorynash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a finite game, a real vector indexed by player–strategy pairs, and a player whose strategy set is nonempty. Let and . Then the equation has exactly one real solution, and it is the threshold :
The paper observes that is continuous, piecewise linear, equal to in the limit , strictly decreasing up to and from there on, and concludes that there is a unique with . This statement certifies that the threshold used in the definition of is that value.
Formalization Note. The statement holds for every real vector , not only for mixed profiles. The hypothesis is the paper's tacit assumption: with the function is identically and no threshold exists.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_DGPNash_NashMap_nashMap import Definitions.Def_FixpNash_DivFree_Map
Formal statement
namespace FixpNash.DivFree
/-- p. 47: for a player with a nonempty strategy set, `f_{i,x}(t) = 1` has exactly one
solution `t`, and it is `threshold u x i`. Holds for every real vector `x`. -/
theorem threshold_spec {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(u : ι → (∀ i, S i) → ℝ)
(x : ∀ i, S i → ℝ) (i : ι) (hi : Nonempty (S i)) :
fSum u x i (threshold u x i) = 1 ∧
∀ t : ℝ, fSum u x i t = 1 → t = threshold u x i := by sorry
end FixpNash.DivFree
Source
Etessami & Yannakakis, On the complexity of Nash equilibria and other fixed points, author manuscript (SIAM J. Comput. 39 (2010)), Section 4, definition of G_I, p. 47
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.