Theorem 6.12 — normalization error, remainder bound
ProvedLinearChoresCLS.theorem_6_12choresclscompetitive-equilibriumfisher-marketp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Consider the market with -layer gadget chains on all pairs, adjusted earning requirements (6.12) and adjusted supplies (6.19), with and , and let . For every ,
The remainder satisfies for every and every coordinate segment from to in ; moreover, for every feasible coordinate direction at , the right directional derivative exists and .
Normalizing the full price vector to the price domain changes the objective only by a third-order term, because of the supply adjustment (6.19).
Formalization Note is the generic objective of the market at the price families and .
Differences from the source:
- generalization: the market of Section 6.5 with the construction's t and L (Section 7: t = 2^{−L} by (7.1)) → any integer L ≥ 1 and real 0 < t < 1/8; reason: the proof (p.50) states exactly this range ("Let L ≥ 1 and 0 < t < 1/8, as in Lemma C.1"); (7.1) is an instance
Preamble
import Mathlib import Definitions.Def_LinearChoresCLS_Remainders import Definitions.Def_LinearChoresCLS_RightDeriv open Finset NetworkEquilibriumCLS.LinearNash
Formal statement
namespace LinearChoresCLS
/-- **Theorem 6.12 (Normalization error)** (arXiv:2611.06589, held version sha256 85d34a9e…,
p.29; proof pp.50–51). For the market with `L`-layer gadget chains, adjusted earning requirements
(6.12) and adjusted supplies (6.19), with `L ≥ 1` and `0 < t < 1/8`, and every `x ∈ [0,1]ⁿ`:
`Ψ(p̃(x)) = Ψ(p(x)) + R_norm(x)`, where `p̃ = ((n+1)/T) p` and `R_norm = (n+1) log(T/(n+1))`; the
remainder satisfies `|R_norm(x + he_ℓ) − R_norm(x)| ≤ 3t³|h|` for every `ℓ ∈ [n]` and every
coordinate segment from `x` to `x + he_ℓ` in `[0,1]ⁿ`; and for every feasible coordinate direction
`ṽ ∈ {±e_ℓ}` at `x` the right directional derivative exists and `|R′_norm(x; ṽ)| ≤ 3t³`.
**Formalization Note.** `Ψ` is the generic logarithmic objective of `chainMarket P t L`. The range
`L ≥ 1`, `0 < t < 1/8` is the one stated in the proof (p.50, "as in Lemma C.1"); the completed
market of (7.1) is the instance `t = 2^{−L}`, `L ≥ 8`. -/
theorem theorem_6_12 {n : ℕ} (hn : 0 < n) (P : Quadratic n) (t : ℝ) (L : ℕ) (hL : 1 ≤ L)
(ht : 0 < t) (ht8 : t < 1 / 8) :
(∀ x : Fin n → ℝ, InCube x →
(chainMarket P t L).Psi (normPrice P t L x) =
(chainMarket P t L).Psi (priceFam t L x) + Rnorm P t L x) ∧
(∀ (x : Fin n → ℝ) (ℓ : Fin n) (h : ℝ), InCube x → InCube (x + h • Pi.single ℓ (1 : ℝ)) →
|Rnorm P t L (x + h • Pi.single ℓ (1 : ℝ)) - Rnorm P t L x| ≤ 3 * t ^ 3 * |h|) ∧
(∀ (x : Fin n → ℝ) (ℓ : Fin n) (s : Bool), InCube x → FeasibleCoordDir x ℓ s →
∃ D : ℝ, HasRightDerivAt0 (fun h => Rnorm P t L (x + h • coordDir ℓ s)) D ∧
|D| ≤ 3 * t ^ 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.12, Eq. (6.20), p.29 (proof Appendix C.3, pp.50–51)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.