Theorem 6.10 — linear approximation, remainder bound
ProvedLinearChoresCLS.theorem_6_10choresclscompetitive-equilibriumfisher-marketp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , as in (5.5), and with . For every ,
For every and every coordinate segment from to in , ; moreover, for every feasible coordinate direction at , the right directional derivative exists and .
The adjustment of the basic earning requirements by produces the linear part of .
Differences from the source:
- generalization: t of the construction (rational; (7.1) gives t = 2^{−L} ≤ 1/256) → any real t ∈ (0, 1] (Section 5's range); reason: the statement involves only the basic price family and α = λt²; the proof (p.48) is written for 0 < t < 1/8, but its computation |∂ℓR_lin| = αt|cℓ|xℓ/(1 + t xℓ) ≤ t³/(2(n+1)) uses only t > 0, and (7.1)'s t is an instance
- generalization: QP dimension n ≥ 1 (A ∈ ℚ^{n×n}, [n] for positive n, p.5) → any n : ℕ; reason: at n = 0 the box is one point and every clause holds trivially; n ≥ 1 is a special case
Preamble
import Mathlib import Definitions.Def_LinearChoresCLS_Remainders import Definitions.Def_LinearChoresCLS_RightDeriv open Finset NetworkEquilibriumCLS.LinearNash
Formal statement
namespace LinearChoresCLS
/-- **Theorem 6.10 (Linear approximation)** (arXiv:2611.06589, held version sha256 85d34a9e…,
p.27). Let `α` be given by (5.5) and `c₀ := −∑_{i=1}^n c_i` (6.13). For every `x ∈ [0,1]ⁿ`,
`(α/t) ∑_{j=0}^n c_j log p_j(x) = αcᵀx + R_lin(x)` (6.16); for every `ℓ ∈ [n]` and every coordinate
segment from `x` to `x + he_ℓ` in `[0,1]ⁿ`, `|R_lin(x + he_ℓ) − R_lin(x)| ≤ t³/(2(n+1)) |h|` (6.17);
and for every feasible coordinate direction `ṽ ∈ {±e_ℓ}` at `x` the right directional derivative
exists and `|R′_lin(x; ṽ)| ≤ t³/(2(n+1))`.
**Formalization Note.** `p_j(x)` is the basic price family (5.2) with `x₀ = 0`. The parameter `t`
is any real in Section 5's range `(0, 1]` (p.13); the completed market's `t` of (7.1) is one
instance. -/
theorem theorem_6_10 {n : ℕ} (P : Quadratic n) (t : ℝ) (ht : 0 < t) (ht1 : t ≤ 1) :
(∀ x : Fin n → ℝ, InCube x →
alpha P t / t * ∑ j, cExt P j * Real.log (basicPrice t x j) =
alpha P t * ∑ i, (P.c i : ℝ) * x i + Rlin P t x) ∧
(∀ (x : Fin n → ℝ) (ℓ : Fin n) (h : ℝ), InCube x → InCube (x + h • Pi.single ℓ (1 : ℝ)) →
|Rlin P t (x + h • Pi.single ℓ (1 : ℝ)) - Rlin P t x| ≤ t ^ 3 / (2 * (n + 1)) * |h|) ∧
(∀ (x : Fin n → ℝ) (ℓ : Fin n) (s : Bool), InCube x → FeasibleCoordDir x ℓ s →
∃ D : ℝ, HasRightDerivAt0 (fun h => Rlin P t (x + h • coordDir ℓ s)) D ∧
|D| ≤ t ^ 3 / (2 * (n + 1))) := 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.10, Eqs. (6.16)–(6.17), p.27 (proof Appendix C.2, p.48)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.