Lemma 6.3 — output prices and optimal ratios of a Maximum–Minimum gadget
ProvedLinearChoresCLS.lemma_6_3choresclscompetitive-equilibriumfisher-marketp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Consider a valid chores market containing a Maximum–Minimum gadget on chores : agents with common earning requirement , output chores with common supply , and designated disutilities , , , , , . Let be an equilibrium such that
- the three gadget agents use only their designated chores, and
- the price condition holds: and , where are the agents outside the gadget that use .
Then
with , and the optimal ratios are , , .
The gadget produces a price proportional to a maximum, whose logarithm contains the absolute-value term .
Formalization Note The gadget's agents and chores are distinct; "uses" is ; the remaining entries of the market (the dashes of Definition 6.1) are arbitrary positive numbers.
Differences from the source:
- generalization: gadget parameter q > 1 (Figure 3) → any q allowed by the market's validity (q > 0); reason: the proof (p.20) does not use q > 1; q > 1 is a special case
- encoding: the gadget adds three new agents and two new chores → explicit distinctness hypotheses on the five chores and three agents; reason: Lean has no notion of "new"; distinctness is what newness means
Preamble
import Mathlib import Definitions.Def_LinearChoresCLS_Psi open Finset
Formal statement
namespace LinearChoresCLS
open Classical in
/-- **Lemma 6.3** (arXiv:2611.06589, held version sha256 85d34a9e…, p.20). Consider a market
containing a Maximum-Minimum gadget on chores `(j, j′)` (Definition 6.1, p.18–19): agents
`a^max, a^{(1)}, a^{(2)}` with the same earning requirement `B`, output chores `p^+, p^−` with the
same supply `S`, and designated disutilities `d(a^max, j) = d(a^max, j′) = q`, `d(a^max, p^+) = 1`,
`d(a^{(1)}, j) = 1/q`, `d(a^{(1)}, p^−) = 1`, `d(a^{(2)}, j′) = 1/q`, `d(a^{(2)}, p^−) = 1`. Suppose at
the equilibrium `(p, z)` (1) the three gadget agents use only their designated chores and
(2) the price condition holds: `∑_{a ∈ N^+_out} B_a < S p^+ < B` and
`∑_{a ∈ N^−_out} B_a < S p^− < B`, where `N^±_out` are the agents outside the gadget using `p^±`.
Then `p^+ = max{p_j, p_{j′}}/q`, `p^− = q min{p_j, p_{j′}}`,
`log(p^+/p^−) = |Δ_{(j,j′),0}| − 2 log q` with `Δ_{(j,j′),0} = log(p_j/p_{j′})` (6.7), and
`μ_{a^max}(p) = max{p_j, p_{j′}}/q`, `μ_{a^{(1)}}(p) = q p_j`, `μ_{a^{(2)}}(p) = q p_{j′}` (6.8).
**Formalization Note.** The market is any valid market; the dashes of Definition 6.1 are its
remaining (arbitrary positive) disutilities. `q` is any value the market's validity allows
(`q > 0`), not only `q > 1` as in Figure 3. "Uses" is `z_{aℓ} > 0`. -/
theorem lemma_6_3 {N M : Type*} [Fintype N] [Fintype M] [Nonempty M]
(F : ChoresMarket N M) (hF : F.Valid) (p : M → ℝ) (z : N → M → ℝ) (hCE : F.IsCE p z)
(j j' pplus pminus : M) (hjj' : j ≠ j') (hpj : pplus ≠ j) (hpj' : pplus ≠ j')
(hmj : pminus ≠ j) (hmj' : pminus ≠ j') (hpm : pplus ≠ pminus)
(amax a1 a2 : N) (h01 : amax ≠ a1) (h02 : amax ≠ a2) (h12 : a1 ≠ a2) (B S q : ℝ)
(hB : F.earn amax = B ∧ F.earn a1 = B ∧ F.earn a2 = B)
(hS : F.supply pplus = S ∧ F.supply pminus = S)
(hd : F.disutil amax j = q ∧ F.disutil amax j' = q ∧ F.disutil amax pplus = 1 ∧
F.disutil a1 j = 1 / q ∧ F.disutil a1 pminus = 1 ∧
F.disutil a2 j' = 1 / q ∧ F.disutil a2 pminus = 1)
(hdes : (∀ ℓ, 0 < z amax ℓ → ℓ = j ∨ ℓ = j' ∨ ℓ = pplus) ∧
(∀ ℓ, 0 < z a1 ℓ → ℓ = j ∨ ℓ = pminus) ∧ (∀ ℓ, 0 < z a2 ℓ → ℓ = j' ∨ ℓ = pminus))
(hpc : (∑ a ∈ univ.filter (fun a => a ≠ amax ∧ a ≠ a1 ∧ a ≠ a2 ∧ 0 < z a pplus), F.earn a)
< S * p pplus ∧ S * p pplus < B ∧
(∑ a ∈ univ.filter (fun a => a ≠ amax ∧ a ≠ a1 ∧ a ≠ a2 ∧ 0 < z a pminus), F.earn a)
< S * p pminus ∧ S * p pminus < B) :
p pplus = max (p j) (p j') / q ∧ p pminus = q * min (p j) (p j') ∧
Real.log (p pplus / p pminus) = |Real.log (p j / p j')| - 2 * Real.log q ∧
F.mu amax p = max (p j) (p j') / q ∧ F.mu a1 p = q * p j ∧ F.mu a2 p = q * p j' := 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), Lemma 6.3, Eqs. (6.7)–(6.8), p.20 (Definition 6.1, pp.18–19)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.