Proof of Lemma 12, p. 14 — a primal point with Σy ≤ R and bᵀy ≥ α gives ŷ = (y/(2R), 1/2 − Σy/(2R), 1/2) ∈ Δ^{m+2} with A‴ŷ ≤ 0
ProvedQZeroSum19.LPReduce.certificatelinear-programminglp-reductionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1zero-sum-game
Let , , , and , and let be the game matrix (6) (with second row ). Suppose satisfies , , and . Put
Then lies in the simplex and
This is the certificate of the first case of the proof of Lemma 12: if , the game (6) has a strategy for the column player that keeps every row payoff nonpositive.
Formalization Note The conclusion states and that every entry of is at most ; the explicit values of the entries are not part of the statement. The columns are indexed by Fin m ⊕ Fin 2, with at inr 0 and at inr 1.
Preamble
import Mathlib import Definitions.Def_QZeroSum19_LPReduce_Setting open Matrix
Formal statement
namespace QZeroSum19.LPReduce
theorem certificate {n m : ℕ} (A : Matrix (Fin n) (Fin m) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(α R : ℝ) (hR : 0 < R) (y : Fin m → ℝ) (hy : IsPrimalFeasible A c y)
(hsum : ∑ j, y j ≤ R) (hby : α ≤ b ⬝ᵥ y) :
let yhat : Fin m ⊕ Fin 2 → ℝ :=
Sum.elim (fun j => y j / (2 * R)) ![1 / 2 - (∑ j, y j) / (2 * R), 1 / 2]
yhat ∈ stdSimplex ℝ (Fin m ⊕ Fin 2) ∧ ∀ k, (gameMatrix A b c α R *ᵥ yhat) k ≤ 0 := by sorry
end QZeroSum19.LPReduce
Source
van Apeldoorn and Gilyén, Quantum algorithms for zero-sum games, arXiv:1904.03180v1, p. 14, proof of Lemma 12, first case (definition of ŷ and the display A‴ŷ ≤ 0)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.