Proof of Lemma 12, p. 14 — if λ* ≤ t, some strategy y* ∈ Δ has every row payoff (My*)ₖ ≤ t
ProvedQZeroSum19.LPReduce.exists_strategy_lelp-reductionminimaxp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1zero-sum-game
Let be a real matrix with finite row set and finite nonempty column set , let be its game value, and let . If , then there is a strategy with
In the proof of Lemma 12 this is the step "if and is a strategy with this value, then ", applied to and : the value of the game is achieved by some strategy of the column player.
Formalization Note The statement is posed for any finite matrix, with the column type nonempty so that the simplex is nonempty; the game matrix (6) has columns.
Preamble
import Mathlib import Definitions.Def_QZeroSum19_LPReduce_Setting open Matrix
Formal statement
namespace QZeroSum19.LPReduce
theorem exists_strategy_le {ι κ : Type*} [Fintype ι] [Fintype κ] [Nonempty κ]
(M : Matrix ι κ ℝ) (t : ℝ) (ht : QZeroSum19.GK.gameValue M ≤ t) :
∃ y ∈ stdSimplex ℝ κ, ∀ k, (M *ᵥ y) k ≤ t := 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, second case ("y* = (y, z, h) is a strategy with this value, then … A‴y* ≤ 2ε‴")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.