Polynomial-time serialization of the completed rational market
OpenLinearChoresCLS.completed_market_wordGiven a positive-dimensional rational quadratic instance with , the market construction in Figure 1 has a polynomial-time bit-string implementation. Its output is the public encoding of a rational market . There are bijections from the named agents and chores of the construction to the rows and columns of under which every disutility, earning requirement and supply equals the specified datum. The first 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.