Proof of Proposition 3, p. 21 — first case: g_{i,j} < 0 and x_{i,j} ≥ ε/2cn² force Σ_l φ_{i,l} < ε
ProvedFixpNash.WeakApprox.first_case_sum_ltfixed-pointnash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , , , and be as in the coordinatewise bound, and let be a weak -approximate fixed point of Nash's function. If, for a player , some strategy has negative gain and probability
then
This is the first of the two cases into which the paper splits the end of the proof of Proposition 3; it bounds every positive gain of player by at once.
Formalization Note "One of the strategies on the rhs" means , i.e. , which is the hypothesis used. is read as .
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_FixpNash_WeakApprox_NashFunction import Definitions.Def_FixpNash_WeakApprox_GameConstants
Formal statement
namespace FixpNash.WeakApprox
/-- Proof of Proposition 3, p. 21, first case: if some strategy `j` with `g_{i,j}(x) < 0` has
`x_{i,j} ≥ ε/(2cn²)`, then `Σ_l φ_{i,l}(x) < ε`. -/
theorem first_case_sum_lt {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)]
(u : ι → (∀ i, S i) → ℝ) (ε : ℝ) (hε : 0 < ε) (hε1 : ε ≤ 1) (x : ∀ i, S i → ℝ)
(hx : IsWeakApproxFixedPoint u x
(ε ^ 2 / (4 * cConst u ^ 2 * (maxNumStrategies S : ℝ) ^ 3)))
(i : ι) (j : S i) (hg : gain u x i j < 0)
(hxj : ε / (2 * cConst u * (maxNumStrategies S : ℝ) ^ 2) ≤ x i j) :
∑ l : S i, max 0 (gain u x i l) < ε := by sorry
end FixpNash.WeakApprox
Source
Etessami & Yannakakis, On the complexity of Nash equilibria and other fixed points, author manuscript (SIAM J. Comput. 39 (2010)), proof of Proposition 3, second direction, first case, p. 21
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.