Theorem 6.9 — target quadratic approximation by a gadget chain, remainder bound
ProvedLinearChoresCLS.theorem_6_9choresclscompetitive-equilibriumfisher-marketp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let with and , and consider the completed market with the parameters (7.1) and (6.9). For every chain and every ,
The remainder satisfies for every and every coordinate segment from to in the box; moreover, for every feasible coordinate direction at , the right directional derivative exists and .
The gadget chain realizes the negative squared difference needed to turn the basic market's quadratic into .
Formalization Note and are the paper's explicit formulas, with gadget prices from the max–min rule; . Ties of the max–min rule are not excluded.
Differences from the source:
- encoding: chains 0 ≤ j < j′ ≤ n, x₀ = 0 → π : Pair n (a subtype of Fin (n+1) × Fin (n+1)), x extended by Fin.cons 0; reason: index conventions; same instances
Preamble
import Mathlib import Definitions.Def_LinearChoresCLS_Remainders import Definitions.Def_LinearChoresCLS_RightDeriv open Finset NetworkEquilibriumCLS.LinearNash
Formal statement
namespace LinearChoresCLS
/-- **Theorem 6.9 (Target quadratic approximation)** (arXiv:2611.06589, held version sha256
85d34a9e…, p.24). For the completed market `f(I)` of an instance `I = (A, c, ε)` (`n ≥ 1`,
`ε > 0`, parameters (7.1) and (6.9)) and every chain `0 ≤ j < j′ ≤ n`: for every `x ∈ [0,1]ⁿ`,
`−(w_{jj′}/2) t² (x_j − x_{j′})² = P_{(j,j′)}(x) + R_{(j,j′)}(x)` (6.11); the remainder satisfies
`|R_{(j,j′)}(x + he_ℓ) − R_{(j,j′)}(x)| ≤ 12 w_{jj′} t³ |h|` for every `ℓ ∈ [n]` and every coordinate
segment from `x` to `x + he_ℓ` in the box; and for every feasible coordinate direction
`ṽ ∈ {±e_ℓ}` at `x` the right directional derivative exists and `|R′_{(j,j′)}(x; ṽ)| ≤ 12 w_{jj′} t³`.
**Formalization Note.** `x₀ = 0`; `P_{(j,j′)}` is `chainAbs` and `R_{(j,j′)} = R̃ + R̂` is
`chainRem`, both from the paper's explicit formulas, with the gadget prices given by the max–min
rule. -/
theorem theorem_6_9 {n : ℕ} (hn : 0 < n) (P : Quadratic n) (ε : ℚ) (hε : 0 < ε) (π : Pair n) :
(∀ x : Fin n → ℝ, InCube x →
-(pairWeight P π / 2) * tParam P ε ^ 2 * (xExt x π.1.1 - xExt x π.1.2) ^ 2 =
chainAbs P (tParam P ε) (chainLength P ε) π x +
chainRem P (tParam P ε) (chainLength P ε) π x) ∧
(∀ (x : Fin n → ℝ) (ℓ : Fin n) (h : ℝ), InCube x → InCube (x + h • Pi.single ℓ (1 : ℝ)) →
|chainRem P (tParam P ε) (chainLength P ε) π (x + h • Pi.single ℓ (1 : ℝ)) -
chainRem P (tParam P ε) (chainLength P ε) π x| ≤
12 * pairWeight P π * tParam P ε ^ 3 * |h|) ∧
(∀ (x : Fin n → ℝ) (ℓ : Fin n) (s : Bool), InCube x → FeasibleCoordDir x ℓ s →
∃ D : ℝ, HasRightDerivAt0
(fun h => chainRem P (tParam P ε) (chainLength P ε) π (x + h • coordDir ℓ s)) D ∧
|D| ≤ 12 * pairWeight P π * tParam P ε ^ 3) := by sorry
end LinearChoresCLS
Source
Liu–Ma–Tao–Yang–Zheng, Competitive Equilibrium for Linear Chores is CLS-complete, arXiv:2611.06589 (held version, sha256 85d34a9e048d151ecff70a8614b9c2dd44307d5cf60faba74d14b2dd7eedc0b5), Theorem 6.9, Eq. (6.11), p.24 (proof Appendix C.1, pp.46–47)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.