Figure 1 — polynomial-time encoding of the completed market and its price decoder
OpenLinearChoresCLS.figure_1_encoded_constructionFor a valid rational quadratic instance of positive dimension, the completed linear chores market has strictly positive data. There are polynomial-time functions and on the mission's bit encodings with the following properties.
The word is a valid rational chores-market instance. For every encoded exact rational equilibrium of , there is an equilibrium of the completed market on its named agents and chores. The output encodes a rational vector satisfying
Here the real embedding of is exactly the mission's price decoder applied to . The representation of on the named agents and chores accommodates the finite reindexing used by the bit-string market encoding.
Formalization note. This is the computational part of Figure 1. It records polynomial-time computability on Cook's machines, positivity and validity of the constructed market, and the agreement of the encoded decoder with equation (7.3). The separate analytic claim that the decoded vector satisfies the approximate KKT conditions follows from Proposition 4.1 and the Section 7 milestones. The answer condition is required for every rational equilibrium encoding, with no length restriction.
import Definitions.Def_LinearChoresCLS_PriceFamily import Definitions.Def_LinearChoresCLS_ChoresSearch import Definitions.Def_LinearChoresCLS_EpsKKT open NetworkEquilibriumCLS.LinearNash
namespace LinearChoresCLS
theorem figure_1_encoded_construction :
∃ (f : List Bool → List Bool) (g : List (Option (Bool ⊕ Bool)) → List Bool),
PolyTime f ∧ PolyTime g ∧
∀ (n : ℕ) (_ : 0 < n) (P : Quadratic n) (ε : ℚ) (_ : 0 < ε),
let I := encQuadratic P ++ encRat ε
(completedMarket P ε).Valid ∧ choresCESearch.valid (f I) ∧
∀ y, choresCESearch.answer (f I) y →
∃ (p : Chore n (chainLength P ε) → ℝ)
(z : Agent n (chainLength P ε) → Chore n (chainLength P ε) → ℝ)
(v : Fin n → ℚ),
(completedMarket P ε).IsCE p z ∧
(fun i => (v i : ℝ)) = decoder (tParam P ε) p ∧
encVector v = g (pairCode I y) := by sorry
end LinearChoresCLS