Proof of Lemma 12, p. 14, (7)–(8) — for ŷ = 2Ry: bᵀŷ ≥ α − 6Rε‴ and Aŷ ≤ c + 6Rε‴ (under |α|, |cᵢ| ≤ R)
ProvedQZeroSum19.LPReduce.eq_7_8linear-programminglp-reductionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1zero-sum-game
Let , , , , with for all and , and let . Let be the game matrix (6) (second row ), and let satisfy entrywise. Put . Then
With these are the displays (7) and (8) of the proof of Lemma 12: the rescaled -part of an approximately optimal strategy is an approximately feasible point of (4) whose objective is approximately at least .
Formalization Note The page's intermediate bounds and are valid as printed for and ; for general signs they hold with and , and the final bounds then need and . Only the final bounds (7) and (8) are stated. The hypothesis is a standing assumption of §4 (p. 12); is added (the binary search of §4 runs over , and (6) has entries in only when ).
Preamble
import Mathlib import Definitions.Def_QZeroSum19_LPReduce_Setting open Matrix
Formal statement
namespace QZeroSum19.LPReduce
theorem eq_7_8 {n m : ℕ} (A : Matrix (Fin n) (Fin m) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(α R κ : ℝ) (hR : 0 < R) (hc : ∀ i, |c i| ≤ R) (hα : |α| ≤ R) (hκ : 0 ≤ κ)
(y' : Fin m ⊕ Fin 2 → ℝ) (hy' : y' ∈ stdSimplex ℝ (Fin m ⊕ Fin 2))
(hle : ∀ k, (gameMatrix A b c α R *ᵥ y') k ≤ 2 * κ) :
let yhat : Fin m → ℝ := fun j => 2 * R * y' (Sum.inl j)
α - 6 * R * κ ≤ b ⬝ᵥ yhat ∧ ∀ i, (A *ᵥ yhat) i ≤ c i + 6 * R * κ := 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, (7) and (8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.