Proof of Lemma 21, p. 48 — t_i = max_l ((Σ_{j≤l} z_ij) − 1)/l for the sorted vector z_i
ProvedFixpNash.DivFree.threshold_eq_sup_prefixfixed-pointnash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1simplex
Fix a finite game, a real vector , and a player with pure strategies. Let and let be sorted in decreasing order, . Then the threshold (the unique solution of ) is
This closed form is what lets be computed by a circuit with gates and rational constants only (Lemma 21): a sorting network produces , and the divisions are by the integer constants .
Formalization Note. The sorted order is given by a bijection (so ) along which is nonincreasing; the 0-based index corresponds to the paper's , hence the denominator and the prefix . The statement holds for every real vector .
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
/-- Proof of Lemma 21, p. 48: if `e` lists the `n + 1` strategies of player `i` so that
`zₗ = hᵢ,e(l)(x)` is decreasing in `l`, then
`tᵢ = max_{l = 1, …, n+1} ((∑_{k ≤ l} z_k) − 1) / l` (indices shifted to `Fin (n + 1)`).
Holds for every real vector `x`. -/
theorem threshold_eq_sup_prefix {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(u : ι → (∀ i, S i) → ℝ)
(x : ∀ i, S i → ℝ) (i : ι) (n : ℕ) (e : Fin (n + 1) ≃ S i)
(hz : Antitone (fun l : Fin (n + 1) => hVal u x i (e l))) :
threshold u x i =
Finset.univ.sup' Finset.univ_nonempty (fun l : Fin (n + 1) =>
((∑ k ∈ Finset.Iic l, hVal u x i (e k)) - 1) / ((l : ℕ) + 1 : ℝ)) := 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, proof of Lemma 21, p. 48
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.