§5.1, value rounding bound — rounding α_j to ⌈Mα_j⌉/A moves the vector by less than 2r/M in ℓ1
ProvedBlottoFPTAS.Main.rounding_boundalgorithmic-game-theorycolonel-blottonash-equilibriump2o-gran-per-chapterp2o-plan-paperp2o-v1
For positive numbers summing to one and a scale , let and , and replace each by . The new numbers are positive and sum to one, , and
Both value roundings of §5.1 (scales and ) use this bound.
Differences from the source:
- encoding: the new numbers have the common denominator A → not a separate clause: a_j are natural numbers and A their sum, so a_j/A has denominator A by construction; reason: a definitional fact, not a mathematical claim
Preamble
import Mathlib
Formal statement
namespace BlottoFPTAS.Main
/-- **§5.1, value rounding bound** (Bichler, Ghosh, arXiv:2611.05221, held version sha256
cac3638e…, p. 30). For positive numbers `α_1, …, α_r` summing to one and a scale `M > 0`, let
`a_j = ⌈M α_j⌉` and `A = ∑_j a_j`. Then the numbers `a_j / A` are positive and sum to one,
`M ≤ A < M + r`, and
`∑_j |a_j/A − α_j| ≤ ∑_j |a_j/A − Mα_j/A| + ∑_j |Mα_j/A − α_j| = 2(A − M)/A < 2r/M`. -/
theorem rounding_bound {r : ℕ} (α : Fin r → ℝ) (hα : ∀ j, 0 < α j) (hsum : ∑ j, α j = 1)
(M : ℝ) (hM : 0 < M) :
let a : Fin r → ℕ := fun j => ⌈M * α j⌉₊
let A : ℝ := ∑ j, (a j : ℝ)
(∀ j, 0 < (a j : ℝ) / A) ∧ ∑ j, (a j : ℝ) / A = 1 ∧
M ≤ A ∧ A < M + r ∧
∑ j, |(a j : ℝ) / A - α j| ≤
∑ j, |(a j : ℝ) / A - M * α j / A| + ∑ j, |M * α j / A - α j| ∧
∑ j, |(a j : ℝ) / A - M * α j / A| + ∑ j, |M * α j / A - α j| = 2 * (A - M) / A ∧
2 * (A - M) / A < 2 * r / M := by sorry
end BlottoFPTAS.Main
Source
Bichler, Ghosh, Efficient Equilibrium Computation in Colonel Blotto Games, arXiv:2611.05221 (held version, sha256 cac3638e…), p. 30, §5.1, value rounding bound
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.