Lemma 12, p. 14 — λ* of the game (6) known to error ε‴ = ε/(6R(r+1)) decides OPT < α or OPT ≥ α − ε (added |α| ≤ R; (6) row 2 corrected)
ProvedQZeroSum19.LPReduce.lemma_12Consider the linear program (4), with , and its dual (5), , under the standing assumptions of §4: all entries of , , lie in ; and for all ; the common optimal value of (4) and (5) is attained by a primal feasible with and by a dual feasible with . Let with , let , and put
Let be the value of the zero-sum game with matrix
that is, . If is any number with , then
In the words of the paper: finding the optimal value of the game (6) up to additive error suffices to correctly conclude either or . Combined with a binary search over and an approximate game solver, it turns any algorithm for zero-sum games into an algorithm for linear programming; Theorem 13 of the paper is obtained this way.
Formalization Note Two deviations from the page, both disclosed. (i) The second row of (6) is printed as ; the derivation on p. 13 gives , which is used. With the printed row the lemma is false (for , , , , , , one has but ). (ii) The hypothesis is added; the proof's step (7) needs it, and §4 supplies it through the binary search over and the requirement that (6) have entries in . The decision rule ( versus ) is the one of the first paragraph of the proof, which reduces to the cases and . The value is the infimum of the image of the simplex, not an infimum over a membership condition.
import Mathlib import Definitions.Def_QZeroSum19_LPReduce_Setting open Matrix
namespace QZeroSum19.LPReduce
theorem lemma_12 {n m : ℕ} (A : Matrix (Fin n) (Fin m) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(R r OPT α ε : ℝ) (hLP : LPStanding A b c R r OPT) (hα : |α| ≤ R) (hε : 0 < ε)
(lam : ℝ) (hlam : |lam - QZeroSum19.GK.gameValue (gameMatrix A b c α R)| ≤ epsGame ε R r) :
(epsGame ε R r < lam → OPT < α) ∧ (lam ≤ epsGame ε R r → α - ε ≤ OPT) := by sorry
end QZeroSum19.LPReduce
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.