Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Polynomial-time serialization of the completed rational market

Open
LinearChoresCLS.completed_market_word

by Weiqiang · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

Given a positive-dimensional rational quadratic instance (P,ε)(P,\varepsilon)(P,ε) with ε>0\varepsilon>0ε>0, the market construction in Figure 1 has a polynomial-time bit-string implementation. Its output is the public encoding of a rational market GGG. There are bijections from the named agents and chores of the construction to the rows and columns of GGG under which every disutility, earning requirement and supply equals the specified datum. The first n+1n+1n+1 columns are the reference chore and the coordinate chores in increasing order. This fixes the locations needed by the price decoder.

Preamble
import Definitions.Def_LinearChoresCLS_PriceFamily
import Definitions.Def_LinearChoresCLS_ChoresSearch

Formal statement
namespace LinearChoresCLS

open NetworkEquilibriumCLS.LinearNash in
theorem completed_market_word :
    ∃ f : List Bool → List Bool, PolyTime f ∧
      ∀ {n : ℕ}, 0 < n → ∀ (P : Quadratic n) (ε : ℚ), 0 < ε →
        let L := chainLength P ε
        let F := completedMarket P ε
        ∃ (a m : ℕ) (e : Agent n L ≃ Fin a) (d : Chore n L ≃ Fin m) (G : RatChoresMarket a m),
          (∀ j : Fin (n+1), (d (Sum.inl j)).val = j.val) ∧
          (∀ i j, (G.disutil (e i) (d j) : ℝ) = F.disutil i j) ∧
          (∀ i, (G.earn (e i) : ℝ) = F.earn i) ∧
          (∀ j, (G.supply (d j) : ℝ) = F.supply j) ∧
          encChores G = f (encQuadratic P ++ encRat ε) := by sorry

end LinearChoresCLS
Source
Liu, Ma, Tao, Yang, and Zheng, Competitive Equilibrium for Linear Chores is CLS-complete, arXiv:2611.06589v1. https://arxiv.org/html/2611.06589v1 Figure 1 and Section 7.1, Market Specification and Completing the Verification.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me