Introduction
Allocating indivisible goods without monetary transfers is a basic problem in matching markets, such as assigning students to dormitory rooms. The Hylland–Zeckhauser (HZ) mechanism [12 ] addresses this problem through a market for probability shares of goods. There are N N N buyers with cardinal utilities and N N N indivisible goods, each available in one copy. Each buyer receives one unit of artificial money and chooses an affordable bundle of probability shares of total quantity one to maximize her expected utility. Equilibrium prices make these demands clear the market. The resulting doubly stochastic allocation can be implemented as a lottery over assignments in which each buyer receives exactly one good. No monetary transfers are made. For linear utilities over probability shares, the allocation is ex ante envy-free and, with minimum-expenditure tie-breaking among optimal bundles, ex ante Pareto-efficient [12 ] .
At fixed prices, a buyer’s demand in the linear model is a linear program with a budget constraint and a unit-quantity constraint. Finding prices that clear the market is the computational difficulty. An optimal bundle may mix an expensive preferred good with a cheaper less preferred good to satisfy both constraints. Vazirani and Yannakakis [17 ] gave a strongly polynomial exact algorithm for bivalued utilities, where each buyer has at most two values, which may differ across buyers, and asked whether { 0 , 1 / 2 , 1 } \{0,1/2,1\} { 0 , 1/2 , 1 } already suffices for intractability. Chen, Chen, Peng, and Yannakakis [4 ] proved PPAD-hardness of inverse polynomial approximation with four values per buyer. Yan and Liu [18 ] subsequently gave a polynomial-time additive 1 / e 1/e 1/ e approximation for utilities in [ 0 , 1 ] [0,1] [ 0 , 1 ] and a 5 × 5 5 \times5 5 × 5 market over { 0 , 1 / 2 , 1 } \{0,1/2,1\} { 0 , 1/2 , 1 } whose exact equilibria all have an irrational price. Irrationality does not, however, establish hardness of approximation; the three-value case remained open.
We study two extensions of the tractable bi-valued domain. The first keeps utilities linear and adds a third value. The second allows separable concave utilities over fractional allocations, with two marginal slopes common across goods for each buyer and a separate breakpoint for every buyer–good pair. Taking all breakpoints in { 0 , 1 } \{0,1\} { 0 , 1 } recovers bi-valued linear utilities, so both extensions contain the tractable case. We can therefore distinguish the effect of an additional utility value from that of diminishing returns.
Our results
Three common utility values. We use the additive approximation notion of [4 ] . A normalized additive ε \varepsilon ε -equilibrium consists of nonnegative prices with minimum zero and an allocation that clears every good and gives every buyer total quantity one. Each buyer i i i spends at most 1 + ε 1+\varepsilon 1 + ε and receives utility at least V i ( p ) − ε V_i(p)-\varepsilon V i ( p ) − ε , where V i ( p ) V_i(p) V i ( p ) is her maximum utility over unit bundles costing at most one at prices p p p . This notion allows expenditure on zero-utility goods and does not impose minimum-expenditure tie-breaking; see Definition 2.2 .
Theorem 1.1. For every fixed rational a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) , there is a positive rational constant ε ∗ ( a ) \varepsilon_*(a) ε ∗ ( a ) such that computing a normalized additive ε ∗ ( a ) / N \varepsilon_*(a)/N ε ∗ ( a ) / N -equilibrium of an N N N -buyer HZ market is PPAD-complete when all utilities belong to { 0 , a , 1 } \{0,a,1\} { 0 , a , 1 } .
Membership in PPAD follows from [17 Section 7] . Their approximation notion imposes all the conditions in Definition 2.2 , together with an approximate minimum-expenditure condition. Dropping that additional condition gives a solution of our problem at the same error parameter. Their upper bound applies to rational utilities in [ 0 , 1 ] [0,1] [ 0 , 1 ] and positive rational accuracy, including ε ∗ ( a ) / N \varepsilon_*(a)/N ε ∗ ( a ) / N .
The theorem answers the question of [17 ] for { 0 , 1 / 2 , 1 } \{0,1/2,1\} { 0 , 1/2 , 1 } and, more generally, for every prescribed middle value a a a . The same three values are used by all buyers; this is stronger than allowing each buyer her own three values. In contrast, the hardness of [4 ] does not assume four common values for all buyers. Furthermore, every row and column of our constructed utility matrix has only a bounded number of positive entries, with the bound depending on a a a . Since 1 / ε = N / ε ∗ ( a ) 1/\varepsilon= N/\varepsilon_*(a) 1/ ε = N / ε ∗ ( a ) is polynomial in the market size, Theorem 1.1 rules out a fully polynomial-time approximation scheme unless P P A D ⊆ P \mathrm{PPAD} \subseteq\mathrm{P} PPAD ⊆ P .
Constant approximation and PCP for PPAD. The PCP-for-PPAD conjecture of Babichenko, Papadimitriou, and Rubinstein [2 ] concerns generalized circuits in which a small constant fraction of gates may fail. We use the formulation of [6 ] : for some positive constant gate accuracy and failure fraction, finding such an assignment is PPAD-hard. The original conjecture asks for a quasilinear reduction. OpenAI has announced a proof of that stronger formulation [13 ] ; we state our constant-approximation result conditionally on PCP for PPAD.
Theorem 1.2 (Constant-error hardness under PCP for PPAD). Assuming the PCP-for-PPAD conjecture, for every fixed rational a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) there is a positive rational constant ε 0 = ε 0 ( a ) \varepsilon_0 = \varepsilon_0(a) ε 0 = ε 0 ( a ) such that computing a normalized additive ε 0 \varepsilon_0 ε 0 -equilibrium of an HZ market with utilities in { 0 , a , 1 } \{0,a,1\} { 0 , a , 1 } is PPAD-hard.
Two common marginal slopes. For the concave extension, buyer i i i has separable utility U i ( x i ) = ∑ j f i j ( x i j ) U_i(x_i) = \sum_j f_{ij}(x_{ij}) U i ( x i ) = ∑ j f ij ( x ij ) , where
f i j ( t ) = c i ( 2 ) t + ( c i ( 1 ) − c i ( 2 ) ) min { t , τ i j } , 0 ≤ t ≤ 1. (1) f_{ij}(t) = c_i^{(2)}t + \left(c_i^{(1)} - c_i^{(2)}\right)\min\{t,\tau_{ij}\}, \qquad0 \le t \le1. \tag*{(1)} f ij ( t ) = c i ( 2 ) t + ( c i ( 1 ) − c i ( 2 ) ) min { t , τ ij } , 0 ≤ t ≤ 1. (1)
The slopes c i ( 1 ) ≥ c i ( 2 ) ≥ 0 c_i^{(1)} \ge c_i^{(2)} \ge0 c i ( 1 ) ≥ c i ( 2 ) ≥ 0 are common across goods for buyer i i i , while τ i j ∈ [ 0 , 1 ] \tau_{ij} \in[0,1] τ ij ∈ [ 0 , 1 ] is the breakpoint for good j j j . Budgets, supplies, and required bundle quantities are still one.
Theorem 1.3 (Two marginal slopes). For rational input in (1) , an exact normalized HZ equilibrium can be computed in strongly polynomial time. Each buyer receives a minimum-expenditure bundle among her utility-maximizing affordable bundles.
With three common slopes, zero-length segments can represent each of the linear utilities 0 0 0 , a t at a t , and t t t . Thus the linear hardness theorem immediately gives the corresponding concave hardness result.
Corollary 1.4 (Three common marginal slopes). For every fixed rational a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) , computing a normalized additive ε ∗ ( a ) / N \varepsilon_*(a)/N ε ∗ ( a ) / N -equilibrium is PPAD-hard for separable concave utilities with the same ordered marginal slopes 1 1 1 , a a a , 0 0 0 for every buyer–good pair, allowing segments of zero length.
Table 1 summarizes these results.
Table 1. Complexity under restrictions on linear utility values and common marginal slopes, for fixed rational a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) . In the concave model, slopes are common across goods for each buyer; the three-slope hardness uses the same slopes for all buyers. Zero-length segments are permitted.
Technical overview
We reduce from the bounded-degree threshold game [15 , 5 ] , with a fixed small tolerance κ > 0 \kappa> 0 κ > 0 . Each vertex has a value z v ∈ [ 0 , 1 ] z_v \in[0,1] z v ∈ [ 0 , 1 ] , which must be at most κ \kappa κ when the incoming sum exceeds 1 / 2 + κ 1/2 + \kappa 1/2 + κ , and at least 1 − κ 1 - \kappa 1 − κ when that sum is below 1 / 2 − κ 1/2 - \kappa 1/2 − κ . Inside this tolerance interval, any value is allowed. Both indegree and outdegree are at most two, and every vertex has at least one outgoing edge. For fixed rational a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) , we choose a small constant τ \tau τ and a large admissible integer K K K before receiving the graph. All vertex and wire gadgets then have constant size, with vertex sizes depending only on the bounded degree pair.
Chen, Chen, Peng, and Yannakakis [4 Section 3, full version] also reduce from threshold games, using at most four utility values per buyer, which may differ across buyers. Their edge gadgets use this freedom to cancel unwanted price dependencies. With the same prescribed set { 0 , a , 1 } \{0, a, 1\} { 0 , a , 1 } for every buyer, we cannot tune these comparisons separately. Our construction uses two successive comparisons to obtain a price ratio a 2 a^2 a 2 . Its separation from the utility ratio a a a lets wire buyers transmit an approximately affine signal. Their spending also changes at the source; degree-dependent supplies cancel that second change. We first explain the reduction at an exact equilibrium.
Encoding values in prices. Each vertex v v v has three target groups of goods L v L_v L v , M v M_v M v , H v H_v H v , with prices q v q_v q v , m v m_v m v , p v p_v p v . Goods within a group have identical utility vectors, allowing price equalization (Lemma 2.3 ). Lower-link buyers compare utilities a a a and one on L v L_v L v , M v M_v M v ; upper buyers make the same comparison on M v M_v M v , H v H_v H v . Two reference groups of goods, supported by their own anchor buyers, bound the target prices. Floor buyers can buy the low and middle targets or their reference; upper buyers can buy the middle and high targets or a second reference.
Suitable group sizes force
q v = a m v = a 2 p v , q v < 1 < m v < p v . q_v = a m_v = a^2 p_v,\qquad q_v < 1 < m_v < p_v. q v = a m v = a 2 p v , q v < 1 < m v < p v .
Thus the two comparisons produce the ratio a 2 a^2 a 2 , while a unit of the low target is affordable and a unit of either other target is not. The reference groups confine every high price to the same interval [ L , U + η ] [L, U + \eta] [ L , U + η ] , of width O a ( 1 / K ) O_a(1/K) O a ( 1/ K ) , just below a − 2 a^{-2} a − 2 . Writing w = U − L w = U - L w = U − L and η = τ w \eta= \tau w η = τ w , we decode z v = clip ( t v ) z_v = \operatorname{clip}(t_v) z v = clip ( t v ) , where t v = ( p v − L ) / w t_v = (p_v - L)/w t v = ( p v − L ) / w and clip truncates to [ 0 , 1 ] [0,1] [ 0 , 1 ] . Then 0 ≤ t v ≤ 1 + τ 0 \le t_v \le1 + \tau 0 ≤ t v ≤ 1 + τ and ∣ t v − z v ∣ ≤ τ |t_v - z_v| \le\tau ∣ t v − z v ∣ ≤ τ . Figure 1 shows the gadget; § 3 and § 4 give the group sizes and prove the price relations.
Figure 1. The vertex gadget at v v v . Solid blue ellipses denote groups of goods; dashed orange ellipses denote buyer populations. Each edge label gives every buyer’s utility for each good in the adjacent group. The balancing group Z \mathcal{Z} Z is shared by the whole market and has no positive-utility connections.
Directed signals and cancellation. For each edge u → v u \to v u → v , introduce K K K wire buyers valuing L u L_u L u at a a a and H v H_v H v at one. Since both high prices lie in the same narrow interval, q u / p v = a 2 + O a ( 1 / K ) < a q_u/p_v = a^2 + O_a(1/K) < a q u / p v = a 2 + O a ( 1/ K ) < a . The low good offers better utility per dollar, whereas the high good offers better utility per unit. Each wire buyer therefore mixes the two, exhausting both budget and quantity. With our calibration of the price interval, their total spending on H v H_v H v is
I u v = K p v ( 1 − a 2 p u ) p v − a 2 p u = 3 − 2 t u + O a ( 1 / K ) . I_{uv} = \frac{Kp_v(1-a^2p_u)}{p_v-a^2p_u} = 3-2t_u+O_a(1/K). I uv = p v − a 2 p u K p v ( 1 − a 2 p u ) = 3 − 2 t u + O a ( 1/ K ) .
The error is proportional to p u − p v p_u-p_v p u − p v , with a factor bounded in terms of a a a alone, so the bound holds for every edge; see Lemma 2.5 and (14) . Spending on H v H_v H v therefore records the value encoded at u u u .
The same buyers spend their remaining budget K − I u v = K − 3 + 2 t u + O a ( 1 / K ) K-I_{uv}=K-3+2t_u+O_a(1/K) K − I uv = K − 3 + 2 t u + O a ( 1/ K ) on L u L_u L u . Thus outgoing wires contribute a term 2 o v t v 2o_vt_v 2 o v t v to revenue at v v v , where o v o_v o v is its outdegree. We choose the target supplies so that the revenue required to clear them contains exactly the same term. Subtracting wire spending cancels this extra dependence on t v t_v t v . The numbers of link buyers adjust the constant terms according to the indegree and outdegree, placing the threshold at 1 / 2 1/2 1/2 . The remaining market-clearing identity is
Φ v = 2 ∑ u → v t u − 1 + O a ( 1 / K ) . \Phi_v = 2\sum_{u\to v} t_u - 1 + O_a(1/K). Φ v = 2 u → v ∑ t u − 1 + O a ( 1/ K ) .
where Φ v \Phi_v Φ v is floor spending on the targets minus upper spending on the upper reference goods. If Φ v > 0 \Phi_v>0 Φ v > 0 , floor buyers must spend on targets. This is optimal only near the low endpoint, forcing z v ≤ τ z_v\le\tau z v ≤ τ . If Φ v < 0 \Phi_v<0 Φ v < 0 , upper buyers must spend on their reference, forcing the high price to be at least U U U and hence z v = 1 z_v=1 z v = 1 . Small τ \tau τ and large K K K therefore turn a large incoming sum into a small output, and a small incoming sum into a large output, whenever the sum lies outside the tolerance interval. Proposition 4.8 formalizes this decoding argument.
Robustness and inverse-linear accuracy. Approximate buyers may spend on goods they value at zero, supplying revenue absent from the exact argument. Even a small quantity can matter if its price is high, so we must control expenditure. We do this before assuming approximate price relations. Our demand estimates bound purchases from inferior options while accounting for both the budget and the unit-bundle constraint. The construction also keeps each buyer’s optimal utility a fixed amount below one. Together with revenue bounds, these estimates give total unapproved expenditure W = O a ( N ε ) W=O_a(N\varepsilon) W = O a ( N ε ) for sufficiently small K ε K\varepsilon K ε .
When W W W and K 2 ε K^2\varepsilon K 2 ε are small, approximate price relations follow, and the additional error in the revenue identity is O a ( K 2 ε + W ) O_a(K^2\varepsilon+W) O a ( K 2 ε + W ) . Away from the required endpoint, nearly optimal floor or upper buyers cannot supply the spending needed to explain the residual. This preserves the threshold response. At ε = ε ∗ ( a ) / N \varepsilon=\varepsilon_*(a)/N ε = ε ∗ ( a ) / N , both error terms are small for sufficiently small ε ∗ ( a ) \varepsilon_*(a) ε ∗ ( a ) , since N = Ω a ( K 2 ) N=\Omega_a(K^2) N = Ω a ( K 2 ) . Appendix § 9 gives the quantitative estimates.
Constant error and local decoding. At constant accuracy, total unapproved expenditure can grow with the graph. We instead bound the amount received by each vertex gadget. A vertex decodes correctly whenever this expenditure is small throughout its radius-two neighborhood: price comparisons use incoming neighbors, and wire accounting uses both endpoints. Bounded degree limits the number of vertices affected by any one gadget receiving too much expenditure. For errors below a suitable constant multiple of 1 / K 2 1/K^2 1/ K 2 , at most O a ( N ε ) O_a(N\varepsilon) O a ( N ε ) constraints fail. For an n n n -vertex source graph, N = Θ a ( K 2 n ) N=\Theta_a(K^2n) N = Θ a ( K 2 n ) , so choosing a sufficiently small constant accuracy makes the failure fraction arbitrarily small. Under PCP for PPAD, the required weak threshold problem is hard: start from weak Pure-Circuit instances in which every node is used as an input exactly once [6 ] , then apply the threshold gadgets of [5 ] . This preserves bounded degree and transfers failures with only a constant loss.
The two-slope algorithm. On unit bundles, the lower-slope contribution is constant. Subtracting it and scaling reduces each nonindifferent buyer’s utility to U i ( x i ) = ∑ j min { x i j , τ i j } U_i(x_i)=\sum_j \min\{x_{ij},\tau_{ij}\} U i ( x i ) = ∑ j min { x ij , τ ij } , preserving demand and minimum-expenditure tie-breaking; indifferent buyers have zero thresholds. All quantities below a threshold now have the same marginal value. Fractional thresholds introduce a difficulty absent from the bi-valued case: a buyer can exhaust a cheap good’s useful quantity while retaining both money and room in her bundle.
We extend the increasing-price method of [17 ] , tracking each buyer’s remaining budget and quantity separately. An initial quantity flow identifies goods that can be assigned price zero. On these goods, each buyer receives either a full bundle of useful quantities or her entire threshold quantity of every identified good, so any unused supply can later fill bundle deficits without changing utility or expenditure. At each subsequent stage, we use reciprocal price as a parameter and apply the Gallo–Grigoriadis–Tarjan parametric maximum-flow algorithm [8 ] to find the largest feasible common price for the remaining goods. A residual-network certificate in the expenditure network identifies which goods can be committed at that price and establishes the key invariant: every continuing buyer has filled every threshold at earlier prices . This ensures that buyers receive cheaper useful quantities first. Buyers stop when their budget or unit-quantity constraint binds, or when all their useful quantities have been allocated. Unused free goods complete their bundles without changing utility or expenditure. These properties establish demand optimality and minimum expenditure. Each stage commits at least one good, giving at most N N N stages; together with polynomial bounds on intermediate encoding lengths, the parametric-flow implementation yields a strongly polynomial algorithm. § 6 gives the implementation and proof. With three common slopes, linear utilities 0 0 0 , a t at a t , and t t t are already representable by allowing zero-length segments, so the hardness result follows directly.
Related work
Exact HZ equilibria need not be rational. Vazirani and Yannakakis [17 ] established this fact and placed their computation in FIXP. Alaei, Jalaly Khalilabadi, and Tardos [1 ] gave exact polynomial-time algorithms, using algebraic representations, when the number of buyer preference types or good types is fixed. Garg, Tao, and Végh [9 ] studied constrained piecewise linear concave utilities, including matching markets, and obtained approximation schemes when the number of buyers or goods is fixed. Their existence theorem also provides normalized equilibria with minimum-expenditure tie-breaking.
For approximation hardness, Braverman, Liu, Xue, and Zhou [3 ] proved a constant-error lower bound under PCP for PPAD and an unconditional result when buyers cannot spend on zero-utility goods. Our results permit such expenditure and restrict every utility to { 0 , a , 1 } \{0,a,1\} { 0 , a , 1 } . Deligkas, Fearnley, Hollender, and Melissourgos [6 ] proved a related PCP equivalence for Fisher markets with approximately optimal bundles. We use their equivalence between weak circuit problems to obtain the input-once weak Pure-Circuit source for our reduction [6 Theorem 2.2] .
Other work considers allocation rules that obtain fairness and efficiency through Nash bargaining. Hosseini and Vazirani [HV22] formulated convex programs for one-sided and two-sided matching markets with linear and concave utilities. Tröbst and Vazirani [TV25] proved that finding an exactly envy-free and Pareto-optimal lottery is PPAD-complete, and that the one-sided Nash-bargaining solution is envy-free within a factor of two. Combined with the algorithms of Panageas, Tröbst, and Vazirani [14 ] , this gives polynomial-time computation of a ( 2 + ε ) (2+\varepsilon) ( 2 + ε ) -approximately envy-free and exactly Pareto-optimal lottery. These guarantees approximate envy; our equilibrium notion instead bounds budget violation and utility loss at the reported prices.
Extensions of HZ also accommodate priorities and allocation constraints. He, Miralles, Pycia, and Yan [10 ] use priority-dependent prices and establish asymptotic incentive compatibility. Echenique, Miralles, and Zhang [7 ] allow allocation constraints arising in settings such as school choice and course scheduling. The concave model studied here keeps the unit budgets, supplies, and bundle requirements of HZ. Its buyer–good breakpoints become capacities in our extension of the increasing-price method of [17 ] .
Organization and notation. § 2 gives the preliminaries. § 3 and § 4 give the market construction and prove inverse-linear approximation hardness. § 5 proves constant-error hardness under PCP for PPAD. § 6 gives the two-slope algorithm and the three-slope hardness corollary. Parameter calculations and quantitative robustness estimates appear in Appendices § 8 and § 9 , respectively. Appendix § 10 contains the rational-witness proof.
Throughout, N N N is the number of buyers and unit-supply goods in a market, and n = ∣ V ∣ n = \lvert V\rvert n = ∣ V ∣ is the number of vertices in a threshold graph. We fix a rational middle utility a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) and the threshold tolerance κ = 1 / 200 \kappa= 1/200 κ = 1/200 . We write clip ( t ) = min { 1 , max { 0 , t } } \operatorname{clip}(t) = \min\{1,\max\{0,t\}\} clip ( t ) = min { 1 , max { 0 , t }} and ⌈ t ⌉ \lceil t\rceil ⌈ t ⌉ for the ceiling of t t t . Constants in O a ( ⋅ ) O_a(\cdot) O a ( ⋅ ) and Θ a ( ⋅ ) \Theta_a(\cdot) Θ a ( ⋅ ) depend only on a a a . Every construction parameter is fixed before the input graph is given.
Preliminaries
The source problem: threshold games
The threshold game of Papadimitriou and Peng [15 ] is specified by a directed graph G = ( V , E ) G = (V,E) G = ( V , E ) . Write u → v u \to v u → v for ( u , v ) ∈ E (u,v) \in E ( u , v ) ∈ E , and let h v h_v h v and o v o_v o v denote the indegree and outdegree of v v v .
Definition 2.1 (Threshold solution). For 0 < κ < 1 / 2 0 < \kappa< 1/2 0 < κ < 1/2 , a κ \kappa κ -threshold solution of G G G is a vector z ∈ [ 0 , 1 ] V z \in[0,1]^V z ∈ [ 0 , 1 ] V satisfying, at every vertex v v v ,
∑ u : u → v z u > 1 2 + κ ⟹ z v ≤ κ , \sum_{u:u\to v} z_u > \frac{1}{2}+\kappa\quad\Longrightarrow\quad z_v \le\kappa, u : u → v ∑ z u > 2 1 + κ ⟹ z v ≤ κ , ∑ u : u → v z u < 1 2 − κ ⟹ z v ≥ 1 − κ . \sum_{u:u\to v} z_u < \frac{1}{2}-\kappa\quad\Longrightarrow\quad z_v \ge1-\kappa. u : u → v ∑ z u < 2 1 − κ ⟹ z v ≥ 1 − κ . If the incoming sum belongs to [ 1 / 2 − κ , 1 / 2 + κ ] [1/2-\kappa,1/2+\kappa] [ 1/2 − κ , 1/2 + κ ] , any value z v ∈ [ 0 , 1 ] z_v \in[0,1] z v ∈ [ 0 , 1 ] is allowed.
Such a solution always exists. Finding one is PPAD-complete for every fixed 0 < κ < 1 / 6 0 < \kappa< 1/6 0 < κ < 1/6 , even when both degrees are at most two [5 Theorem 4.23] . We fix κ = 1 / 200 \kappa= 1/200 κ = 1/200 .
We also require positive outdegree. This restriction preserves hardness: for each sink v v v , introduce fresh vertices s , t s,t s , t and edges v → s v \to s v → s , s → t s \to t s → t , and t → s t \to s t → s . All degrees remain at most two. Since no original incoming neighborhood changes, every solution of the augmented graph restricts to a solution of the original graph. Conversely, every original solution extends by setting z s = 0 z_s = 0 z s = 0 and z t = 1 z_t = 1 z t = 1 . Hence we may assume throughout that
h v ∈ { 0 , 1 , 2 } , o v ∈ { 1 , 2 } . (2) h_v \in\{0,1,2\}, \qquad o_v \in\{1,2\}. \tag*{(2)} h v ∈ { 0 , 1 , 2 } , o v ∈ { 1 , 2 } . (2)
HZ equilibrium and additive approximation
An HZ market has N ≥ 1 N \ge1 N ≥ 1 buyers and N N N divisible goods, with unit budgets and unit supplies. Every buyer must receive a bundle of total quantity one. Buyer i i i ’s utility for a bundle x i = ( x i j ) j = 1 N x_i = (x_{ij})_{j=1}^{N} x i = ( x ij ) j = 1 N is
U i ( x i ) = ∑ j = 1 N u i j x i j U_i(x_i) = \sum_{j=1}^{N} u_{ij}x_{ij} U i ( x i ) = j = 1 ∑ N u ij x ij
where the nonnegative utilities u i j u_{ij} u ij are rational numbers given in binary. An allocation x ≥ 0 x \ge0 x ≥ 0 is feasible if
∑ j x i j = 1 for every buyer i , ∑ i x i j = 1 for every good j . \sum_j x_{ij} = 1 \quad\text{for every buyer } i, \qquad\sum_i x_{ij} = 1 \quad\text{for every good } j. j ∑ x ij = 1 for every buyer i , i ∑ x ij = 1 for every good j .
A nonnegative price vector p p p is normalized if min j p j = 0 \min_j p_j = 0 min j p j = 0 . Write p ⋅ x i = ∑ j p j x i j p \cdot x_i = \sum_j p_jx_{ij} p ⋅ x i = ∑ j p j x ij for expenditure. At normalized prices, the budget-one optimal utility is the value of
V i ( p ) = max y ∑ j u i j y j subject to ∑ j y j = 1 , ∑ j p j y j ≤ 1 , y j ≥ 0 for every good j . \begin{aligned}
V_i(p) &= \max_y \sum_j u_{ij}y_j \\
\text{subject to}\quad&\sum_j y_j = 1,\\
&\sum_j p_jy_j \le1,\\
&y_j \ge0 \qquad\text{for every good } j.
\end{aligned} V i ( p ) subject to = y max j ∑ u ij y j j ∑ y j = 1 , j ∑ p j y j ≤ 1 , y j ≥ 0 for every good j .
(OptBundle)
A normalized exact equilibrium is a pair ( p , x ) (p, x) ( p , x ) with normalized prices and feasible allocation such that p ⋅ x i ≤ 1 p \cdot x_i \le1 p ⋅ x i ≤ 1 and U i ( x i ) = V i ( p ) U_i(x_i) = V_i(p) U i ( x i ) = V i ( p ) for every buyer i i i .
For approximation, assume u i j ∈ [ 0 , 1 ] u_{ij} \in[0,1] u ij ∈ [ 0 , 1 ] and use the following notion from [4 Definition 2.3, full version] .
Definition 2.2 (Approximate equilibrium). For ε ≥ 0 \varepsilon\ge0 ε ≥ 0 , a normalized additive ε \varepsilon ε -equilibrium is a pair p , x ≥ 0 p, x \ge0 p , x ≥ 0 with min j p j = 0 \min_j p_j = 0 min j p j = 0 and feasible x x x such that, for every buyer i i i ,
p ⋅ x i ≤ 1 + ε , U i ( x i ) ≥ V i ( p ) − ε . p \cdot x_i \le1 + \varepsilon, \qquad U_i(x_i) \ge V_i(p) - \varepsilon. p ⋅ x i ≤ 1 + ε , U i ( x i ) ≥ V i ( p ) − ε .
The case ε = 0 \varepsilon= 0 ε = 0 is an exact equilibrium.
The benchmark V i ( p ) V_i(p) V i ( p ) uses budget one, including for approximate equilibria. An exact equilibrium has minimum-expenditure tie-breaking if every buyer receives a cheapest utility-maximizing affordable unit bundle. A normalized equilibrium with this property exists for our linear markets [9 Theorem 5.1, conference version] . The hardness results use only Definition 2.2; the two-slope algorithm also satisfies minimum-expenditure tie-breaking.
Groups of goods and optimal demand
We use groups of distinct unit-supply goods with identical utility vectors: for any two goods j , k j, k j , k in a group, u i j = u i k u_{ij} = u_{ik} u ij = u ik for every buyer i i i . Assigning utility c c c to a group means assigning utility c c c to each good in it. All groups in the construction are disjoint. A buyer approves a good if her utility for it is positive. Her quantity and expenditure on a group are the sums over its goods.
Lemma 2.3 (Equalizing prices within a group). Replacing all prices in a group by their minimum, while keeping the allocation fixed, preserves a normalized additive ε \varepsilon ε -equilibrium with the same error and the same group minima.
Proof. Allocated bundles become weakly cheaper. A bundle affordable at the new prices can be purchased at the old prices by moving its quantity from the group to an originally cheapest good in that group. The utility and cost are unchanged, and individual demand has no supply constraints. Conversely, every bundle affordable at the old prices remains affordable. Each buyer’s optimal value is therefore unchanged, as are allocation feasibility and price normalization.
The lemma allows us to use one price per group. To describe individual demand, we also use free filler : an auxiliary good of price and utility zero that supplies any unused bundle quantity. It has no supply constraint in the individual problem.
Lemma 2.4 (Demand dual and filler). Let prices be nonnegative with at least one zero-price good, and let a buyer’s utilities lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , with max j u i j = 1 \max_j u_{ij}=1 max j u ij = 1 . Replacing her unapproved goods by free filler preserves her optimal utility. The dual of (OptBundle) is
V i ( p ) = min β i , μ i β i + μ i subject to β i p j + μ i ≥ u i j for every j , β i ≥ 0 , μ i ∈ R . (Dual) \begin{aligned}
V_i(p) &= \min_{\beta_i,\mu_i}\ \beta_i+\mu_i\\
\text{subject to}\quad&\beta_i p_j+\mu_i\ge u_{ij} \qquad\text{for every }j,\\
&\beta_i\ge0,\qquad\mu_i\in\mathbb{R}.
\end{aligned}
\qquad\text{(Dual)} V i ( p ) subject to = β i , μ i min β i + μ i β i p j + μ i ≥ u ij for every j , β i ≥ 0 , μ i ∈ R . (Dual) Every optimal dual satisfies 0 ≤ β i , μ i ≤ 1 0\le\beta_i,\mu_i\le1 0 ≤ β i , μ i ≤ 1 . Every optimal bundle has zero expenditure on unapproved goods. If every good valued at one costs more than one, every optimal bundle exhausts the budget.
Proof. Replacing unapproved quantities by filler preserves utility and weakly reduces cost. Conversely, replacing filler by an actual zero-price good weakly increases utility at the same cost. Hence the two problems have the same optimal value.
Linear-programming duality gives (Dual), with budget multiplier β i \beta_i β i and quantity multiplier μ i \mu_i μ i . The latter is unrestricted, but the constraint for a zero-price good implies μ i ≥ 0 \mu_i\ge0 μ i ≥ 0 . Strong duality gives β i + μ i = V i ( p ) ≤ 1 \beta_i+\mu_i=V_i(p)\le1 β i + μ i = V i ( p ) ≤ 1 , so both multipliers belong to [ 0 , 1 ] [0,1] [ 0 , 1 ] . They cannot both be zero because some utility is one. Consequently, an unapproved good of positive price has strict dual slack β i p j + μ i > 0 \beta_i p_j+\mu_i>0 β i p j + μ i > 0 and cannot occur in an optimal bundle.
If every good valued at one costs more than one, then V i ( p ) < 1 V_i(p)<1 V i ( p ) < 1 . A feasible dual with β i = 0 \beta_i=0 β i = 0 would require μ i ≥ 1 \mu_i\ge1 μ i ≥ 1 and could not be optimal. Thus β i > 0 \beta_i>0 β i > 0 at every optimum, and complementary slackness forces expenditure one.
If all approved goods cost more than one, spending the budget on goods of maximum utility per dollar uses less than one unit; filler completes an optimal bundle. A good priced below one can instead make both constraints bind. We will repeatedly use the following two-group calculation.
Lemma 2.5 (Demand for two groups). Suppose a buyer values two groups at a a a and one and all other goods at zero. Let q ≥ 0 q\ge0 q ≥ 0 and p > 1 p>1 p > 1 be their respective prices. With x , y x,y x , y denoting her quantities from these groups, the demand problem is
max { a x + y : x , y ≥ 0 , x + y ≤ 1 , q x + p y ≤ 1 } . \max\{ax+y:x,y\ge0,\ x+y\le1,\ qx+py\le1\}. max { a x + y : x , y ≥ 0 , x + y ≤ 1 , q x + p y ≤ 1 } . The optimal pairs are as follows:
If q > a p q>ap q > a p , the unique pair is ( x , y ) = ( 0 , 1 / p ) (x,y)=(0,1/p) ( x , y ) = ( 0 , 1/ p ) .
If 1 ≤ q < a p 1\le q<ap 1 ≤ q < a p , the unique pair is ( x , y ) = ( 1 / q , 0 ) (x,y)=(1/q,0) ( x , y ) = ( 1/ q , 0 ) .
If q < 1 q<1 q < 1 and q < a p q<ap q < a p , both constraints bind and the unique pair is*
x = p − 1 p − q , y = 1 − q p − q . (3) x=\frac{p-1}{p-q},\qquad y=\frac{1-q}{p-q}. \tag*{(3)} x = p − q p − 1 , y = p − q 1 − q . (3)
If q = a p q = ap q = a p , every nonnegative pair with q x + p y = 1 qx + py = 1 q x + p y = 1 and x + y ≤ 1 x + y \le1 x + y ≤ 1 is optimal, and these are all the optimal pairs.
In each case, filler supplies quantity 1 − x − y 1 - x - y 1 − x − y .
Proof. If q > a p q > ap q > a p , the dual ( β , μ ) = ( 1 / p , 0 ) (\beta, \mu) = (1/p, 0) ( β , μ ) = ( 1/ p , 0 ) bounds utility by 1 / p 1/p 1/ p , attained at ( 0 , 1 / p ) (0, 1/p) ( 0 , 1/ p ) . The first group has strict dual slack, so every optimum has x = 0 x = 0 x = 0 . If 1 ≤ q < a p 1 \le q < ap 1 ≤ q < a p , the dual ( a / q , 0 ) (a/q, 0) ( a / q , 0 ) similarly forces y = 0 y = 0 y = 0 and gives x = 1 / q x = 1/q x = 1/ q .
If q < 1 q < 1 q < 1 and q < a p q < ap q < a p , use
β = 1 − a p − q > 0 , μ = a p − q p − q > 0. \beta= \frac{1-a}{p-q} > 0,\qquad\mu= \frac{ap-q}{p-q} > 0. β = p − q 1 − a > 0 , μ = p − q a p − q > 0.
Both group constraints are tight in the dual. Complementary slackness requires x + y = 1 x + y = 1 x + y = 1 and q x + p y = 1 qx + py = 1 q x + p y = 1 . Their solution is (3) ; it is nonnegative and attains the dual value. Finally, when q = a p q = ap q = a p , utility is ( q x + p y ) / p (qx + py)/p ( q x + p y ) / p and is maximized precisely by feasible pairs that spend one.
The market construction
Fix a rational a ∈ ( 0 , 1 ) a \in(0, 1) a ∈ ( 0 , 1 ) and a nonempty directed graph G = ( V , E ) G = (V, E) G = ( V , E ) satisfying (2) . We construct an HZ market whose prices encode a solution of the threshold game on G G G . Each vertex contributes five groups of goods, and each edge contributes buyers who approve goods at its two endpoints. The preferences use only { 0 , a , 1 } \{0, a, 1\} { 0 , a , 1 } . We specify these preferences first and choose the integer supplies and population sizes in § 4 .
All goods have unit supply. All buyers have budget one and require one unit of goods in total. Groups and populations are disjoint, and every utility not specified below is zero.
Goods and preferences
For each vertex v v v , introduce target groups L v , M v , H v L_v, M_v, H_v L v , M v , H v , with supplies S L , S M , S H S_L, S_M, S_H S L , S M , S H , and reference groups R F v , R U v \mathcal{R}_{Fv}, \mathcal{R}_{Uv} R F v , R U v with supplies S F v R , S U v R S^R_{Fv}, S^R_{Uv} S F v R , S U v R . The low and middle supplies depend on o v o_v o v ; we omit that argument from the notation. The high supply is the same at every vertex.
The vertex has two populations linking consecutive targets. The b v b_v b v lower-link buyers B v L M B_v^{LM} B v L M assign utility a a a to L v L_v L v and utility one to M v M_v M v . The c v c_v c v upper buyers B v M H B_v^{MH} B v M H assign utility a a a to M v M_v M v and R U v \mathcal{R}_{Uv} R U v , and utility one to H v H_v H v . We will choose b v b_v b v as a function of h v h_v h v and c v c_v c v as a function of o v o_v o v .
There are also F v F_v F v floor buyers F v F_v F v , who assign utility a a a to L v L_v L v and utility one to M v M_v M v and R F v \mathcal{R}_{Fv} R F v . Each reference group has its own anchors: the A F v R A^R_{Fv} A F v R buyers A F v A_{Fv} A F v approve only R F v \mathcal{R}_{Fv} R F v , and the A U v R A^R_{Uv} A U v R buyers A U v A_{Uv} A U v approve only R U v \mathcal{R}_{Uv} R U v , in each case at utility one. Thus the floor reference is approved only by floors and its anchors, and the upper reference only by upper buyers and its anchors. Figure 1 records all vertex preferences.
The global group Z \mathcal{Z} Z consists of goods valued at zero by every buyer. Its size will make the total supply equal to the number of buyers.
For each directed edge u → v u \to v u → v , introduce a population E u v \mathcal{E}_{uv} E uv of K K K wire buyers, each assigning utility a a a to L u L_u L u and utility one to H v H_v H v . Consequently, L v L_v L v has o v K o_vK o v K outgoing wire approvers and H v H_v H v has h v K h_vK h v K incoming wire approvers. A self-loop contributes one population, approving L v L_v L v and H v H_v H v ; it is counted only once. See Figure 2 .
Figure 2. The wire gadget for u → v u \to v u → v : K K K buyers connect L u L_u L u to H v H_v H v . For a self-loop u = v u = v u = v , this is one population connecting L v L_v L v and H v H_v H v .
Let N N N be the total number of buyers and G l i s t e d G_{\mathrm{listed}} G listed the number of goods in the five groups per vertex. Add N − G l i s t e d N - G_{\mathrm{listed}} N − G listed goods to Z \mathcal{Z} Z . Lemma A.3 proves that this number is positive for our parameter choice. The resulting market has N N N buyers and N N N goods. Table 2 lists all groups and populations.
Table 2. The groups of goods and buyer populations. Each listed utility applies to every good in the indicated group. All unlisted utilities are zero.
Prices and the decoded variables
For a price vector, write
q v = min j ∈ L v p j , m v = min j ∈ M v p j , p v = min j ∈ H v p j , q_v = \min_{j\in L_v} p_j,\qquad m_v = \min_{j\in M_v} p_j,\qquad p_v = \min_{j\in H_v} p_j, q v = j ∈ L v min p j , m v = j ∈ M v min p j , p v = j ∈ H v min p j ,
r F v = min j ∈ R F v p j , r U v = min j ∈ R U v p j . r_{Fv} = \min_{j\in\mathcal{R}_{Fv}} p_j,\qquad r_{Uv} = \min_{j\in\mathcal{R}_{Uv}} p_j. r F v = j ∈ R F v min p j , r U v = j ∈ R U v min p j .
Lemma 2.3 allows us to replace every price in a group by its minimum, preserving the equilibrium error. We use these equalized prices in the analysis; the decoder depends only on the group minima and is therefore unchanged.
The high price p v p_v p v represents the variable at v v v . For endpoints L < U L<U L < U , to be chosen in (8) , put w = U − L w=U-L w = U − L and define
t v = p v − L w , z v = clip ( t v ) . (4) t_v = \frac{p_v-L}{w},\qquad z_v=\operatorname{clip}(t_v). \tag*{(4)} t v = w p v − L , z v = clip ( t v ) . (4)
A positive rational parameter τ ≤ κ / 100 \tau\leq\kappa/100 τ ≤ κ /100 determines η = τ w \eta=\tau w η = τ w . We choose the two reference groups so that every exact equilibrium satisfies
a L ≤ r F v ≤ a ( L + η ) , a U ≤ r U v ≤ a ( U + η ) . aL\leq r_{Fv}\leq a(L+\eta),\qquad aU\leq r_{Uv}\leq a(U+\eta). a L ≤ r F v ≤ a ( L + η ) , a U ≤ r U v ≤ a ( U + η ) .
These bounds will imply L ≤ p v ≤ U + η L\leq p_v\leq U+\eta L ≤ p v ≤ U + η .
Denote the completed market by M ( G ; a , τ , K ) \mathcal{M}(G;a,\tau,K) M ( G ; a , τ , K ) , with all supplies and counts given in Subsection 4.4. For fixed a , τ , K a,\tau,K a , τ , K , each count depends only on the local degrees and is bounded independently of the graph. The hardness results use one sufficiently small rational value of τ \tau τ , denoted τ a \tau_a τ a , that depends only on a a a ; its existence is established in Theorem 5.7 .
Hardness of inverse-linear approximation
Theorem 4.1 (Soundness of the market construction). For every fixed rational a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) , there are positive rational constants τ a \tau_a τ a , ε ∗ ( a ) \varepsilon_*(a) ε ∗ ( a ) and an integer K a K_a K a , depending only on a a a , with the following property. For every K ≥ K a K \ge K_a K ≥ K a admissible as in Subsection 4.4 and every nonempty graph G G G satisfying (2) , every normalized additive ε ∗ ( a ) / N \varepsilon_*(a)/N ε ∗ ( a ) / N -equilibrium of M ( G ; a , τ a , K ) \mathcal{M}(G;a,\tau_a,K) M ( G ; a , τ a , K ) decodes to values satisfying, at every vertex,
∑ u → v z u > 1 2 + κ ⟹ z v ≤ κ , \sum_{u\to v} z_u > \frac{1}{2}+\kappa\quad\Longrightarrow\quad z_v \le\kappa, u → v ∑ z u > 2 1 + κ ⟹ z v ≤ κ , ∑ u → v z u < 1 2 − κ ⟹ z v ≥ 1 − κ . \sum_{u\to v} z_u < \frac{1}{2}-\kappa\quad\Longrightarrow\quad z_v \ge1-\kappa. u → v ∑ z u < 2 1 − κ ⟹ z v ≥ 1 − κ . Thus the decoded vector is a solution of the threshold game.
The exact analysis has two parts. First, market clearing forces q v = a 2 p v q_v=a^2p_v q v = a 2 p v and m v = a p v m_v=ap_v m v = a p v . Second, the resulting wire payments relate the incoming sum to the expenditure of floor and upper buyers. When the incoming sum is outside the threshold interval, this forces p v p_v p v to the corresponding lower or upper endpoint. We derive the necessary size inequalities in this order. All supplies and buyer counts are positive integers, and each requirement remains in force after it is introduced. Subsection 4.4 gives a simultaneous choice; the arithmetic verification is in Appendix § 8 . The subsequent robustness argument proves the theorem from the same expenditure identities.
Reference prices and lower bounds on target prices
Fix a normalized exact equilibrium and equalize its group prices using Lemma 2.3 . By Lemma 2.4 , no buyer spends on goods she values at zero. The following observation controls each reference price independently of the other groups.
Lemma 4.2 (Reference price bounds). Consider a group of supply S S S with A > S A>S A > S anchors, each assigning utility one to this group and zero to every other good. Suppose at most T T T other buyers approve the group, and let E E E be their total expenditure on it. At an exact equilibrium, its price r r r satisfies
r S = A + E , 0 ≤ E ≤ T , and hence A S ≤ r ≤ A + T S . rS=A+E,\qquad0\le E\le T,\qquad\text{and hence}\qquad\frac{A}{S}\le r\le\frac{A+T}{S}. r S = A + E , 0 ≤ E ≤ T , and hence S A ≤ r ≤ S A + T . Proof. If r ≤ 1 r\le1 r ≤ 1 , every anchor has optimal utility one and must receive one unit from the group. This is impossible because A > S A>S A > S . Thus r > 1 r>1 r > 1 . Each anchor buys 1 / r 1/r 1/ r units and spends one, while all other approvers together spend between zero and T T T . Market clearing gives the identity.
For λ > 1 \lambda>1 λ > 1 and η > 0 \eta>0 η > 0 , the choices
S = ⌈ T + 1 a η ⌉ , A = ⌈ λ S ⌉ S=\left\lceil\frac{T+1}{a\eta}\right\rceil,\qquad A=\lceil\lambda S\rceil S = ⌈ a η T + 1 ⌉ , A = ⌈ λ S ⌉
give λ ≤ r ≤ λ + ( T + 1 ) / S ≤ λ + a η \lambda\le r\le\lambda+(T+1)/S\le\lambda+a\eta λ ≤ r ≤ λ + ( T + 1 ) / S ≤ λ + a η . Apply this construction with ( λ , T ) = ( a L , F v ) (\lambda,T)=(aL,F_v) ( λ , T ) = ( a L , F v ) and ( a U , c v ) (aU,c_v) ( a U , c v ) , respectively:
S F v R = ⌈ F v + 1 a η ⌉ , A F v R = ⌈ a L S F v R ⌉ , S^R_{F_v}=\left\lceil\frac{F_v+1}{a\eta}\right\rceil,\qquad A^R_{F_v}=\left\lceil aL S^R_{F_v}\right\rceil, S F v R = ⌈ a η F v + 1 ⌉ , A F v R = ⌈ a L S F v R ⌉ ,
S U v R = ⌈ c v + 1 a η ⌉ , A U v R = ⌈ a U S U v R ⌉ . (5) S^R_{U_v}=\left\lceil\frac{c_v+1}{a\eta}\right\rceil,\qquad A^R_{U_v}=\left\lceil aU S^R_{U_v}\right\rceil. \tag*{(5)} S U v R = ⌈ a η c v + 1 ⌉ , A U v R = ⌈ a U S U v R ⌉ . (5)
We impose
a L ≥ 1 + a 2 a , a ( U + η ) < 1 a , L + η < U . (6) aL\ge\frac{1+a}{2a},\qquad a(U+\eta)<\frac{1}{a},\qquad L+\eta<U. \tag*{(6)} a L ≥ 2 a 1 + a , a ( U + η ) < a 1 , L + η < U . (6)
The two reference prices then satisfy
a L ≤ r F v ≤ a ( L + η ) < a U ≤ r U v ≤ a ( U + η ) . aL \le r_{Fv} \le a(L+\eta) < aU \le r_{Uv} \le a(U+\eta). a L ≤ r F v ≤ a ( L + η ) < a U ≤ r U v ≤ a ( U + η ) .
In particular, both references cost more than one, and a floor buyer can obtain utility 1 / r F v > a 1/r_{Fv}>a 1/ r F v > a from her reference alone.
Choose the floor population large enough that the targets cannot supply a fixed positive quantity to every floor buyer:
θ = min { a , 1 − a 2 } , F v = ⌈ S L + S M θ ⌉ + 1. (7) \theta=\min\left\{a,\frac{1-a}{2}\right\},\qquad F_v=\left\lceil\frac{S_L+S_M}{\theta}\right\rceil+1. \tag*{(7)} θ = min { a , 2 1 − a } , F v = ⌈ θ S L + S M ⌉ + 1. (7)
Lemma 4.3 (Reference intervals and target floors). Under (5) , (6) , and (7) , the reference prices lie in the intervals above and
q v ≥ a r F v , m v ≥ r F v . q_v \ge ar_{Fv},\qquad m_v \ge r_{Fv}. q v ≥ a r F v , m v ≥ r F v . A floor buyer spends on low goods only if q v = a r F v q_v=ar_{Fv} q v = a r F v , and on middle goods only if m v = r F v m_v=r_{Fv} m v = r F v .
Proof. The reference bounds follow from Lemma 4.2 . Write r = r F v r=r_{Fv} r = r F v and suppose q v < a r q_v<ar q v < a r or m v < r m_v<r m v < r . One target is then free or has a strictly greater utility-per-dollar ratio than the reference. An optimal floor bundle cannot contain both reference goods and zero-utility filler. Indeed, transferring a small amount of reference expenditure to the better target and adjusting the filler improves utility; a free target can directly replace filler.
If the bundle contains no reference goods, its target quantity exceeds a a a , since its utility is at least 1 / r > a 1/r>a 1/ r > a and every unit has utility at most one. If it contains no filler, its reference quantity is at most 1 / r 1/r 1/ r , and its target quantity is at least
1 − 1 r ≥ 1 − a 1 + a ≥ 1 − a 2 . 1-\frac{1}{r}\ge\frac{1-a}{1+a}\ge\frac{1-a}{2}. 1 − r 1 ≥ 1 + a 1 − a ≥ 2 1 − a .
Thus every floor buyer receives at least θ \theta θ target units, contrary to F v θ > S L + S M F_v\theta>S_L+S_M F v θ > S L + S M .
It follows that the reference has a weakly greater utility-per-dollar ratio than either target. The bundle consisting of 1 / r 1/r 1/ r reference units and free filler attains utility 1 / r 1/r 1/ r . Any positive target expenditure in an optimal bundle therefore requires equality of that target’s ratio with the reference ratio.
The target-price equalities
To prove m v = a p v m_v=ap_v m v = a p v , we first show that upper buyers must spend on high goods. This requires a bound on incoming wire expenditure that does not assume either target-price equality. Set γ = a 2 / ( 1 − a 2 ) \gamma=a^2/(1-a^2) γ = a 2 / ( 1 − a 2 ) and choose
w = U − L = 2 γ K , L = 1 a 2 − 3 γ K , U = 1 a 2 − 1 γ K . (8) w=U-L=\frac{2}{\gamma K},\qquad L=\frac{1}{a^2}-\frac{3}{\gamma K},\qquad U=\frac{1}{a^2}-\frac{1}{\gamma K}. \tag*{(8)} w = U − L = γ K 2 , L = a 2 1 − γ K 3 , U = a 2 1 − γ K 1 . (8)
η = τ w , 0 < τ ≤ κ / 100. (9) \eta=\tau w,\qquad0<\tau\le\kappa/100. \tag*{(9)} η = τ w , 0 < τ ≤ κ /100. (9)
Thus 1 − a 2 L = 3 ( 1 − a 2 ) / K 1-a^2L=3(1-a^2)/K 1 − a 2 L = 3 ( 1 − a 2 ) / K . Together with the price bounds below, this identity bounds each incoming wire buyer’s high expenditure by O a ( 1 / K ) O_a(1/K) O a ( 1/ K ) . Assume K ≥ 48 K\ge48 K ≥ 48 and require
( L + η ) S H < c v . (L+\eta)S_H<c_v. ( L + η ) S H < c v .
For a constant C > 0 C>0 C > 0 , set
S L = o v K + C . (10) S_L=o_vK+C. \tag*{(10)} S L = o v K + C . (10)
with C < b v C < b_v C < b v and
o v K + b v S L < a L . \frac{o_vK+b_v}{S_L}<aL. S L o v K + b v < a L .
The strict excess S L > o v K S_L>o_vK S L > o v K will also be needed for the lower link.
Lemma 4.4 (Preliminary price and wire bounds). Under these requirements,
p v ≥ r F v / a ≥ L , a 2 L ≤ q v ≤ o v K + b v S L < a L . p_v\ge r_{Fv}/a\ge L,\qquad a^2L\le q_v\le\frac{o_vK+b_v}{S_L}<aL. p v ≥ r F v / a ≥ L , a 2 L ≤ q v ≤ S L o v K + b v < a L . All incoming wires together spend less than 9 on H v H_v H v .
Proof. Suppose p v < r F v / a p_v<r_{Fv}/a p v < r F v / a . The floor bounds and reference intervals give m v > a p v m_v>ap_v m v > a p v and r U v > a p v r_{Uv}>ap_v r U v > a p v . Both alternatives cost more than one. Each upper buyer therefore demands 1 / max { 1 , p v } 1/\max\{1,p_v\} 1/ max { 1 , p v } high units. Since p v < L + η p_v<L+\eta p v < L + η and L + η > 1 L+\eta>1 L + η > 1 , their total demand exceeds c v / ( L + η ) > S H c_v/(L+\eta)>S_H c v / ( L + η ) > S H , a contradiction.
The floor bound gives q v ≥ a r F v ≥ a 2 L q_v\ge ar_{Fv}\ge a^2L q v ≥ a r F v ≥ a 2 L . If floors spend on low goods, then q v = a r F v < 1 q_v=ar_{Fv}<1 q v = a r F v < 1 . Otherwise the entire low revenue comes from lower links and outgoing wires, so q v S L ≤ b v + o v K q_vS_L\le b_v+o_vK q v S L ≤ b v + o v K . Because C < b v C<b_v C < b v , ( o v K + b v ) / S L > 1 (o_vK+b_v)/S_L>1 ( o v K + b v ) / S L > 1 , and the stated upper bound holds in both cases.
An incoming wire faces a low price q < a L ≤ a p q<aL\le ap q < a L ≤ a p and a high price p ≥ L p\ge L p ≥ L . If q ≥ 1 q\ge1 q ≥ 1 , it buys no high goods. If q < 1 q<1 q < 1 , Lemma 2.5 gives high expenditure p ( 1 − q ) / ( p − q ) p(1-q)/(p-q) p ( 1 − q ) / ( p − q ) . Using q ≥ a 2 L q\ge a^2L q ≥ a 2 L , q < 1 q<1 q < 1 , and p ≥ L p\ge L p ≥ L ,
p ( 1 − q ) p − q ≤ L L − 1 ( 1 − a 2 L ) = 3 a 2 w L 2 ( L − 1 ) < 2 a 2 w L L − 1 . \frac{p(1-q)}{p-q}\le\frac{L}{L-1}(1-a^2L)=\frac{3a^2wL}{2(L-1)}<\frac{2a^2wL}{L-1}. p − q p ( 1 − q ) ≤ L − 1 L ( 1 − a 2 L ) = 2 ( L − 1 ) 3 a 2 w L < L − 1 2 a 2 w L . There are at most 2 K 2K 2 K incoming buyers, whose total high expenditure is therefore at most
4 K a 2 w L L − 1 = 8 + 24 a 2 K − 3 < 9. \frac{4Ka^2wL}{L-1}=8+\frac{24a^2}{K-3}<9. L − 1 4 K a 2 w L = 8 + K − 3 24 a 2 < 9.
We now impose the remaining inequalities used to prove the links:
L S H > 10 , a L S M > c v + 10 , c v > b v , 3 b v ( 1 + a ) K < 1. (11) LS_H>10,\qquad aLS_M>c_v+10,\qquad c_v>b_v,\qquad\frac{3b_v(1+a)}{K}<1. \tag*{(11)} L S H > 10 , a L S M > c v + 10 , c v > b v , K 3 b v ( 1 + a ) < 1. (11)
The first requires more high revenue than incoming wires can provide. The second requires more middle revenue than upper buyers can provide alone. These two facts rule out the strict price comparisons in the next two lemmas.
Lemma 4.5 (The upper link). The middle and high prices satisfy
m v = a p v , p v ≤ r U v / a . m_v=ap_v,\qquad p_v\le r_{Uv}/a. m v = a p v , p v ≤ r U v / a . Proof. High revenue is at least L S H > 10 LS_H>10 L S H > 10 , and incoming wires contribute less than 9. Hence some upper buyer purchases high goods. All her approved goods cost more than one, so she spends only on groups maximizing utility per dollar. Her positive high expenditure implies m v ≥ a p v m_v\ge ap_v m v ≥ a p v and r U v ≥ a p v r_{Uv}\ge ap_v r U v ≥ a p v .
If m v > a p v m_v>ap_v m v > a p v , upper buyers purchase no middle goods. Floor buyers purchase none either, because m v > a p v ≥ r F v m_v>ap_v\ge r_{Fv} m v > a p v ≥ r F v . Lower links would then have to provide all middle revenue. Their total budget b v b_v b v is smaller than m v S M ≥ a L S M > c v > b v m_vS_M\ge aLS_M>c_v>b_v m v S M ≥ a L S M > c v > b v , a contradiction. Thus m v = a p v m_v=ap_v m v = a p v .
Lemma 4.6 (The lower link). The low price satisfies q v = a m v = a 2 p v < 1 q_v=am_v=a^2p_v<1 q v = a m v = a 2 p v < 1 .
:::`
Proof. Suppose first that q v > a m v q_v > am_v q v > a m v . Lower links then purchase no low goods. Since m v ≥ r F v m_v \ge r_{Fv} m v ≥ r F v , floor buyers also purchase none. The o v K o_vK o v K outgoing wire buyers cannot clear S L > o v K S_L > o_vK S L > o v K low goods because each receives only one unit in total. Consequently,
q v ≤ a m v = a 2 p v ≤ a 2 ( U + η ) < 1. q_v \le am_v = a^2p_v \le a^2(U+\eta) < 1. q v ≤ a m v = a 2 p v ≤ a 2 ( U + η ) < 1.
Suppose instead that q v < a m v q_v < am_v q v < a m v . Since q v ≥ a r F v q_v \ge ar_{Fv} q v ≥ a r F v , we have m v > r F v m_v > r_{Fv} m v > r F v , and floor buyers purchase no middle goods. Lemma 2.5 bounds each lower buyer’s middle expenditure by
m v ( 1 − q v ) m v − q v < 1 − q v 1 − a ≤ 1 − a 2 L 1 − a = 3 ( 1 + a ) K . \frac{m_v(1-q_v)}{m_v-q_v} < \frac{1-q_v}{1-a} \le\frac{1-a^2L}{1-a} = \frac{3(1+a)}{K}. m v − q v m v ( 1 − q v ) < 1 − a 1 − q v ≤ 1 − a 1 − a 2 L = K 3 ( 1 + a ) .
By (11) , lower links contribute less than one in total, and upper buyers contribute at most c v c_v c v . This is insufficient for the middle revenue m v S M ≥ a L S M > c v + 10 m_vS_M \ge aLS_M > c_v+10 m v S M ≥ a L S M > c v + 10 . Hence q v = a m v q_v=am_v q v = a m v .
Proposition 4.7 (The price chain). Every normalized exact equilibrium has equal prices within each group and satisfies
q v = a m v = a 2 p v , q v < 1 < m v < p v , r F v a ≤ p v ≤ r U v a . q_v=am_v=a^2p_v,\qquad q_v<1<m_v<p_v,\qquad\frac{r_{Fv}}{a}\le p_v\le\frac{r_{Uv}}{a}. q v = a m v = a 2 p v , q v < 1 < m v < p v , a r F v ≤ p v ≤ a r U v . Every buyer spends one. Lower links spend only on the targets. Upper buyers spend only on the targets when p v < r U v / a p_v<r_{Uv}/a p v < r U v / a ; floor buyers spend on targets only when p v = r F v / a p_v=r_{Fv}/a p v = r F v / a .
Proof. The preceding lemmas give all the price relations for the equalized equilibrium. Every group assigned utility one has price above one. Lemma 2.4 therefore implies that every buyer spends her full budget.
Lower links approve only targets. If p v < r U v / a p_v<r_{Uv}/a p v < r U v / a , the upper reference has a strictly smaller utility-per-dollar ratio than either upper target, so upper buyers spend only on the targets. At p v = r U v / a p_v=r_{Uv}/a p v = r U v / a , all their approved groups have the same ratio; any division of the unit budget among them is optimal and can be completed with free filler. For floor buyers, the target spending equalities in Lemma 4.3 are both equivalent to p v = r F v / a p_v=r_{Fv}/a p v = r F v / a .
Finally, the equalized prices have total revenue N N N . The original prices are no smaller, while their total revenue is at most N N N . Thus no price decreased under equalization, and the original prices were already equal within each group.
Expenditure identities and exact decoding
The price chain gives an explicit expression for each wire payment. For u → v u\to v u → v , we have q u = a 2 p u < 1 < p v q_u=a^2p_u<1<p_v q u = a 2 p u < 1 < p v and q u < a p v q_u<ap_v q u < a p v . By Lemma 2.5 , every wire buyer receives the following quantities from L u L_u L u and H v H_v H v , respectively:
x = p v − 1 p v − q u , y = 1 − q u p v − q u . (12) x=\frac{p_v-1}{p_v-q_u},\qquad y=\frac{1-q_u}{p_v-q_u}. \tag*{(12)} x = p v − q u p v − 1 , y = p v − q u 1 − q u . (12)
The K K K buyers together spend I u v I_{uv} I uv on H v H_v H v and K − I u v K-I_{uv} K − I uv on L u L_u L u , where
I u v = K p v ( 1 − a 2 p u ) p v − a 2 p u . (13) I_{uv}=\frac{Kp_v(1-a^2p_u)}{p_v-a^2p_u}. \tag*{(13)} I uv = p v − a 2 p u K p v ( 1 − a 2 p u ) . (13)
Recall t u = ( p u − L ) / w t_u=(p_u-L)/w t u = ( p u − L ) / w and z u = clip ( t u ) z_u=\operatorname{clip}(t_u) z u = clip ( t u ) . The reference bounds imply 0 ≤ t u ≤ 1 + τ 0\le t_u\le1+\tau 0 ≤ t u ≤ 1 + τ and 0 ≤ t u − z u ≤ τ 0\le t_u-z_u\le\tau 0 ≤ t u − z u ≤ τ . Substituting p u = L + w t u p_u=L+wt_u p u = L + w t u into (13) , and using K ( 1 − a 2 p u ) = ( 1 − a 2 ) ( 3 − 2 t u ) K(1-a^2p_u)=(1-a^2)(3-2t_u) K ( 1 − a 2 p u ) = ( 1 − a 2 ) ( 3 − 2 t u ) , gives
I u v = 3 − 2 t u + ϵ u v , ϵ u v = a 2 ( 3 − 2 t u ) ( p u − p v ) p v − a 2 p u . (14) I_{uv}=3-2t_u+\epsilon_{uv},\qquad\epsilon_{uv}=\frac{a^2(3-2t_u)(p_u-p_v)}{p_v-a^2p_u}. \tag*{(14)} I uv = 3 − 2 t u + ϵ uv , ϵ uv = p v − a 2 p u a 2 ( 3 − 2 t u ) ( p u − p v ) . (14)
Since p u , p v ∈ [ L , U + η ] p_u,p_v \in[L,U+\eta] p u , p v ∈ [ L , U + η ] and p v − a 2 p u ≥ L − 1 p_v-a^2p_u \ge L-1 p v − a 2 p u ≥ L − 1 ,
∣ e u v ∣ ≤ 3 a 2 ( w + η ) L − 1 = O a ( 1 / K ) . |e_{uv}| \le\frac{3a^2(w+\eta)}{L-1}=O_a(1/K). ∣ e uv ∣ ≤ L − 1 3 a 2 ( w + η ) = O a ( 1/ K ) .
For a self-loop, e v v = 0 e_{vv}=0 e v v = 0 .
At vertex v v v , let R v R_v R v be the total revenue of its three target groups, E v E_v E v their receipts from wires, and W v W_v W v , V v V_v V v the expenditures of floor and upper buyers on these targets. Define Φ v \Phi_v Φ v to be target revenue minus wire receipts and the full budgets of the two link populations. Explicitly,
R v = q v S L + m v S M + p v S H = p v ( a 2 S L + a S M + S H ) , R_v=q_vS_L+m_vS_M+p_vS_H=p_v(a^2S_L+aS_M+S_H), R v = q v S L + m v S M + p v S H = p v ( a 2 S L + a S M + S H ) ,
W v ≥ 0 , 0 ≤ V v ≤ c v , W_v\ge0,\qquad0\le V_v\le c_v, W v ≥ 0 , 0 ≤ V v ≤ c v ,
E v = ∑ v → t ( K − I v t ) + ∑ u → v I u v . (15) E_v=\sum_{v\to t}(K-I_{vt})+\sum_{u\to v}I_{uv}. \tag*{(15)} E v = v → t ∑ ( K − I v t ) + u → v ∑ I uv . (15)
Φ v : = R v − E v − b v − c v = W v + ( V v − c v ) . (16) \Phi_v:=R_v-E_v-b_v-c_v=W_v+(V_v-c_v). \tag*{(16)} Φ v := R v − E v − b v − c v = W v + ( V v − c v ) . (16)
The equality in (16) is market clearing: the lower links spend exactly b v b_v b v on targets, and the remaining target receipts are E v , W v , V v E_v,W_v,V_v E v , W v , V v .
Equation (16) relates the sign of Φ v \Phi_v Φ v to the location of p v p_v p v . If Φ v > 0 \Phi_v>0 Φ v > 0 , then W v > 0 W_v>0 W v > 0 , so floors purchase targets. If Φ v < 0 \Phi_v<0 Φ v < 0 , then V v < c v V_v<c_v V v < c v , so upper buyers spend on their reference. Proposition 4.7 therefore implies
Φ v > 0 ⟹ p v = r F v / a ≤ L + η , Φ v < 0 ⟹ p v = r U v / a ≥ U . \Phi_v>0\quad\Longrightarrow\quad p_v=r_{Fv}/a\le L+\eta,\qquad
\Phi_v<0\quad\Longrightarrow\quad p_v=r_{Uv}/a\ge U. Φ v > 0 ⟹ p v = r F v / a ≤ L + η , Φ v < 0 ⟹ p v = r U v / a ≥ U .
It remains to express Φ v \Phi_v Φ v in terms of the incoming variables. Writing e v = ∑ u → v e u v − ∑ v → t e v t e_v=\sum_{u\to v}e_{uv}-\sum_{v\to t}e_{vt} e v = ∑ u → v e uv − ∑ v → t e v t , (14) yields
E v = o v ( K − 3 + 2 t v ) + 3 h v − 2 ∑ u → v t u + e v . E_v=o_v(K-3+2t_v)+3h_v-2\sum_{u\to v}t_u+e_v. E v = o v ( K − 3 + 2 t v ) + 3 h v − 2 u → v ∑ t u + e v .
We require the target revenue and link budgets to satisfy
a 2 S L + a S M + S H = o v γ K , b v + c v = o v γ K + 1 − 3 h v . a^2S_L+aS_M+S_H=o_v\gamma K,\qquad b_v+c_v=o_v\gamma K+1-3h_v. a 2 S L + a S M + S H = o v γ K , b v + c v = o v γ K + 1 − 3 h v .
Because γ K w = 2 \gamma K w=2 γ K w = 2 and γ K ( L − 1 ) = K − 3 \gamma K(L-1)=K-3 γ K ( L − 1 ) = K − 3 , these identities cancel the term 2 o v t v 2o_vt_v 2 o v t v from Φ v \Phi_v Φ v and leave the threshold constant 1 / 2 1/2 1/2 after division by two. Both identities and (10) hold if, for a constant b > 2 C b>2C b > 2 C , we set
b v = b + 1 − 3 h v , c v = o v γ K − b , b_v=b+1-3h_v,\qquad c_v=o_v\gamma K-b, b v = b + 1 − 3 h v , c v = o v γ K − b ,
S L = o v K + C , S M = a ( c v + C ) , S H = a 2 ( b − 2 C ) . (17) S_L=o_vK+C,\qquad S_M=a(c_v+C),\qquad S_H=a^2(b-2C). \tag*{(17)} S L = o v K + C , S M = a ( c v + C ) , S H = a 2 ( b − 2 C ) . (17)
Indeed, R v = o v γ K p v = o v γ K + o v ( K − 3 + 2 t v ) R_v=o_v\gamma Kp_v=o_v\gamma K+o_v(K-3+2t_v) R v = o v γ K p v = o v γ K + o v ( K − 3 + 2 t v ) , and subtraction gives
Φ v = 2 ∑ u → v t u − 1 − e v . (18) \Phi_v=2\sum_{u\to v}t_u-1-e_v. \tag*{(18)} Φ v = 2 u → v ∑ t u − 1 − e v . (18)
A self-loop contributes t v t_v t v to this incoming sum, as required by the threshold game.
There are at most four incident wire errors and two incoming clipping errors. Thus
∣ Φ v 2 − ( ∑ u → v z u − 1 2 ) ∣ ≤ 6 a 2 w ( 1 + τ ) L − 1 + 2 τ . (19) \left|\frac{\Phi_v}{2}-\left(\sum_{u\to v}z_u-\frac{1}{2}\right)\right|
\le\frac{6a^2w(1+\tau)}{L-1}+2\tau. \tag*{(19)} 2 Φ v − ( u → v ∑ z u − 2 1 ) ≤ L − 1 6 a 2 w ( 1 + τ ) + 2 τ . (19)
The parameter choice in the next subsection makes the right-hand side less than κ / 10 \kappa/10 κ /10 ; see (29) .
Proposition 4.8 (Exact decoding). For that parameter choice, every exact equilibrium decodes to values satisfying
∑ u → v z u ≥ 1 2 + κ 2 ⟹ z v ≤ κ 4 , \sum_{u \to v} z_u \ge\frac{1}{2}+\frac{\kappa}{2} \quad\Longrightarrow\quad z_v \le\frac{\kappa}{4}, u → v ∑ z u ≥ 2 1 + 2 κ ⟹ z v ≤ 4 κ , ∑ u → v z u < 1 2 − κ 2 ⟹ z v ≥ 1 − κ 4 . \sum_{u \to v} z_u < \frac{1}{2}-\frac{\kappa}{2} \quad\Longrightarrow\quad z_v \ge1-\frac{\kappa}{4}. u → v ∑ z u < 2 1 − 2 κ ⟹ z v ≥ 1 − 4 κ .
Proof. In the first case, (19) gives Φ v > 0 \Phi_v>0 Φ v > 0 . Hence p v ≤ L + η p_v\le L+\eta p v ≤ L + η and z v ≤ η / w = τ < κ / 4 z_v\le\eta/w=\tau<\kappa/4 z v ≤ η / w = τ < κ /4 . In the second case, Φ v < 0 \Phi_v<0 Φ v < 0 , so p v ≥ U p_v\ge U p v ≥ U and z v = 1 z_v=1 z v = 1 .
Choosing the integer multiplicities
We now choose the remaining constants to satisfy the inequalities used in the exact analysis. Write a = A / D a=A/D a = A / D in lowest terms and put
C = 16 D 2 , b = 4 C . C=16D^2,\qquad b=4C. C = 16 D 2 , b = 4 C .
For any rational 0 < τ ≤ κ / 100 0<\tau\le\kappa/100 0 < τ ≤ κ /100 , choose a positive multiple K K K of D 2 ( D 2 − A 2 ) D^2(D^2-A^2) D 2 ( D 2 − A 2 ) such that
K ≥ 8 b + 200 / κ a 2 ( 1 − a ) . (20) K\ge\frac{8b+200/\kappa}{a^2(1-a)}. \tag*{(20)} K ≥ a 2 ( 1 − a ) 8 b + 200/ κ . (20)
We call these values of K K K admissible . Evaluate the remaining parameters in the following order: first L , U , w , η L,U,w,\eta L , U , w , η from (8) and (9) ; then b v , c v , S L , S M , S H b_v,c_v,S_L,S_M,S_H b v , c v , S L , S M , S H from (17) ; then F v F_v F v from (7) ; and finally the reference supplies and anchor counts from (5) .
Lemmas A.1 and A.2 prove that all counts and supplies are positive integers and that every inequality used above holds. They also establish the error bound in (29) . Lemma A.3 proves N > G l i s t e d N>G_{\mathrm{listed}} N > G listed , completing the construction.
For approximate equilibria, we will choose a fixed value τ a ≤ κ / 100 \tau_a\le\kappa/100 τ a ≤ κ /100 and an additional cutoff K a K_a K a , both depending only on a a a . Theorem 5.7 provides these constants and applies to every admissible K ≥ K a K\ge K_a K ≥ K a . This uniformity is used again in § 5 .
Robustness to approximation
For inverse-linear accuracy, we make the total expenditure on unapproved goods sufficiently small and prove correct decoding at every vertex. § 5.2 will use a local version of this argument when some decoding failures are permitted.
Put n = ∣ V ∣ n=|V| n = ∣ V ∣ and equalize group prices using Lemma 2.3 . This preserves the equilibrium error and the minimum-price decoder. Let G v G_v G v be the union of the five groups at v v v , and put
W = ∑ i ∑ j : u i j = 0 p j x i j , W v = ∑ i ∑ j ∈ G v : u i j = 0 p j x i j . \mathcal{W}=\sum_i\sum_{j:u_{ij}=0}p_jx_{ij},\qquad
\mathcal{W}_v=\sum_i\sum_{j\in G_v:u_{ij}=0}p_jx_{ij}. W = i ∑ j : u ij = 0 ∑ p j x ij , W v = i ∑ j ∈ G v : u ij = 0 ∑ p j x ij .
Thus W \mathcal{W} W is total unapproved expenditure and ∑ v W v ≤ W \sum_v\mathcal{W}_v\le\mathcal{W} ∑ v W v ≤ W . The quantity W v \mathcal{W}_v W v is distinct from the floor buyers’ target expenditure W v W_v W v . All implicit constants below depend only on a a a , uniformly over the graph, admissible K K K , and 0 < τ ≤ κ / 100 0<\tau\le\kappa/100 0 < τ ≤ κ /100 .
Lemma 4.9 (Unapproved expenditure). There are positive rational constants d a , g a , c a , C a d_a,g_a,c_a,C_a d a , g a , c a , C a , depending only on a a a , such that for every sufficiently large admissible K K K , every normalized additive ε \varepsilon ε -equilibrium with ε ≤ min { c a , 1 / ( C a K ) } \varepsilon\le\min\{c_a,1/(C_aK)\} ε ≤ min { c a , 1/ ( C a K )} satisfies
W ≤ C a N ε . \mathcal{W}\le C_aN\varepsilon. W ≤ C a N ε .
Every group valued at one has price greater than 1 + d a 1+d_a 1 + d a , and every buyer has optimal utility at most 1 − g a 1-g_a 1 − g a .
Proof. Lemma B.2 gives the price and utility gaps. For each buyer i i i , choose a group f ( i ) f(i) f ( i ) valued at one. Her optimal demand dual satisfies
β i ( p f ( i ) − 1 ) ≥ 1 − V i ( p ) ≥ g a . \beta_i(p_{f(i)}-1) \ge1-V_i(p) \ge g_a. β i ( p f ( i ) − 1 ) ≥ 1 − V i ( p ) ≥ g a .
By Lemma B.1 , her unapproved expenditure is at most 2 ε / β i ≤ ( 2 ε / g a ) p f ( i ) 2\varepsilon/\beta_i \le(2\varepsilon/g_a)p_{f(i)} 2 ε / β i ≤ ( 2 ε / g a ) p f ( i ) .
Choose middle goods for lower links, the floor reference for floor buyers, each anchor’s own reference, and high goods for upper buyers and wires. For middle and reference groups, the number of buyers selecting a group is at most a constant times its supply; for high groups, it is at most O a ( K ) O_a(K) O a ( K ) times the supply. Since total revenue is at most N ( 1 + ε ) N(1+\varepsilon) N ( 1 + ε ) , writing R H = S H ∑ v p v R_H=S_H\sum_v p_v R H = S H ∑ v p v gives
∑ i p f ( i ) = O a ( N + K R H ) , R H ≤ ∑ v ( c v + h v K ) ( 1 + ε ) + W = O a ( K n ) + W . \sum_i p_{f(i)}=O_a(N+KR_H), \qquad R_H\le\sum_v(c_v+h_vK)(1+\varepsilon)+\mathcal{W}=O_a(Kn)+\mathcal{W}. i ∑ p f ( i ) = O a ( N + K R H ) , R H ≤ v ∑ ( c v + h v K ) ( 1 + ε ) + W = O a ( K n ) + W .
The reference counts in (5) give N = Ω a ( K 2 n ) N=\Omega_a(K^2n) N = Ω a ( K 2 n ) throughout the permitted range of τ \tau τ . Consequently,
W ≤ O a ( ε ) ( N + K W ) . \mathcal{W}\le O_a(\varepsilon)(N+K\mathcal{W}). W ≤ O a ( ε ) ( N + K W ) .
Taking C a C_a C a sufficiently large and c a c_a c a sufficiently small, the assumption ε ≤ min { c a , 1 / ( C a K ) } \varepsilon\le\min\{c_a,1/(C_aK)\} ε ≤ min { c a , 1/ ( C a K )} lets us move the term proportional to K ε W K\varepsilon\mathcal{W} K ε W to the left and obtain the claimed bound.
Lemma 4.10 (Global decoding). There are positive rational constants τ a ≤ κ / 100 \tau_a\le\kappa/100 τ a ≤ κ /100 , ζ a , e a \zeta_a,e_a ζ a , e a , and an integer K a ≥ 1 K_a\ge1 K a ≥ 1 , depending only on a a a , such that the following holds for every admissible K ≥ K a K\ge K_a K ≥ K a . If a normalized additive ε \varepsilon ε -equilibrium of M ( G ; a , τ a , K ) \mathcal{M}(G;a,\tau_a,K) M ( G ; a , τ a , K ) satisfies
ε ≤ e a / K 2 , W ≤ ζ a , \varepsilon\le e_a/K^2,\qquad\mathcal{W}\le\zeta_a, ε ≤ e a / K 2 , W ≤ ζ a , then its decoded vector is a κ \kappa κ -threshold solution of G G G . The constants can be chosen so that ε ≤ e a / K 2 \varepsilon\le e_a/K^2 ε ≤ e a / K 2 also implies the hypotheses of Lemma 4.9 .
Proof. Since W v ≤ W \mathcal{W}_v\le\mathcal{W} W v ≤ W at every vertex, the price and expenditure estimates in Appendix § 9 apply everywhere when K K K is large and τ a \tau_a τ a , K 2 ε K^2\varepsilon K 2 ε , and W \mathcal{W} W are sufficiently small. In particular, Lemma B.4 gives
q v = a 2 p v + O a ( K ε ) , m v = a p v + O a ( K ε ) . q_v=a^2p_v+O_a(K\varepsilon),\qquad m_v=ap_v+O_a(K\varepsilon). q v = a 2 p v + O a ( K ε ) , m v = a p v + O a ( K ε ) .
Evaluate Φ v \Phi_v Φ v using the ideal prices a 2 p u a^2p_u a 2 p u , a p u ap_u a p u , p u p_u p u , as in Lemma B.5. That lemma gives
Φ v = W v + ( V v − c v ) + O a ( K 2 ε + W ) , \Phi_v=\mathcal{W}_v+(V_v-c_v)+O_a(K^2\varepsilon+\mathcal{W}), Φ v = W v + ( V v − c v ) + O a ( K 2 ε + W ) ,
Φ v 2 = ∑ u → v z u − 1 2 + O a ( 1 / K + τ a + K 2 ε ) . \frac{\Phi_v}{2}=\sum_{u\to v}z_u-\frac{1}{2}+O_a(1/K+\tau_a+K^2\varepsilon). 2 Φ v = u → v ∑ z u − 2 1 + O a ( 1/ K + τ a + K 2 ε ) .
Suppose ∑ u → v z u > 1 / 2 + κ \sum_{u\to v}z_u>1/2+\kappa ∑ u → v z u > 1/2 + κ but z v > κ z_v>\kappa z v > κ . The second identity gives Φ v > κ \Phi_v>\kappa Φ v > κ for sufficiently small errors. Also p v > L + κ w p_v>L+\kappa w p v > L + κ w , so the approximate price relations and reference bounds give reduced slack Ω a ( κ w ) \Omega_a(\kappa w) Ω a ( κ w ) on both floor targets. The demand estimate in Lemma B.1 , together with F v = O a ( K ) F_v=O_a(K) F v = O a ( K ) and w = Θ a ( 1 / K ) w=\Theta_a(1/K) w = Θ a ( 1/ K ) , yields
W v = O a ( K 2 ε / κ ) , V v − c v ≤ c v ε . \mathcal{W}_v=O_a(K^2\varepsilon/\kappa),\qquad V_v-c_v\le c_v\varepsilon. W v = O a ( K 2 ε / κ ) , V v − c v ≤ c v ε .
The first identity therefore gives Φ v ≤ O a ( K 2 ε / κ + W ) \Phi_v\le O_a(K^2\varepsilon/\kappa+\mathcal{W}) Φ v ≤ O a ( K 2 ε / κ + W ) , a contradiction.
If instead ∑ u → v z u < 1 / 2 − κ \sum_{u\to v}z_u<1/2-\kappa ∑ u → v z u < 1/2 − κ but z v < 1 − κ z_v<1-\kappa z v < 1 − κ , then Φ v < − κ \Phi_v<-\kappa Φ v < − κ and p v < U − κ w p_v<U-\kappa w p v < U − κ w . The upper reference has reduced slack Ω a ( κ w ) \Omega_a(\kappa w) Ω a ( κ w ) , so upper buyers spend at most O a ( K 2 ε / κ ) O_a(K^2\varepsilon/\kappa) O a ( K 2 ε / κ ) on it. Their total approved expenditure is c v + O a ( K ε ) c_v + O_a(K\varepsilon) c v + O a ( K ε ) , giving V v − c v ≥ − O a ( K 2 ε / κ ) V_v-c_v \ge-O_a(K^2\varepsilon/\kappa) V v − c v ≥ − O a ( K 2 ε / κ ) . Since W v ≥ 0 W_v \ge0 W v ≥ 0 , the first identity now gives Φ v ≥ − O a ( K 2 ε / κ + W ) \Phi_v \ge-O_a(K^2\varepsilon/\kappa+ W) Φ v ≥ − O a ( K 2 ε / κ + W ) , again a contradiction. Both contradictions hold once
H a ( 1 K + τ a + K 2 ε κ + W ) < κ / 2 H_a\left(\frac{1}{K}+\tau_a+\frac{K^2\varepsilon}{\kappa}+W\right)<\kappa/2 H a ( K 1 + τ a + κ K 2 ε + W ) < κ /2
for a sufficiently large constant H a H_a H a depending only on a a a . Choose τ a , ζ a , e a \tau_a,\zeta_a,e_a τ a , ζ a , e a sufficiently small and K a K_a K a sufficiently large to ensure this inequality and the estimates above. Taking e a ≤ min { c a , 1 / C a } e_a \le\min\{c_a,1/C_a\} e a ≤ min { c a , 1/ C a } and enlarging K a K_a K a also ensures the hypotheses of Lemma 4.9 .
For the fixed value τ a \tau_a τ a , the reference counts give N ≥ ν a K 2 n N \ge\nu_aK^2n N ≥ ν a K 2 n for some positive rational ν a \nu_a ν a depending only on a a a . Define
ε ∗ ( a ) = min { 1 , ζ a / ( 2 C a ) , ν a e a } . \varepsilon_*(a)=\min\{1,\zeta_a/(2C_a),\nu_ae_a\}. ε ∗ ( a ) = min { 1 , ζ a / ( 2 C a ) , ν a e a } .
Proof of Theorem 4.1 . Since n ≥ 1 n \ge1 n ≥ 1 , the error ε = ε ∗ ( a ) / N \varepsilon=\varepsilon_*(a)/N ε = ε ∗ ( a ) / N satisfies ε ≤ e a / K 2 \varepsilon\le e_a/K^2 ε ≤ e a / K 2 . Lemma 4.9 gives
W ≤ C a N ε = C a ε ∗ ( a ) ≤ ζ a / 2. W \le C_aN\varepsilon=C_a\varepsilon_*(a)\le\zeta_a/2. W ≤ C a N ε = C a ε ∗ ( a ) ≤ ζ a /2.
Lemma 4.10 therefore proves correct decoding at every vertex.
Completing the reduction
It remains to verify the encoding and totality requirements of the search reduction. We first record a rounding lemma for general HZ markets.
Lemma 4.11 (Rational approximate witnesses). For rational 0 < ε ≤ 1 0 < \varepsilon\le1 0 < ε ≤ 1 , every N N N -buyer HZ market with utilities in [ 0 , 1 ] [0,1] [ 0 , 1 ] has a normalized additive ε \varepsilon ε -equilibrium whose coordinates have bit length O ( 1 + log N + log ( 1 / ε ) ) O(1+\log N+\log(1/\varepsilon)) O ( 1 + log N + log ( 1/ ε )) .
The proof is given in Appendix § 10 .
Proof of Theorem 1.1 . Membership in PPAD follows from [17 Section 7] , as explained above. It remains to prove PPAD-hardness. Fix a = A / D a=A/D a = A / D and the constants of Theorem 5.7 . Choose the least admissible K ≥ K a K \ge K_a K ≥ K a and use the market M ( G ; a , τ a , K ) \mathcal{M}(G;a,\tau_a,K) M ( G ; a , τ a , K ) . All multiplicities are then constants depending only on a a a and the local degree pair.
Given a nonempty threshold instance, eliminate sinks as described before (2) , then construct the market. Lemmas A.1 and A.3 ensure positive integer sizes and equal numbers of buyers and goods. Each vertex and edge contributes a constant number of individual buyers and unit-supply goods. Thus N = O a ( ∣ V ∣ + ∣ E ∣ ) N=O_a(|V|+|E|) N = O a ( ∣ V ∣ + ∣ E ∣ ) , and the explicit utility matrix is constructible in polynomial time with entries in { 0 , a , 1 } \{0,a,1\} { 0 , a , 1 } .
The numbers of approvers of a good in the five module groups are
F v + b v + o v K , b v + c v + F v , c v + h v K , A F v R + F v , A U v R + c v . F_v+b_v+o_vK,\quad b_v+c_v+F_v,\quad c_v+h_vK,\quad A^{R}_{F_v}+F_v,\quad A^{R}_{U_v}+c_v. F v + b v + o v K , b v + c v + F v , c v + h v K , A F v R + F v , A U v R + c v .
Their maximum over the six degree pairs depends only on a a a ; balancing goods have no approvers. Lemma 4.11 provides a normalized additive ε ∗ ( a ) / N \varepsilon_*(a)/N ε ∗ ( a ) / N -equilibrium with O a ( 1 + log N ) O_a(1+\log N) O a ( 1 + log N ) bits per coordinate. Thus the search problem is total and has witnesses of polynomial length.
For every returned equilibrium, Theorem 4.1 guarantees that the minimum-price decoder solves the augmented threshold instance. Restricting to the original vertices solves the input instance. All decoding operations are rational arithmetic of polynomial complexity. For the empty graph, output the one-buyer, one-good market with utility one and decode every equilibrium to the empty assignment.
Constant-error hardness under PCP for PPAD
The inverse-linear accuracy in Theorem 1.1 can be replaced by a positive constant under PCP for PPAD.
We use the polynomial-time formulation of the conjecture of Babichenko, Papadimitriou, and Rubinstein [2 ] . It asserts that, for some fixed positive error and failure tolerances, finding a generalized-circuit assignment satisfying all but the permitted fraction of gates is PPAD-hard [6 ] . The original conjecture requires a quasilinear reduction. OpenAI [13 ] has announced a proof of that formulation; we retain the conjecture as a hypothesis.
The reduction passes through weak Pure-Circuit and weak threshold games.
Weak Pure-Circuit and threshold games
We use NOR and PURIFY gates, as in [5 ] . This formulation is equivalent to the NAND/PURIFY formulation of [6 ] : replace NAND by NOR and complement every Boolean value, leaving ⊥ \bot ⊥ fixed. The transformation preserves satisfaction of each gate and the number of times each node is used as an input.
Definition 5.1 (Pure-Circuit). An instance consists of a finite node set V C V_C V C and a nonempty collection G \mathcal{G} G of gates ( T , u , v , w ) (T,u,v,w) ( T , u , v , w ) , with pairwise distinct u , v , w ∈ V C u,v,w \in V_C u , v , w ∈ V C and T ∈ { N O R , P U R I F Y } T \in\{\mathrm{NOR},\mathrm{PURIFY}\} T ∈ { NOR , PURIFY } . A NOR gate has inputs u , v u,v u , v and output w w w ; a PURIFY gate has input u u u and outputs v , w v,w v , w . Every node is produced by exactly one gate.
An assignment is a map ξ : V C → { 0 , 1 , ⊥ } \xi: V_C \to\{0,1,\bot\} ξ : V C → { 0 , 1 , ⊥ } . A NOR gate is satisfied when
ξ u = ξ v = 0 ⟹ ξ w = 1 , \xi_u=\xi_v=0 \Longrightarrow\xi_w=1, ξ u = ξ v = 0 ⟹ ξ w = 1 , ξ u = 1 or ξ v = 1 ⟹ ξ w = 0. \xi_u=1\ \text{or}\ \xi_v=1 \Longrightarrow\xi_w=0. ξ u = 1 or ξ v = 1 ⟹ ξ w = 0. Its output is unrestricted otherwise. A PURIFY gate is satisfied when
ξ u = b ∈ { 0 , 1 } ⟹ ξ v = ξ w = b , \xi_u=b\in\{0,1\} \Longrightarrow\xi_v=\xi_w=b, ξ u = b ∈ { 0 , 1 } ⟹ ξ v = ξ w = b , ξ u = ⊥ ⟹ { ξ v , ξ w } ∩ { 0 , 1 } ≠ ∅ . \xi_u=\bot\Longrightarrow\{\xi_v,\xi_w\}\cap\{0,1\}\ne\varnothing. ξ u = ⊥ ⟹ { ξ v , ξ w } ∩ { 0 , 1 } = ∅ . Pure-Circuit asks for an assignment satisfying every gate.
Definition 5.2 (Weak Pure-Circuit and the input-once restriction). For δ ∈ [ 0 , 1 ] \delta\in[0,1] δ ∈ [ 0 , 1 ] , a weak δ \delta δ -Pure-Circuit solution fails at most δ ∣ G ∣ \delta|\mathcal{G}| δ ∣ G ∣ gates, counting each PURIFY gate once. The case δ = 0 \delta=0 δ = 0 is ordinary Pure-Circuit. An instance is input-once if every node is used as an input to exactly one gate.
By [6 Theorem 2.2] , PCP for PPAD is equivalent to PPAD-hardness of weak δ \delta δ -Pure-Circuit for some fixed δ > 0 \delta>0 δ > 0 , with or without the input-once restriction. We use input-once instances so that the resulting threshold graph has bounded degrees.
A threshold game, as in Definition 2.1 , is given by a finite nonempty directed graph G = ( V , E ) G=(V,E) G = ( V , E ) , with indegree h v ≤ 2 h_v\le2 h v ≤ 2 and outdegree 1 ≤ o v ≤ 2 1\le o_v\le2 1 ≤ o v ≤ 2 at each vertex. A threshold assignment is a vector z ∈ [ 0 , 1 ] V z\in[0,1]^V z ∈ [ 0 , 1 ] V . For a fixed κ > 0 \kappa>0 κ > 0 , the constraint at v v v is
∑ u : u → v z u > 1 2 + κ ⟹ z v ≤ κ , \sum_{u:u\to v}z_u>\frac{1}{2}+\kappa\Longrightarrow z_v\le\kappa, u : u → v ∑ z u > 2 1 + κ ⟹ z v ≤ κ ,
∑ u : u → v z u < 1 2 − κ ⟹ z v ≥ 1 − κ . \sum_{u:u\to v}z_u<\frac{1}{2}-\kappa\Longrightarrow z_v\ge1-\kappa. u : u → v ∑ z u < 2 1 − κ ⟹ z v ≥ 1 − κ .
If the incoming sum lies in [ 1 / 2 − κ , 1 / 2 + κ ] [1/2-\kappa,1/2+\kappa] [ 1/2 − κ , 1/2 + κ ] , any z v ∈ [ 0 , 1 ] z_v\in[0,1] z v ∈ [ 0 , 1 ] is permitted. An ordinary κ \kappa κ -threshold solution satisfies this constraint at every vertex, as in Definition 2.1 .
Definition 5.3 (Weak threshold solution). For fixed κ > 0 \kappa> 0 κ > 0 and 0 ≤ ρ ≤ 1 0 \le\rho\le1 0 ≤ ρ ≤ 1 , a ( κ , ρ ) (\kappa,\rho) ( κ , ρ ) -threshold solution is an assignment z ∈ [ 0 , 1 ] V z \in[0,1]^V z ∈ [ 0 , 1 ] V whose threshold constraint fails at at most ρ ∣ V ∣ \rho|V| ρ ∣ V ∣ vertices. The weak threshold search problem asks for such an assignment given G G G . For ρ = 0 \rho= 0 ρ = 0 , it is the ordinary threshold problem.
Fix κ = 1 / 200 \kappa= 1/200 κ = 1/200 . The failure fractions δ \delta δ and ρ \rho ρ count circuit gates and threshold vertices, respectively.
Given an input-once instance C = ( V C , G ) \mathcal{C} = (V_C,\mathcal{G}) C = ( V C , G ) , construct the threshold graph using the gadgets of [5 Theorem 4.23] :
Create one graph vertex for each node of V C V_C V C , keeping its label. A circuit node shared by gates is represented by one vertex.
For a NOR gate with inputs u , v u,v u , v and output w w w , add the edges u → w u \to w u → w and v → w v \to w v → w .
For a PURIFY gate with input u u u and outputs v , w v,w v , w , create four fresh vertices s 1 , s 2 , s 3 , s 4 s_1,s_2,s_3,s_4 s 1 , s 2 , s 3 , s 4 , private to that gate. Add
u → s 1 → s 2 → s 3 → v , s 2 → s 4 → w , u \to s_1 \to s_2 \to s_3 \to v,\qquad s_2 \to s_4 \to w, u → s 1 → s 2 → s 3 → v , s 2 → s 4 → w ,
There are no other vertices or edges. The gadgets are shown in Figure 3 .
Figure 3. The NOR and PURIFY threshold gadgets from the proof of [5 Theorem 4.23] , redrawn with our vertex labels. Solid blue circles are original circuit nodes; dashed orange circles are the four fresh vertices used for a PURIFY gate. Every arrow is a directed edge of the threshold graph. For NOR, u , v u,v u , v are the inputs and w w w is the output. For PURIFY, u u u is the input and v , w v,w v , w are the outputs. The curved edge is u → s 3 u \to s_3 u → s 3 . Only the edges contributed by the displayed gate are shown; the remaining incidences of original circuit nodes are omitted.
For a threshold assignment z z z , define
D κ ( s ) = { 0 , 0 ≤ s ≤ κ , 1 , 1 − κ ≤ s ≤ 1 , ⊥ , κ < s < 1 − κ . D_\kappa(s) =
\begin{cases}
0, & 0 \le s \le\kappa,\\
1, & 1-\kappa\le s \le1,\\
\perp, & \kappa< s < 1-\kappa.
\end{cases} D κ ( s ) = ⎩ ⎨ ⎧ 0 , 1 , ⊥ , 0 ≤ s ≤ κ , 1 − κ ≤ s ≤ 1 , κ < s < 1 − κ .
and return ξ u = D κ ( z u ) \xi_u = D_\kappa(z_u) ξ u = D κ ( z u ) for each original circuit node u ∈ V C u \in V_C u ∈ V C .
Lemma 5.4 (Weak threshold hardness). Assuming PCP for PPAD , there is a fixed rational ρ > 0 \rho> 0 ρ > 0 for which computing a ( κ , ρ ) (\kappa,\rho) ( κ , ρ ) -threshold solution is PPAD-hard, even with h v ≤ 2 h_v \le2 h v ≤ 2 and 1 ≤ o v ≤ 2 1 \le o_v \le2 1 ≤ o v ≤ 2 .
Proof. Under PCP for PPAD, fix δ > 0 \delta> 0 δ > 0 for which weak δ \delta δ -Pure-Circuit is hard on input-once instances [6 Theorem 2.2] . Let m = ∣ G ∣ m = |\mathcal{G}| m = ∣ G ∣ . The local correctness argument of [DFHM24, Theorem 4.23] applies because κ < 1 / 6 \kappa< 1/6 κ < 1/6 : a NOR gate is satisfied whenever its output vertex satisfies its threshold constraint; a PURIFY gate is satisfied whenever its four private vertices and two outputs satisfy theirs. No threshold constraint at an input vertex is needed for either conclusion.
Associate with each gate g g g the set T g T_g T g of its output vertices and private vertices. These sets partition the graph: each circuit node has one producing gate, and each additional vertex belongs to one gadget. A NOR gate contributes one vertex to its set and a PURIFY gate contributes six. Hence
∣ V ∣ = ∑ g ∈ G ∣ T g ∣ ≤ 6 m . |V| = \sum_{g \in\mathcal{G}} |T_g| \le6m. ∣ V ∣ = g ∈ G ∑ ∣ T g ∣ ≤ 6 m .
A failed decoded gate requires a failed threshold constraint in its own set T g T_g T g . Since the sets are disjoint, choose a positive rational ρ ≤ δ / 6 \rho\le\delta/6 ρ ≤ δ /6 to obtain
# { failed gates of C } ≤ # { failed threshold vertices } ≤ ρ ∣ V ∣ ≤ 6 ρ m ≤ δ m . \#\{\text{failed gates of }\mathcal{C}\} \le\#\{\text{failed threshold vertices}\} \le\rho|V| \le6\rho m \le\delta m. # { failed gates of C } ≤ # { failed threshold vertices } ≤ ρ ∣ V ∣ ≤ 6 ρ m ≤ δ m .
Thus every permitted threshold assignment decodes to a permitted circuit assignment.
Every original node is an output of one gate and an input to one gate. Its incoming edges belong to its producing gadget, and its outgoing edges to its consuming gadget. Inspection of the two gadgets gives h v ≤ 2 h_v \le2 h v ≤ 2 and 1 ≤ o v ≤ 2 1 \le o_v \le2 1 ≤ o v ≤ 2 , including at the private vertices. The graph and decoder have polynomial size and are computable in polynomial time.
From weak threshold games to HZ
Apply the construction of § 3 to a graph satisfying (2) , using the fixed reference tolerance τ a \tau_a τ a and a sufficiently large admissible K K K . As before, decode by
p v = min j ∈ H v p j , t v = p v − L w , z v = clip ( t v ) . p_v = \min_{j \in H_v} p_j,\qquad t_v = \frac{p_v-L}{w},\qquad z_v = \operatorname{clip}(t_v). p v = j ∈ H v min p j , t v = w p v − L , z v = clip ( t v ) .
At constant error, the bound W = O a ( N ε ) \mathcal{W} = O_a(N\varepsilon) W = O a ( N ε ) need not make total unapproved expenditure small. We instead use the price argument at vertices whose nearby groups receive little unapproved expenditure, and bound the number of remaining vertices. We first record the dependence of market size on K K K .
Lemma 5.5 (Market size). For sufficiently large admissible K K K and 0 < τ ≤ κ / 100 0 < \tau\le\kappa/100 0 < τ ≤ κ /100 , every nonempty n n n -vertex graph satisfying (2) gives
N = Θ a ( K n / η ) = Θ a ( K 2 n / τ ) . (21) N = \Theta_a(Kn/\eta) = \Theta_a(K^2n/\tau). \tag*{(21)} N = Θ a ( K n / η ) = Θ a ( K 2 n / τ ) . (21) For each fixed positive rational τ \tau τ depending only on a a a , there are positive rational ν a , M a \nu_a, M_a ν a , M a such that ν a K 2 n ≤ N ≤ M a K 2 n \nu_aK^2n \le N \le M_aK^2n ν a K 2 n ≤ N ≤ M a K 2 n throughout this range.
Proof. At every vertex, F v , c v = Θ a ( K ) F_v, c_v = \Theta_a(K) F v , c v = Θ a ( K ) . Equation (5) therefore gives reference supplies and anchor populations of size Θ a ( K / η ) \Theta_a(K/\eta) Θ a ( K / η ) . All remaining populations contribute O a ( K ) O_a(K) O a ( K ) per vertex. Summing the counts in (31) and using η = 2 τ / ( γ K ) \eta= 2\tau/(\gamma K) η = 2 τ / ( γ K ) proves (21) . For fixed τ \tau τ , choose positive rational lower and upper coefficients to obtain ν a \nu_a ν a and M a M_a M a .
Recall W v \mathcal{W}_v W v from Subsection 4.5. Let B 2 ( v ) B_2(v) B 2 ( v ) be the vertices at undirected distance at most two from v v v . The following local form of the decoding argument is proved in Appendix § 9 .§ 3 .
Lemma 5.6 (Local decoding). There are positive constants c a , K a c_a, K_a c a , K a , depending only on a a a , such that the following holds for admissible K ≥ K a K \ge K_a K ≥ K a , 0 < τ ≤ min { κ / 100 , c a κ } 0 < \tau\le\min\{\kappa/100,c_a\kappa\} 0 < τ ≤ min { κ /100 , c a κ } , ε ≤ c a κ 2 / K 2 \varepsilon\le c_a\kappa^2/K^2 ε ≤ c a κ 2 / K 2 , and ζ ≤ c a κ \zeta\le c_a\kappa ζ ≤ c a κ . For any normalized additive ε \varepsilon ε -equilibrium, if W u ≤ ζ \mathcal{W}_u \le\zeta W u ≤ ζ for every u ∈ B 2 ( v ) u \in B_2(v) u ∈ B 2 ( v ) , then
∑ u → v z u > 1 2 + κ ⟹ z v ≤ κ , \sum_{u\to v} z_u > \frac{1}{2}+\kappa\quad\Longrightarrow\quad z_v \le\kappa, u → v ∑ z u > 2 1 + κ ⟹ z v ≤ κ , ∑ u → v z u < 1 2 − κ ⟹ z v ≥ 1 − κ . \sum_{u\to v} z_u < \frac{1}{2}-\kappa\quad\Longrightarrow\quad z_v \ge1-\kappa. u → v ∑ z u < 2 1 − κ ⟹ z v ≥ 1 − κ . Only the modules in B 2 ( v ) B_2(v) B 2 ( v ) and their incident wire rows are used; no bound is required on prices at exterior endpoints.
The proof uses the same price relations, expenditure identities, and slack bounds as Lemma 4.10 . The preliminary price bounds at a vertex use only its own module; the price relations also use its incoming neighbors. Applying those relations at both endpoints of the wires incident to v v v requires only B 2 ( v ) B_2(v) B 2 ( v ) . Thus the argument needs small unapproved expenditure on this neighborhood, even if prices elsewhere are unrestricted.
Theorem 5.7 (Uniform robustness). For every fixed rational a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) , there are positive rational constants τ a ≤ κ / 100 \tau_a \le\kappa/100 τ a ≤ κ /100 , e a e_a e a , B a B_a B a , ν a \nu_a ν a , M a M_a M a , and an integer K a ≥ 1 K_a \ge1 K a ≥ 1 , depending only on a a a , such that the following holds. For every admissible K ≥ K a K \ge K_a K ≥ K a and every nonempty graph satisfying (2) , the market M ( G ; a , τ a , K ) \mathcal{M}(G;a,\tau_a,K) M ( G ; a , τ a , K ) , with η = τ a w \eta=\tau_a w η = τ a w , has ν a K 2 n ≤ N ≤ M a K 2 n \nu_a K^2n \le N \le M_aK^2n ν a K 2 n ≤ N ≤ M a K 2 n . For every 0 < ε ≤ e a / K 2 0 < \varepsilon\le e_a/K^2 0 < ε ≤ e a / K 2 , the minimum-price decoder applied to any normalized additive ε \varepsilon ε -equilibrium fails the κ \kappa κ -threshold condition at at most
vertices.
Proof. Choose the constants τ a \tau_a τ a , ζ a \zeta_a ζ a , e a e_a e a in Lemma 4.10 sufficiently small, and K a K_a K a sufficiently large, so that
τ a ≤ min { κ / 100 , c a κ } , ζ a ≤ c a κ , e a ≤ c a κ 2 , \tau_a \le\min\{\kappa/100,c_a\kappa\}, \qquad\zeta_a \le c_a\kappa, \qquad e_a \le c_a\kappa^2, τ a ≤ min { κ /100 , c a κ } , ζ a ≤ c a κ , e a ≤ c a κ 2 ,
where c a c_a c a is from Lemma 5.6 . These choices preserve all conclusions of Subsection 4.5. Lemma 5.5 gives the size bounds, using the same lower coefficient ν a \nu_a ν a and a sufficiently large upper coefficient M a M_a M a .
Since ∑ u W u ≤ W \sum_u \mathcal{W}_u \le\mathcal{W} ∑ u W u ≤ W , at most W / ζ a \mathcal{W}/\zeta_a W / ζ a vertices have W u > ζ a \mathcal{W}_u > \zeta_a W u > ζ a . The underlying undirected degree is at most four, so at most 21 21 21 vertices lie within distance two of any one of them. Every vertex outside these neighborhoods satisfies the hypothesis of Lemma 5.6 and decodes correctly. Lemma 4.9 therefore bounds the number of failures by
21 W ζ a ≤ 21 C a ζ a N ε . \frac{21\mathcal{W}}{\zeta_a} \le\frac{21C_a}{\zeta_a}N\varepsilon. ζ a 21 W ≤ ζ a 21 C a N ε .
Set B a = 21 C a / ζ a B_a=21C_a/\zeta_a B a = 21 C a / ζ a .
Proposition 5.8 (Forward reduction). There is a positive rational s a s_a s a , depending only on a a a , such that for every rational 0 < ρ ≤ 1 0 < \rho\le1 0 < ρ ≤ 1 and every sufficiently large admissible K K K , every normalized additive s a ρ / K 2 s_a\rho/K^2 s a ρ / K 2 -equilibrium of M ( G ; a , τ a , K ) \mathcal{M}(G;a,\tau_a,K) M ( G ; a , τ a , K ) decodes to a ( κ , ρ ) (\kappa,\rho) ( κ , ρ ) -threshold solution.
Proof. Let e a e_a e a , B a B_a B a , M a M_a M a be the constants in Theorem 5.7 and Lemma 5.5 . Choose a positive rational s a ≤ min { e a , 1 / ( B a M a ) } s_a \le\min\{e_a,1/(B_aM_a)\} s a ≤ min { e a , 1/ ( B a M a )} . For ε = s a ρ / K 2 \varepsilon= sa\rho/K^{2} ε = s a ρ / K 2 , uniform robustness applies because ε ≤ e a / K 2 \varepsilon\leq e_a/K^{2} ε ≤ e a / K 2 . Together with the market-size bound, it gives
# { failed threshold vertices } n ≤ B a N n ε ≤ B a M a K 2 ε = B a M a s a ρ ≤ ρ . \frac{\#\{\text{failed threshold vertices}\}}{n} \leq B_a\frac{N}{n}\varepsilon\leq B_aM_aK^{2}\varepsilon= B_aM_as_a\rho\leq\rho. n # { failed threshold vertices } ≤ B a n N ε ≤ B a M a K 2 ε = B a M a s a ρ ≤ ρ .
For fixed parameters the market has N = O a , K ( n ) N = O_{a,K}(n) N = O a , K ( n ) buyers and goods, so its explicit utility matrix has polynomial size. Construction and decoding use rational arithmetic of polynomial bit complexity.
Proof of Theorem 1.2 . Assume PCP for PPAD and choose a fixed rational 0 < ρ ≤ 1 0 < \rho\leq1 0 < ρ ≤ 1 for which the weak threshold problem is PPAD-hard, as supplied by Lemma 5.4 . Fix a sufficiently large admissible K K K and put ε 0 = s a ρ / K 2 > 0 \varepsilon_0 = sa\rho/K^{2} > 0 ε 0 = s a ρ / K 2 > 0 . Proposition 5.8 converts every ε 0 \varepsilon_0 ε 0 -equilibrium of the constructed market into a ( κ , ρ ) (\kappa,\rho) ( κ , ρ ) -threshold solution. The construction has polynomial size, and Lemma 4.11 gives totality and polynomial-length rational outputs. Every utility belongs to { 0 , a , 1 } \{0,a,1\} { 0 , a , 1 } , proving the theorem. A PTAS run at this fixed accuracy would solve the problem in polynomial time. Hence, assuming PCP for PPAD, this problem admits no PTAS unless PPAD ⊆ \subseteq ⊆ P.
Two common marginal slopes
Let B \mathcal{B} B be the set of buyers and G \mathcal{G} G the set of goods, with ∣ B ∣ = ∣ G ∣ = N |\mathcal{B}| = |\mathcal{G}| = N ∣ B ∣ = ∣ G ∣ = N . Budgets, supplies, and required bundle sizes are one, as in § 2 . Throughout this section, buyer indices i i i range over B \mathcal{B} B and good indices j j j range over G \mathcal{G} G , unless a smaller set is specified.
We prove Theorem 1.3 by giving a strongly polynomial-time algorithm for an exact normalized equilibrium with minimum-expenditure tie-breaking. We first state the search problem and reduce it to threshold utilities. We then describe the flow algorithm, prove its correctness, and bound its arithmetic operation count and intermediate encoding lengths.
Problem definition and normalization
Definition 6.1 (Two-slope HZ equilibrium). For each buyer i ∈ B i \in\mathcal{B} i ∈ B , the input specifies rational slopes c i ( 1 ) ≥ c i ( 2 ) ≥ 0 c_i^{(1)} \geq c_i^{(2)} \geq0 c i ( 1 ) ≥ c i ( 2 ) ≥ 0 and rational breakpoints τ i j ∈ [ 0 , 1 ] \tau_{ij} \in[0,1] τ ij ∈ [ 0 , 1 ] for every good j ∈ G j \in\mathcal{G} j ∈ G . The slopes are common across goods for a fixed buyer but may differ between buyers. Utilities are separable:
U i ( x i ) = ∑ j ∈ G f i j ( x i j ) , f i j ( t ) = c i ( 2 ) t + ( c i ( 1 ) − c i ( 2 ) ) min { t , τ i j } , 0 ≤ t ≤ 1. U_i(x_i) = \sum_{j\in\mathcal{G}} f_{ij}(x_{ij}), \qquad f_{ij}(t) = c_i^{(2)}t + \left(c_i^{(1)} - c_i^{(2)}\right)\min\{t,\tau_{ij}\}, \qquad0 \leq t \leq1. U i ( x i ) = j ∈ G ∑ f ij ( x ij ) , f ij ( t ) = c i ( 2 ) t + ( c i ( 1 ) − c i ( 2 ) ) min { t , τ ij } , 0 ≤ t ≤ 1. The problem is to compute an exact normalized HZ equilibrium with minimum-expenditure tie-breaking, as defined in § 2 . Here the demand value V i ( p ) V_i(p) V i ( p ) is given by OptBundle with objective U i ( y ) U_i(y) U i ( y ) in place of ∑ j u i j y j \sum_j u_{ij}y_j ∑ j u ij y j ; its budget, unit-quantity, and nonnegativity constraints are unchanged.
On a unit bundle, the utility in Definition 6.1 satisfies
U i ( x i ) = c i ( 2 ) + ( c i ( 1 ) − c i ( 2 ) ) ∑ j min { x i j , τ i j } . U_i(x_i) = c_i^{(2)} + \left(c_i^{(1)} - c_i^{(2)}\right)\sum_j \min\{x_{ij},\tau_{ij}\}. U i ( x i ) = c i ( 2 ) + ( c i ( 1 ) − c i ( 2 ) ) j ∑ min { x ij , τ ij } . If c i ( 1 ) > c i ( 2 ) c_i^{(1)} > c_i^{(2)} c i ( 1 ) > c i ( 2 ) , a positive affine normalization therefore preserves both utility-maximizing bundles and minimum-expenditure tie-breaking. If the slopes are equal, the buyer is indifferent among unit
Figure 4. A two-slope utility and its normalized threshold utility for the same buyer i i i , good j j j , and breakpoint τ i j \tau_{ij} τ ij . The left panel illustrates c i ( 1 ) > c i ( 2 ) > 0 c_i^{(1)} > c_i^{(2)} > 0 c i ( 1 ) > c i ( 2 ) > 0 . For c i ( 1 ) > c i ( 2 ) c_i^{(1)} > c_i^{(2)} c i ( 1 ) > c i ( 2 ) , subtracting c i ( 2 ) t c_i^{(2)}t c i ( 2 ) t and dividing by c i ( 1 ) − c i ( 2 ) c_i^{(1)} - c_i^{(2)} c i ( 1 ) − c i ( 2 ) gives f ~ i j ( t ) = min { t , τ i j } \widetilde{f}_{ij}(t) = \min\{t,\tau_{ij}\} f ij ( t ) = min { t , τ ij } , shown on the right with slope one (a 45-degree segment) followed by slope zero. On unit bundles this induces a positive affine transformation of the buyer’s total utility.
bundles; we represent her by replacing her entire threshold row with zeros. Hence it suffices to solve the problem for the normalized threshold utilities
U i ( x i ) = ∑ j min { x i j , τ i j } . (22) U_i(x_i) = \sum_j \min\{x_{ij},\tau_{ij}\}. \tag*{(22)} U i ( x i ) = j ∑ min { x ij , τ ij } . (22)
Throughout the two-slope analysis, U i U_i U i and τ i j \tau_{ij} τ ij denote these normalized utilities and thresholds.
Each of the first τ i j \tau_{ij} τ ij units of good j j j contributes one unit of utility per unit of quantity to buyer i i i ; additional units contribute no utility. We call the former quantities useful . The algorithm assigns useful quantities in increasing order of price, then fills any remaining bundle deficits with free goods. For thresholds in { 0 , 1 } \{0,1\} { 0 , 1 } , receiving a positive threshold fills the buyer’s bundle; this is the bivalued case treated by [17 Section 4] . With fractional thresholds, a buyer may continue through several price levels, so the algorithm must track both her remaining budget and her remaining quantity.
The flow algorithm
State and invariant. Let J ⊆ G \mathcal{J} \subseteq\mathcal{G} J ⊆ G be the goods whose prices have not yet been assigned. These goods are still unallocated; trial flows will not change the current allocation x x x . Define each buyer’s remaining budget and quantity by
B i = 1 − ∑ j ∈ G ∖ J p j x i j , R i = 1 − ∑ j ∈ G x i j , B_i = 1 - \sum_{j\in\mathcal{G}\setminus\mathcal{J}} p_jx_{ij}, \qquad R_i = 1 - \sum_{j\in\mathcal{G}} x_{ij}, B i = 1 − j ∈ G ∖ J ∑ p j x ij , R i = 1 − j ∈ G ∑ x ij ,
and let
I = { i ∈ B : B i > 0 and R i > 0 } \mathcal{I} = \{i \in\mathcal{B} : B_i > 0 \text{ and } R_i > 0\} I = { i ∈ B : B i > 0 and R i > 0 }
be the active buyers. Initially, x = 0 x = 0 x = 0 , B i = R i = 1 B_i = R_i = 1 B i = R i = 1 , and I = B \mathcal{I} = \mathcal{B} I = B , J = G \mathcal{J} = \mathcal{G} J = G . We update I \mathcal{I} I after committing each price group, using the updated budgets and quantities.
Before the final completion step, we maintain x i j ≤ τ i j x_{ij} \le\tau_{ij} x ij ≤ τ ij and the invariant
x i j = τ i j for every i ∈ I and every j ∈ G ∖ J . (23) x_{ij} = \tau_{ij} \quad\text{for every } i \in\mathcal{I} \text{ and every } j \in\mathcal{G} \setminus\mathcal{J}. \tag*{(23)} x ij = τ ij for every i ∈ I and every j ∈ G ∖ J . (23)
Thus an active buyer has already received every useful unit available to her at earlier prices. Every good assigned a positive price is allocated in full. Any unused supply of free goods is reserved for completion.
The expenditure network. For λ > 0 \lambda> 0 λ > 0 , form a network F ( λ ) \mathcal{F}(\lambda) F ( λ ) with source s s s , sink t t t , goods j ∈ J j \in\mathcal{J} j ∈ J , and buyers i ∈ I i \in\mathcal{I} i ∈ I . Its capacities are
s → j : λ , j → i : λ τ i j , i → t : min { B i , λ R i } . \begin{aligned}
s \to j &:\ \lambda,\\
j \to i &:\ \lambda\tau_{ij},\\
i \to t &:\ \min\{B_i,\lambda R_i\}.
\end{aligned} s → j j → i i → t : λ , : λ τ ij , : min { B i , λ R i } .
Every ordinary maximum-flow computation below starts from zero and uses shortest augmenting paths, found by breadth-first search.
Write w i j w_{ij} w ij for the flow on j → i j \to i j → i , keeping the buyer-first indexing used in x i j x_{ij} x ij and τ i j \tau_{ij} τ ij . It represents expenditure, so the corresponding quantity is w i j / λ w_{ij}/\lambda w ij / λ . The three arc types enforce supply, useful-quantity limits, and the buyer’s budget and bundle-size limits, respectively. We set w i j = 0 w_{ij} = 0 w ij = 0 for buyers outside I \mathcal{I} I when referring to a full flow matrix.
Figure 5. The expenditure network F ( λ ) \mathcal{F}(\lambda) F ( λ ) . Solid blue ellipses denote unpriced goods, and dashed orange ellipses denote active buyers. Labels above the highlighted arcs give their capacities; lighter arcs have the corresponding capacities for their endpoints. A flow w i j w_{ij} w ij on j → i j \to i j → i represents expenditure and allocates w i j / λ w_{ij}/\lambda w ij / λ units of good j j j to buyer i i i . The original indices 1 , … , N 1,\ldots,N 1 , … , N are shown schematically; each stage retains only goods in J \mathcal{J} J and buyers in I \mathcal{I} I .
In the residual network, unused capacity gives a forward arc and positive flow gives a reverse arc. A good is closed if it has no residual path to t t t . Closed goods may still have individual residual arcs. To find them, reverse all residual arcs, search from t t t , and select the goods not reached by the search. The pseudocode denotes this operation by ClosedGoods .
Selecting a positive price. All remaining goods can be allocated usefully at a common price λ \lambda λ if and only if the maximum flow has value λ ∣ J ∣ \lambda|\mathcal{J}| λ ∣ J ∣ . For reference, the largest such price is characterized by
max λ , w λ subject to ∑ i ∈ I w i j = λ for j ∈ J , ∑ j ∈ J w i j ≤ B i for i ∈ I , ∑ j ∈ J w i j ≤ λ R i for i ∈ I , 0 ≤ w i j ≤ λ τ i j for i ∈ I , j ∈ J , λ ≥ 0. (24) \begin{aligned}
\max_{\lambda,w}\quad& \lambda\\
\text{subject to}\quad& \sum_{i\in\mathcal{I}} w_{ij}=\lambda&& \text{for }j\in\mathcal{J},\\
& \sum_{j\in\mathcal{J}} w_{ij}\le B_i && \text{for }i\in\mathcal{I},\\
& \sum_{j\in\mathcal{J}} w_{ij}\le\lambda R_i && \text{for }i\in\mathcal{I},\\
& 0\le w_{ij}\le\lambda\tau_{ij} && \text{for }i\in\mathcal{I},\ j\in\mathcal{J},\\
& \lambda\ge0. \tag*{(24)}
\end{aligned} λ , w max subject to λ i ∈ I ∑ w ij = λ j ∈ J ∑ w ij ≤ B i j ∈ J ∑ w ij ≤ λ R i 0 ≤ w ij ≤ λ τ ij λ ≥ 0. for j ∈ J , for i ∈ I , for i ∈ I , for i ∈ I , j ∈ J , (24)
We compute this optimum without invoking a linear-programming algorithm, using the parametric maximum-flow algorithm of Gallo, Grigoriadis, and Tarjan [8 ] . We commit only the closed goods of the returned expenditure flow. Buyers who remain active receive their full thresholds on those goods, preserving (23) ; the other trial allocations are discarded. The correctness proof shows that the closed set is nonempty and that the next price is strictly larger.
The price-finding network. For ϑ ≥ 0 \vartheta\ge0 ϑ ≥ 0 , form a quantity network Q ( ϑ ) Q(\vartheta) Q ( ϑ ) with source s s s , sink t t t , two vertices i − , i + i^{-},i^{+} i − , i + for each i ∈ I i\in\mathcal{I} i ∈ I , and one vertex for each j ∈ J j\in\mathcal{J} j ∈ J . Its arcs and capacities are
s → i − : B i ϑ , i − → i + : R i , i + → j : τ i j , j → t : 1. (25) \begin{aligned}
s\to i^{-}&: B_i\vartheta,\\
i^{-}\to i^{+}&: R_i,\\
i^{+}\to j&: \tau_{ij},\\
j\to t&: 1. \tag*{(25)}
\end{aligned} s → i − i − → i + i + → j j → t : B i ϑ , : R i , : τ ij , : 1. (25)
Only the source capacities depend on ϑ \vartheta ϑ ; the active sets, budgets, and remaining quantities stay fixed during a price search. The two consecutive buyer arcs enforce both affordability and the remaining quantity limit. Figure 6 illustrates this auxiliary network.
Figure 6. The quantity network Q ( ϑ ) Q(\vartheta) Q ( ϑ ) for price selection, with ϑ = 1 / λ \vartheta=1/\lambda ϑ = 1/ λ . Each active buyer is split into two orange vertices; blue vertices represent unpriced goods. Highlighted arcs are labeled with their capacities, and only B i ϑ B_i\vartheta B i ϑ varies during the search. The smallest ϑ \vartheta ϑ permitting flow ∣ J ∣ |\mathcal{J}| ∣ J ∣ gives the largest feasible price λ = 1 / ϑ \lambda=1/\vartheta λ = 1/ ϑ .
Lemma 6.2 (Strongly polynomial price selection). Suppose J ≠ ∅ \mathcal{J} \ne\varnothing J = ∅ and a positive price is feasible in (24). Its optimum and a corresponding expenditure flow can be computed by one call to the GGT parametric maximum-flow algorithm and one ordinary maximum-flow computation, using a number of arithmetic operations polynomial in N N N and independent of the numerical data.
Proof. Fix the active sets, budgets, and remaining quantities for this stage, and put k = ∣ J ∣ k = \lvert\mathcal{J}\rvert k = ∣ J ∣ . For ϑ > 0 \vartheta> 0 ϑ > 0 , a flow of value k k k in Q ( ϑ ) Q(\vartheta) Q ( ϑ ) saturates every arc j → t j \to t j → t . Writing q i j q_{ij} q ij for its flow on i + → j i^+ \to j i + → j , we have
∑ i q i j = 1 , ∑ j q i j ≤ min { B i ϑ , R i } , 0 ≤ q i j ≤ τ i j . \sum_i q_{ij} = 1,\qquad\sum_j q_{ij} \le\min\{B_i\vartheta, R_i\},\qquad0 \le q_{ij} \le\tau_{ij}. i ∑ q ij = 1 , j ∑ q ij ≤ min { B i ϑ , R i } , 0 ≤ q ij ≤ τ ij . Thus λ = 1 / ϑ \lambda= 1/\vartheta λ = 1/ ϑ and w i j = λ q i j w_{ij} = \lambda q_{ij} w ij = λ q ij give a feasible expenditure flow at price λ \lambda λ . Conversely, dividing a feasible expenditure flow by λ \lambda λ gives a value-k k k flow in Q ( 1 / λ ) Q(1/\lambda) Q ( 1/ λ ) .
Let F ( ϑ ) F(\vartheta) F ( ϑ ) be the maximum-flow value of Q ( ϑ ) Q(\vartheta) Q ( ϑ ) , and put T = max i ∈ I R i / B i T = \max_{i\in I} R_i/B_i T = max i ∈ I R i / B i . At ϑ = T \vartheta= T ϑ = T , each source capacity is at least the following quantity capacity, so the budget arcs impose no additional restriction. Positive-price feasibility therefore implies F ( T ) = k F(T) = k F ( T ) = k , whereas F ( 0 ) = 0 F(0) = 0 F ( 0 ) = 0 . By max-flow/min-cut, F F F is the minimum of finitely many affine cut-capacity functions, and hence is continuous and piecewise linear. It is nondecreasing and bounded above by k k k . Consequently,
ϑ ∗ = min { ϑ ∈ [ 0 , T ] : F ( ϑ ) = k } , λ ∗ = 1 / ϑ ∗ \vartheta_* = \min\{\vartheta\in[0,T] : F(\vartheta) = k\},\qquad\lambda_* = 1/\vartheta_* ϑ ∗ = min { ϑ ∈ [ 0 , T ] : F ( ϑ ) = k } , λ ∗ = 1/ ϑ ∗ are well-defined, and the total source capacity gives ϑ ∗ ≥ k / ∑ i B i > 0 \vartheta_* \ge k/\sum_i B_i > 0 ϑ ∗ ≥ k / ∑ i B i > 0 .
The capacities leaving the source are nondecreasing affine functions of ϑ \vartheta ϑ , while all other capacities are constant. These are the hypotheses of the GGT breakpoint algorithm (Theorem 3.1 of their paper). It computes the breakpoints and linear pieces of F F F on [ 0 , T ] [0,T] [ 0 , T ] in strongly polynomial time, and hence the first parameter ϑ ∗ \vartheta_* ϑ ∗ for which F = k F = k F = k . The network has O ( N ) O(N) O ( N ) vertices and O ( N 2 ) O(N^2) O ( N 2 ) arcs. Finally, compute an ordinary maximum flow q q q from zero in Q ( ϑ ∗ ) Q(\vartheta_*) Q ( ϑ ∗ ) and return λ = 1 / ϑ ∗ \lambda= 1/\vartheta_* λ = 1/ ϑ ∗ and w i j = λ q i j w_{ij} = \lambda q_{ij} w ij = λ q ij . This returned w w w is a maximum flow of value λ k \lambda k λk in the original expenditure network F ( λ ) \mathcal{F}(\lambda) F ( λ ) .
We denote this procedure by Price ( I , J , B , R ) \operatorname{Price}(I,\mathcal{J},B,R) Price ( I , J , B , R ) . The goods to commit are determined by residual reachability in F ( λ ) \mathcal{F}(\lambda) F ( λ ) using the returned expenditure flow, not by cuts of Q ( ϑ ) Q(\vartheta) Q ( ϑ ) .
Algorithm 1. Strongly polynomial equilibrium for threshold utilities
Input: Rational thresholds τ i j ∈ [ 0 , 1 ] \tau_{ij} \in[0,1] τ ij ∈ [ 0 , 1 ] for i ∈ B i \in\mathcal{B} i ∈ B , j ∈ G j \in\mathcal{G} j ∈ G .
Output: A normalized equilibrium ( x , p ) (x,p) ( x , p ) with minimum-expenditure tie-breaking.
Initialize x ← 0 x \leftarrow0 x ← 0 , I ← B \mathcal{I} \leftarrow\mathcal{B} I ← B , and J ← G \mathcal{J} \leftarrow\mathcal{G} J ← G . Set B i ← 1 B_i \leftarrow1 B i ← 1 and R i ← 1 R_i \leftarrow1 R i ← 1 for every buyer i ∈ B i \in\mathcal{B} i ∈ B .
Phase 1: allocate free goods. (a) Compute a maximum flow w w w in the initial quantity network F ( 1 ) \mathcal{F}(1) F ( 1 ) . (b) Let S 0 S_0 S 0 be its closed goods. (c) Assign p j ← 0 p_j \leftarrow0 p j ← 0 and x i j ← w i j x_{ij} \leftarrow w_{ij} x ij ← w ij for j ∈ S 0 j \in S_0 j ∈ S 0 , i ∈ B i \in\mathcal{B} i ∈ B . (d) Update R i ← R i − ∑ j ∈ S 0 x i j R_i \leftarrow R_i - \sum_{j \in S_0} x_{ij} R i ← R i − ∑ j ∈ S 0 x ij for each buyer; budgets are unchanged. (e) Remove S 0 S_0 S 0 from J \mathcal{J} J and update the active buyers I \mathcal{I} I .
Phase 2: allocate goods at increasing positive prices. (a) While J ≠ ∅ \mathcal{J} \ne\varnothing J = ∅ , do: i. Compute ( λ , w ) ← Price ( I , J , B , R ) (\lambda,w) \leftarrow\operatorname{Price}(\mathcal{I},\mathcal{J},B,R) ( λ , w ) ← Price ( I , J , B , R ) using Lemma 6.2 . ii. Let S S S be the closed goods of this flow in F ( λ ) \mathcal{F}(\lambda) F ( λ ) . iii. Assign p j ← λ p_j \leftarrow\lambda p j ← λ and x i j ← w i j / λ x_{ij} \leftarrow w_{ij}/\lambda x ij ← w ij / λ for j ∈ S j \in S j ∈ S , i ∈ I i \in\mathcal{I} i ∈ I . iv. Let d i = ∑ j ∈ S x i j d_i = \sum_{j \in S} x_{ij} d i = ∑ j ∈ S x ij for each active buyer i i i . v. Update ( B i , R i ) ← ( B i − λ d i , R i − d i ) (B_i,R_i) \leftarrow(B_i-\lambda d_i,R_i-d_i) ( B i , R i ) ← ( B i − λ d i , R i − d i ) for each active buyer. vi. Remove S S S from J \mathcal{J} J and update the active buyers I \mathcal{I} I . vii. Discard the trial allocations on goods outside S S S .
Phase 3: fill the remaining bundles. Use the unused supply of S 0 S_0 S 0 to fill all remaining bundle deficits, including those of buyers whose budgets are exhausted.
Return ( x , p ) (x,p) ( x , p ) .
The free stage leaves all budgets equal to one. In the positive-price loop, each update uses the active set from the start of that stage; we recompute the active set only after committing the group. In the completion phase, we include all buyers with a quantity deficit, even if their budgets are exhausted. Lemma 6.7 shows that free supply is sufficient and that these final quantities change neither utility nor expenditure.
Correctness
We first prove feasibility and progress of the price stages. We then show that completion preserves utility and expenditure, and establish optimal demand with minimum-expenditure tie-breaking.
Feasibility and progress
We first record the residual-network property that determines which allocations can be fixed at a given price.
Lemma 6.3 (Closed goods). Let S S S be the closed goods of a maximum flow in F ( λ ) \mathcal{F}(\lambda) F ( λ ) . Every good outside S S S has a saturated arc from s s s . For each active buyer i ∈ I i \in\mathcal{I} i ∈ I , at least one of the following holds:
every arc j → i j \to i j → i with j ∈ S j \in S j ∈ S is saturated;
the arc i → t i \to t i → t is saturated, and all positive flow into i i i comes from S S S .
Proof. An unsaturated arc s → j s \to j s → j with j ∉ S j \notin S j ∈ / S could be followed by a residual path from j j j to t t t , contradicting maximality. Now suppose some arc j → i j \to i j → i with j ∈ S j \in S j ∈ S is unsaturated. The buyer i i i cannot reach t t t in the residual network, since then j j j could also reach t t t . In particular, i → t i \to t i → t is saturated. If i i i received positive flow from k ∉ S k \notin S k ∈ / S , the reverse arc i → k i \to k i → k followed by a residual path from k k k to t t t would give the same contradiction. Thus all her inflow comes from S S S . □
Lemma 6.4 (Largest feasible price). Suppose J ≠ ∅ \mathcal{J} \ne\varnothing J = ∅ and (24) is feasible at some positive price. It has a finite positive optimum. Every optimal flow saturates all source arcs and has a nonempty set of closed goods. Moreover, if a feasible positive price admits a flow with no closed goods, then a strictly larger price is feasible.
Proof. The budget constraints give λ ∣ J ∣ ≤ ∑ i ∈ I B i ≤ N \lambda|\mathcal{J}| \le\sum_{i\in I} B_i \le N λ ∣ J ∣ ≤ ∑ i ∈ I B i ≤ N . Both λ \lambda λ and all w i j w_{ij} w ij are therefore bounded. The feasible region is closed and nonempty, so an optimum exists and is positive. The good equalities saturate every source arc, making the corresponding flow a maximum flow of value λ ∣ J ∣ \lambda|\mathcal{J}| λ ∣ J ∣ .
For the final assertion, consider such a flow at price λ 0 > 0 \lambda_0 > 0 λ 0 > 0 . If every good has a residual path to t t t , then every cut with a good on its source side has positive residual capacity and hence capacity strictly greater than λ 0 ∣ J ∣ \lambda_0|\mathcal{J}| λ 0 ∣ J ∣ . There are finitely many cuts, and their capacities depend continuously on λ \lambda λ . These inequalities remain strict after a sufficiently small increase in λ \lambda λ . A cut with no goods on its source side contains all source arcs, so its capacity is at least λ ∣ J ∣ \lambda|\mathcal{J}| λ ∣ J ∣ at every price. Max-flow/min-cut therefore gives a larger feasible price. At an optimum this is impossible, proving that a closed good exists. □
Lemma 6.5 (The free stage). The set S 0 S_0 S 0 is nonempty. After the free stage, every buyer with R i > 0 R_i > 0 R i > 0 has received τ i j \tau_{ij} τ ij units of each j ∈ S 0 j \in S_0 j ∈ S 0 . If any goods remain, the first positive-price stage is feasible at one and has optimum strictly greater than one.
Proof. The sink capacity of every buyer in F ( 1 ) \mathcal{F}(1) F ( 1 ) is one. Lemma 6.3 implies that each buyer receives either all her thresholds on S 0 S_0 S 0 or one useful unit entirely from S 0 S_0 S 0 . In the second case R i = 0 R_i = 0 R i = 0 , so the invariant holds.
If the maximum-flow value is less than N N N , some source arc is unsaturated, and its good belongs to S 0 S_0 S 0 by Lemma 6.3. If the value is N N N , all sink arcs are saturated and no good can reach t t t . Thus S 0 S_0 S 0 is nonempty in either case.
Restrict the flow to the remaining goods. Their source arcs are saturated. A buyer receiving d i d_i d i free units retains inflow at most 1 − d i = R i 1-d_i = R_i 1 − d i = R i and budget one, so the restricted flow is feasible at price one. Buyers with R i = 0 R_i = 0 R i = 0 have no remaining inflow and can be deleted.
Every remaining good also retains a residual path to t t t . Its old path avoids closed goods and s s s , since neither could reach t t t . It avoids deleted buyers as well: their entire inflow came from S 0 S_0 S 0 and their sink arcs were saturated. For a retained buyer, both sink capacity and sink flow decrease by d i d_i d i , preserving forward residual capacity. All other arcs on the path are unchanged. Lemma 6.4 now gives a feasible price greater than one. □
Lemma 6.6 (Committing a positive-price group). At each positive-price stage, S S S is nonempty and every good in S S S is allocated in full. Every buyer who remains active receives her full threshold from each good in S S S . If goods remain, the next positive-price stage is feasible and has a strictly larger optimum. There are at most N N N positive-price stages.
Proof. The first stage is feasible by Lemma 6.5. At any feasible stage, Lemma 6.4 gives a nonempty closed set and saturated source arcs. Dividing their flows by λ \lambda λ allocates each good in S S S in full.
If a buyer does not receive all her thresholds on S S S , Lemma 6.3 gives
λ d i = min { B i , λ R i } . (26) \lambda d_i = \min\{B_i,\lambda R_i\}. \tag*{(26)} λ d i = min { B i , λ R i } . (26)
Her budget or quantity is exhausted. She leaves the active set, and every buyer who remains satisfies the invariant.
Restrict the flow to the remaining goods. At price λ \lambda λ , each buyer’s sink flow decreases by λ d i \lambda d_i λ d i , exactly the decrease in her sink capacity:
min { B i − λ d i , λ ( R i − d i ) } = min { B i , λ R i } − λ d i . \min\{B_i-\lambda d_i,\lambda(R_i-d_i)\}=\min\{B_i,\lambda R_i\}-\lambda d_i. min { B i − λ d i , λ ( R i − d i )} = min { B i , λ R i } − λ d i .
Thus the restricted flow is feasible and saturates all remaining source arcs. Deleted buyers have zero remaining capacity and inflow.
To obtain a strict price increase, take an old residual path from a remaining good to t t t . It cannot enter a closed good. It also cannot pass through s s s , whose source arcs are all saturated. For a deleted buyer, λ d i \lambda d_i λ d i equals her old sink capacity; hence all her inflow came from S S S and her sink arc was saturated. Such a buyer had no residual path to t t t , so the old path avoids her. At retained buyers, the equal decreases in sink capacity and flow preserve forward residual capacity, and every other arc on the path is unchanged. All remaining goods can therefore still reach t t t . Lemma 6.4 gives a strictly larger feasible price, completing the induction. Each stage removes at least one good, so there are at most N N N stages.
Completion and optimal demand
Lemma 6.7 (Completing the bundles). The completion step clears every good and fills every unit bundle without changing utility or expenditure. The resulting allocation respects all budgets, and prices are normalized.
Proof. Every allocation before completion respects the remaining budgets and quantities. All goods outside S 0 S_0 S 0 are allocated in full. Since both total supply and total required quantity are N N N , the unused supply in S 0 S_0 S 0 equals ∑ i R i \sum_i R_i ∑ i R i . The greedy procedure therefore exhausts all remaining supply and all deficits, preserving nonnegativity and satisfying every row and column constraint.
A buyer with a remaining deficit also had a deficit after the free stage. By Lemma 6.5, she has already received her full threshold on each good of S 0 S_0 S 0 . Additional quantities from these goods have zero marginal utility and zero cost, including for buyers whose budgets have been exhausted. Finally, S 0 S_0 S 0 is nonempty and has price zero, so the prices are normalized.
Lemma 6.8 (Optimal demand and expenditure). Every buyer’s final allocation is a minimum-expenditure bundle among her utility-maximizing affordable unit bundles.
Proof. First consider a buyer who leaves the active set at a positive price P P P . She has received every threshold below P P P , receives no goods above P P P , and pays only for useful quantities. Completion adds only free quantities and preserves these properties.
For an alternative unit bundle y i y_i y i , write z j = min { y i j , τ i j } z_j=\min\{y_{ij},\tau_{ij}\} z j = min { y ij , τ ij } and z ˉ j = min { x i j , τ i j } \bar z_j=\min\{x_{ij},\tau_{ij}\} z ˉ j = min { x ij , τ ij } . Below P P P we have z ˉ j = τ i j \bar z_j=\tau_{ij} z ˉ j = τ ij and z j − z ˉ j ≤ 0 z_j-\bar z_j\le0 z j − z ˉ j ≤ 0 ; above P P P we have z ˉ j = 0 \bar z_j=0 z ˉ j = 0 and z j − z ˉ j ≥ 0 z_j-\bar z_j\ge0 z j − z ˉ j ≥ 0 . Including goods at price P P P , we obtain in every case
p j ( z j − z ˉ j ) ≥ P ( z j − z ˉ j ) . p_j(z_j-\bar z_j)\ge P(z_j-\bar z_j). p j ( z j − z ˉ j ) ≥ P ( z j − z ˉ j ) .
Since p ⋅ y i ≥ ∑ j p j z j p\cdot y_i\ge\sum_j p_jz_j p ⋅ y i ≥ ∑ j p j z j and p ⋅ x i = ∑ j p j z ˉ j p\cdot x_i=\sum_jp_j\bar z_j p ⋅ x i = ∑ j p j z ˉ j , summation gives
p ⋅ y i − p ⋅ x i ≥ P ( U i ( y i ) − U i ( x i ) ) . (27) p\cdot y_i-p\cdot x_i\ge P\bigl(U_i(y_i)-U_i(x_i)\bigr). \tag*{(27)} p ⋅ y i − p ⋅ x i ≥ P ( U i ( y i ) − U i ( x i ) ) . (27)
If her budget was exhausted, p ⋅ x i = 1 p\cdot x_i=1 p ⋅ x i = 1 , and any strict utility improvement would cost more than one. If her quantity was exhausted, she already has utility one, the maximum possible on a unit bundle. In either case she is optimal, and (27) excludes a cheaper bundle of equal utility. A buyer who fills her useful bundle in the free stage has utility one at zero cost. Finally, consider a buyer still active when all prices have been assigned. The invariant gives her every threshold, so her utility is ∑ j τ i j \sum_j \tau_{ij} ∑ j τ ij . This is the largest possible utility, and any bundle attaining it must contain at least τ i j \tau_{ij} τ ij of every good, at cost at least ∑ j p j τ i j \sum_j p_j\tau_{ij} ∑ j p j τ ij . Her allocation has exactly this cost, because completion adds only free goods. This includes all-zero threshold rows and thus the originally indifferent buyers.
Encoding lengths and strongly polynomial running time
The stage prices depend on budgets obtained at earlier stages. To bound their encoding lengths, we use the invariant to express the surviving buyers’ allocations in terms of the input thresholds. We also bound all trial parameters and flow data used by the parametric price finder.
Lemma 6.9 (Polynomial encoding lengths). All trial parameters, capacities, flows, prices, remaining budgets and quantities, and final allocations can be computed with encoding length polynomial in the binary input length.
Proof. Let Q Q Q be the product of the input threshold denominators, so log Q \log Q log Q is at most the binary input length. An active buyer has received her exact threshold on every previously allocated good. Her remaining quantity therefore has denominator dividing Q Q Q .
We first express an optimal stage price using a tight cut. For S ⊆ J S \subseteq\mathcal{J} S ⊆ J and i ∈ I i \in\mathcal{I} i ∈ I , put h i ( S ) = min { R i , ∑ j ∈ S τ i j } h_i(S) = \min\{R_i,\sum_{j\in S}\tau_{ij}\} h i ( S ) = min { R i , ∑ j ∈ S τ ij } . A cut whose source-side goods are exactly S S S pays λ ( ∣ J ∣ − ∣ S ∣ ) \lambda(|\mathcal{J}|-|S|) λ ( ∣ J ∣ − ∣ S ∣ ) for source arcs. Placing buyer i i i on the source side adds min { B i , λ R i } \min\{B_i,\lambda R_i\} min { B i , λ R i } ; placing her on the sink side adds λ ∑ j ∈ S τ i j \lambda\sum_{j\in S}\tau_{ij} λ ∑ j ∈ S τ ij . Minimizing independently over buyers and applying max-flow/min-cut shows that a positive price is feasible exactly when
∑ i ∈ I min { B i / λ , h i ( S ) } ≥ ∣ S ∣ for every S ⊆ J . (28) \sum_{i\in\mathcal{I}} \min\{B_i/\lambda,h_i(S)\} \ge|S| \qquad\text{for every } S \subseteq\mathcal{J}. \tag*{(28)} i ∈ I ∑ min { B i / λ , h i ( S )} ≥ ∣ S ∣ for every S ⊆ J . (28)
At the optimum λ ∗ \lambda_* λ ∗ , some inequality in (28) is tight and becomes false immediately to its right. Indeed, there are finitely many sets S S S , their left sides are continuous and nonincreasing, and every larger price violates at least one inequality. Fix such a set. Let A ⊆ I A \subseteq\mathcal{I} A ⊆ I consist of the buyers whose minimum is B i / λ B_i/\lambda B i / λ immediately to the right of λ ∗ \lambda_* λ ∗ , including those whose terms tie at λ ∗ \lambda_* λ ∗ . The set A A A is nonempty, since otherwise the left side would remain constant. Tightness gives
λ ∗ = ∑ i ∈ A B i ∣ S ∣ − ∑ i ∈ I ∖ A h i ( S ) . \lambda_* = \frac{\sum_{i\in A} B_i}{|S|-\sum_{i\in\mathcal{I}\setminus A}h_i(S)}. λ ∗ = ∣ S ∣ − ∑ i ∈ I ∖ A h i ( S ) ∑ i ∈ A B i .
Each h i ( S ) h_i(S) h i ( S ) has denominator dividing Q Q Q . The denominator of this ratio equals ∑ i ∈ A B i / λ ∗ > 0 \sum_{i\in A}B_i/\lambda_*>0 ∑ i ∈ A B i / λ ∗ > 0 and is at most ∣ S ∣ ≤ N |S|\le N ∣ S ∣ ≤ N . Thus
d = Q ( ∣ S ∣ − ∑ i ∈ I ∖ A h i ( S ) ) d=Q\left(|S|-\sum_{i\in\mathcal{I}\setminus A}h_i(S)\right) d = Q ∣ S ∣ − i ∈ I ∖ A ∑ h i ( S )
is an integer with 1 ≤ d ≤ N Q 1\le d\le NQ 1 ≤ d ≤ N Q .
Suppose the active budgets share denominator E E E , and write ∑ i ∈ A B i = M / E \sum_{i\in A}B_i=M/E ∑ i ∈ A B i = M / E . Then λ ∗ = Q M / ( E d ) \lambda_*=QM/(Ed) λ ∗ = QM / ( E d ) . By the invariant, a surviving buyer receives T i / Q T_i/Q T i / Q in this stage for some integer T i T_i T i . If her old budget was m i / E m_i/E m i / E , her new budget is
m i E − Q M E d T i Q = m i d − M T i E d . \frac{m_i}{E}-\frac{QM}{Ed}\frac{T_i}{Q}=\frac{m_i d-MT_i}{Ed}. E m i − E d QM Q T i = E d m i d − M T i .
The surviving budgets therefore share denominator E d Ed E d . Starting from E = 1 E = 1 E = 1 , at most N N N stages give log E ≤ N log ( N Q ) \log E \le N \log(NQ) log E ≤ N log ( N Q ) . Budgets lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] and prices in [ 0 , N ] [0,N] [ 0 , N ] , so their numerators also have polynomial bit length. All data for each subsequent price search consequently have polynomial encoding length.
We next bound the intermediate numbers used within a GGT call. For a source-side cut X X X in Q ( ϑ ) Q(\vartheta) Q ( ϑ ) , write
c ϑ ( X ) = a X ϑ + b X , a X = M X E , b X = H X Q . c_{\vartheta}(X) = a_X\vartheta+ b_X,\qquad a_X = \frac{M_X}{E},\qquad b_X = \frac{H_X}{Q}. c ϑ ( X ) = a X ϑ + b X , a X = E M X , b X = Q H X .
Here a X a_X a X is a sum of active budgets, and b X b_X b X is a sum of constant arc capacities. Thus M X , H X M_X,H_X M X , H X are nonnegative integers with M X ≤ N E M_X \le NE M X ≤ N E and H X ≤ ( N 2 + 2 N ) Q H_X \le(N^2 + 2N)Q H X ≤ ( N 2 + 2 N ) Q . Besides the endpoints 0 , T 0,T 0 , T , the trial parameters of the GGT breakpoint algorithm are intersections of affine cut capacities; an intersection of two distinct slopes has the form
ϑ = E ( H Y − H X ) Q ( M X − M Y ) . \vartheta= \frac{E(H_Y-H_X)}{Q(M_X-M_Y)}. ϑ = Q ( M X − M Y ) E ( H Y − H X ) .
The same description applies after contraction, since cuts of a contracted network lift to cuts of the original stage network; any common affine contribution cancels in the intersection. The endpoint T = max i R i / B i T = \max_i R_i/B_i T = max i R i / B i also has polynomial encoding length. Hence every trial parameter and every trial capacity has polynomial encoding length. There are only polynomially many trials. The product of their capacity denominators therefore has polynomial bit length and is a common denominator for the flow and residual updates, which use additions, subtractions, and comparisons. The magnitudes of these quantities are bounded by sums of the trial capacities. Thus all intermediate flow data in the GGT call have polynomial encoding length as well.
At the accepted parameter ϑ ∗ = E d / ( Q M ) \vartheta_* = Ed/(QM) ϑ ∗ = E d / ( QM ) , the source capacities of Q ( ϑ ∗ ) Q(\vartheta_*) Q ( ϑ ∗ ) are B i ϑ ∗ = m i d / ( Q M ) B_i\vartheta_* = m_i d/(QM) B i ϑ ∗ = m i d / ( QM ) , and all other capacities have denominators dividing Q Q Q . The final ordinary maximum flow, computed from zero by shortest augmenting paths, therefore has entries q i j = z i j / ( Q M ) q_{ij} = z_{ij}/(QM) q ij = z ij / ( QM ) for integers z i j z_{ij} z ij . Its expenditure entries are w i j = λ ∗ q i j = z i j / ( E d ) w_{ij} = \lambda_*q_{ij} = z_{ij}/(Ed) w ij = λ ∗ q ij = z ij / ( E d ) . The initial quantity flow likewise has denominator dividing Q Q Q . Subtracting committed quantities and costs also gives polynomial-length remaining quantities and budgets for departing buyers.
For completion, take the product of the denominators of the remaining supplies, deficits, and allocation entries. There are polynomially many such quantities, each of polynomial encoding length, so this common denominator has polynomial bit length. The filling procedure uses only addition, subtraction, and minima; it preserves this denominator and keeps all allocation entries in [ 0 , 1 ] [0,1] [ 0 , 1 ] . The final allocation therefore has polynomial encoding length as well.
Proof of Theorem 1.3 . Lemmas 6.5 and 6.6 establish feasibility, the invariant, and termination. Lemmas 6.7 and 6.8 give an exact normalized equilibrium with minimum-expenditure tie-breaking. The initial normalization preserves these conclusions for the original utilities.
The algorithm uses one initial maximum-flow computation and at most N N N positive-price stages. By Lemma 6.2 , each stage uses one GGT call, one ordinary maximum-flow computation, and a residual reachability search in the expenditure network. Every network has v = O ( N ) v = O(N) v = O ( N ) vertices and m = O ( N 2 ) m = O(N^2) m = O ( N 2 ) arcs. The GGT breakpoint algorithm uses O ( v m log ( 2 + v 2 / m ) ) O(v m \log(2 + v^2/m)) O ( v m log ( 2 + v 2 / m )) arithmetic operations, while the Edmonds–Karp shortest-augmenting-path algorithm uses O ( v m 2 ) O(vm^2) O ( v m 2 ) . Thus the total is O ( N 6 ) O(N^6) O ( N 6 ) arithmetic operations, without optimizing the ordinary maximum-flow subroutine. Cut searches and allocation updates have smaller cost. Completion makes at most 2 N 2N 2 N nonzero assignments, because each exhausts a remaining supply or a deficit. The operation count is independent of the magnitudes and encoding lengths of the rational input, and Lemma 6.9 bounds every intermediate encoding length polynomially. The algorithm is therefore strongly polynomial.
Three common marginal slopes
Theorem 1.3 permits two common slopes for each buyer. With three prescribed slopes 1 , a , 0 1,a,0 1 , a , 0 , the class includes the hard linear instances of Theorem 1.1 . As in Corollary 1.4, segments may have zero length. Approximation is defined by Definition 2.2 , using separable utility in the budget-one benchmark and imposing no minimum-expenditure tie-breaking.
Proof of Corollary 1.4. Fix a rational a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) and set
f i j ( t ) = ( 1 − a ) min { t , τ i j ( 1 ) } + a min { t , τ i j ( 2 ) } , 0 ≤ τ i j ( 1 ) ≤ τ i j ( 2 ) ≤ 1. f_{ij}(t)=(1-a)\min\{t,\tau_{ij}^{(1)}\}+a\min\{t,\tau_{ij}^{(2)}\}, \qquad0\leq\tau_{ij}^{(1)}\leq\tau_{ij}^{(2)}\leq1. f ij ( t ) = ( 1 − a ) min { t , τ ij ( 1 ) } + a min { t , τ ij ( 2 ) } , 0 ≤ τ ij ( 1 ) ≤ τ ij ( 2 ) ≤ 1.
The successive marginal slopes are 1 , a , 0 1,a,0 1 , a , 0 . Given a linear instance with utilities in { 0 , a , 1 } \{0,a,1\} { 0 , a , 1 } , choose
( τ i j ( 1 ) , τ i j ( 2 ) ) = { ( 0 , 0 ) , u i j = 0 , ( 0 , 1 ) , u i j = a , ( 1 , 1 ) , u i j = 1. (\tau_{ij}^{(1)},\tau_{ij}^{(2)})=
\begin{cases}
(0,0), & u_{ij}=0,\\
(0,1), & u_{ij}=a,\\
(1,1), & u_{ij}=1.
\end{cases} ( τ ij ( 1 ) , τ ij ( 2 ) ) = ⎩ ⎨ ⎧ ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 1 ) , u ij = 0 , u ij = a , u ij = 1.
Then f i j ( t ) = u i j t f_{ij}(t)=u_{ij}t f ij ( t ) = u ij t on [ 0 , 1 ] [0,1] [ 0 , 1 ] . Utilities of all unit bundles and all budget-one demand values are unchanged, as are supplies, budgets, and price normalization. A normalized additive ε ∗ ( a ) / N \varepsilon_*(a)/N ε ∗ ( a ) / N -equilibrium of the transformed instance is therefore an equilibrium with the same error in the original instance. The transformation has polynomial size and uses the identity decoder, so Theorem 1.1 proves the corollary. Lemma 4.11 gives existence and polynomial-length rational witnesses, since the utilities on unit bundles are identical.
Discussion
Our results distinguish two ways of extending the tractable bi-valued HZ model. For linear utilities, adding a third common value makes inverse-linear approximation PPAD-complete, for every prescribed rational middle value a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) . For separable concave utilities, arbitrary rational buyer–good breakpoints remain compatible with strongly polynomial-time exact computation when each buyer has two marginal slopes common across goods. These results identify a boundary in the expressive power of preferences, while leaving several finer computational questions open.
The optimal approximation error. For each fixed rational a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) , what is the optimal polynomial-time approximation guarantee for HZ markets with utilities in { 0 , a , 1 } \{0,a,1\} { 0 , a , 1 } , under the normalized additive notion of Definition 2.2 ? Specializing the analysis of [18 Lemma 4.7] gives an additive a ( 1 − a ) a(1-a) a ( 1 − a ) guarantee. Since a a a is fixed and rational, the clone proportions a a a and 1 − a 1-a 1 − a can be implemented exactly, without rounding loss. In particular, the guarantee is 1 / 4 1/4 1/4 for { 0 , 1 / 2 , 1 } \{0,1/2,1\} { 0 , 1/2 , 1 } . Can this bound be improved, and what hardness threshold can be established under PCP for PPAD? Our constant-error lower bound leaves a gap to this algorithmic guarantee. Determining the threshold for a = 1 / 2 a=1/2 a = 1/2 is a concrete first target. More generally, how does the optimal error depend on a a a , especially as a a a approaches 0 0 0 or 1 1 1 , where the utility domain becomes bi-valued?
Few buyers with three utility values. Fix a rational a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) , and suppose that only k k k buyers use all three values in { 0 , a , 1 } \{0,a,1\} { 0 , a , 1 } , while every other buyer uses at most two. Can a normalized additive ε \varepsilon ε -equilibrium be computed in time polynomial in N N N and 1 / ε 1/\varepsilon 1/ ε for every fixed k k k ? Here the polynomial degree may depend on k k k . The case k = 1 k=1 k = 1 is a natural starting point. A stronger goal is an algorithm with running time
f ( k ) poly ( N , 1 / ε ) , f(k)\operatorname{poly}(N,1/\varepsilon), f ( k ) poly ( N , 1/ ε ) ,
where the polynomial degree is independent of k k k . This asks whether the bi-valued algorithm can accommodate a small number of buyers with richer preferences. The remaining buyers may have arbitrarily many distinct bi-valued preference types, so algorithms for a fixed total number of preference types [1 ] do not resolve this question.
Parameter bounds
This appendix verifies the integer multiplicities chosen in Subsection 4.4. Fix a = A / D a=A/D a = A / D in lowest terms, C = 16 D 2 C=16D^2 C = 16 D 2 , b = 4 C b=4C b = 4 C , and 0 < τ < κ / 100 0<\tau<\kappa/100 0 < τ < κ /100 . Let K K K be a positive multiple of D 2 ( D 2 − A 2 ) D^2(D^2-A^2) D 2 ( D 2 − A 2 ) satisfying (20) . Every bound below holds for all six degree pairs h v ∈ { 0 , 1 , 2 } h_v\in\{0,1,2\} h v ∈ { 0 , 1 , 2 } and o v ∈ { 1 , 2 } o_v\in\{1,2\} o v ∈ { 1 , 2 } .
Lemma A.1 (Parameter feasibility). All supplies and buyer counts are positive integers. The endpoints satisfy 1 < L < U 1<L<U 1 < L < U , and the populations satisfy
F v > S L + S M , c v > S H , A F v R > S F v R , A U v R > S U v R . F_v>S_L+S_M,\qquad c_v>S_H,\qquad A^R_{F_v}>S^R_{F_v},\qquad A^R_{U_v}>S^R_{U_v}. F v > S L + S M , c v > S H , A F v R > S F v R , A U v R > S U v R . The endpoints satisfy
a L ≥ 1 + a 2 a , a ( U + η ) < 1 a , L + η < U . aL\ge\frac{1+a}{2a},\qquad a(U+\eta)<\frac{1}{a},\qquad L+\eta<U. a L ≥ 2 a 1 + a , a ( U + η ) < a 1 , L + η < U . Consequently, a ( L + η ) < 1 / a a(L+\eta)<1/a a ( L + η ) < 1/ a and a 2 ( U + η ) < 1 a^2(U+\eta)<1 a 2 ( U + η ) < 1 . The decoding error obeys
6 a 2 w ( 1 + τ ) L − 1 + 2 τ < κ 10 , η w = τ < κ 4 . (29) \frac{6a^2w(1+\tau)}{L-1}+2\tau<\frac{\kappa}{10},\qquad\frac{\eta}{w}=\tau<\frac{\kappa}{4}. \tag*{(29)} L − 1 6 a 2 w ( 1 + τ ) + 2 τ < 10 κ , w η = τ < 4 κ . (29)
Lemma A.2 (Supply and population inequalities). At each vertex, the low supply satisfies
o v K < S L < o v K + b v , o v K + b v S L < a L . (30) o_vK<S_L<o_vK+b_v,\qquad\frac{o_vK+b_v}{S_L}<aL. \tag*{(30)} o v K < S L < o v K + b v , S L o v K + b v < a L . (30) The link populations and middle supply satisfy c v > b + 1 c_v>b+1 c v > b + 1 , a L S M > c v + 10 aLS_M>c_v+10 a L S M > c v + 10 , and
3 ( b + 1 ) ( 1 + a ) K < 1. \frac{3(b+1)(1+a)}{K}<1. K 3 ( b + 1 ) ( 1 + a ) < 1. The high supply satisfies L S H > 10 LS_H>10 L S H > 10 and ( L + η ) S H < c v (L+\eta)S_H<c_v ( L + η ) S H < c v . In particular, c v > b v c_v>b_v c v > b v and a L S M > b v aLS_M>b_v a L S M > b v .
Proof of Lemmas A.1 and A.2. We first record the consequences of (20) used throughout the proof. Since D ≥ 2 D\ge2 D ≥ 2 , we have C ≥ 64 C\ge64 C ≥ 64 and b ≥ 256 b\ge256 b ≥ 256 . The bound on K K K gives
K > max { 48 , 6 ( b + 1 ) , 2 a ( b + 1 ) 1 − a } , γ K > 4 ( b + 1 ) , w < 1 128 . K>\max\left\{48,6(b+1),\frac{2a(b+1)}{1-a}\right\},\qquad\gamma K>4(b+1),\qquad w<\frac{1}{128}. K > max { 48 , 6 ( b + 1 ) , 1 − a 2 a ( b + 1 ) } , γ K > 4 ( b + 1 ) , w < 128 1 .
Here γ K ≥ ( 8 b + 40000 ) / ( ( 1 − a 2 ) ( 1 − a ) ) > 8 b > 4 ( b + 1 ) \gamma K\ge(8b+40000)/((1-a^2)(1-a))>8b>4(b+1) γ K ≥ ( 8 b + 40000 ) / (( 1 − a 2 ) ( 1 − a )) > 8 b > 4 ( b + 1 ) , and we also have K > 200 / ( κ a 2 ) K>200/(\kappa a^2) K > 200/ ( κ a 2 ) .
Integrality and positivity. Write K = j D 2 ( D 2 − A 2 ) K=jD^2(D^2-A^2) K = j D 2 ( D 2 − A 2 ) . Then γ K = j A 2 D 2 \gamma K=jA^2D^2 γ K = j A 2 D 2 , so C , b , c v C,b,c_v C , b , c v are multiples of D 2 D^2 D 2 and
S L = o v K + C , S M = A D ( j o v A 2 − 48 ) , S H = 32 A 2 S_L=o_vK+C,\qquad S_M=AD(j_o{}_vA^2-48),\qquad S_H=32A^2 S L = o v K + C , S M = A D ( j o v A 2 − 48 ) , S H = 32 A 2
are integers. The floor, reference, and anchor counts are integers by their definitions using ceilings. Also,
b − 5 ≤ b v ≤ b + 1 , c v ≥ γ K − b > 3 b + 4 > b + 1. b-5\le b_v\le b+1,\qquad c_v\ge\gamma K-b>3b+4>b+1. b − 5 ≤ b v ≤ b + 1 , c v ≥ γ K − b > 3 b + 4 > b + 1.
These inequalities imply positivity of every count and supply. They also give C < b − 5 ≤ b v C<b-5\le b_v C < b − 5 ≤ b v , hence o v K < S L < o v K + b v o_vK<S_L<o_vK+b_v o v K < S L < o v K + b v .
Price and clearing inequalities. For the remaining low-price comparison,
o v K + b v S L = 1 + b v − C o v K + C < 1 + b + 1 K < 1 + 1 − a 2 a . \frac{o_vK+b_v}{S_L}=1+\frac{b_v-C}{o_vK+C}<1+\frac{b+1}{K}<1+\frac{1-a}{2a}. S L o v K + b v = 1 + o v K + C b v − C < 1 + K b + 1 < 1 + 2 a 1 − a .
whereas
a L − 1 = 1 − a a ( 1 − 3 ( 1 + a ) K ) > 1 − a 2 a . aL-1=\frac{1-a}{a}\left(1-\frac{3(1+a)}{K}\right)>\frac{1-a}{2a}. a L − 1 = a 1 − a ( 1 − K 3 ( 1 + a ) ) > 2 a 1 − a .
This proves (30) and a L > ( 1 + a ) / ( 2 a ) > 1 aL>(1+a)/(2a)>1 a L > ( 1 + a ) / ( 2 a ) > 1 . Since c v + C = o v γ K − 3 C < o v γ K c_v+C=o_v\gamma K-3C<o_v\gamma K c v + C = o v γ K − 3 C < o v γ K ,
a L S M = c v + C − 3 ( 1 − a 2 ) ( c v + C ) K > c v + C − 3 o v a 2 > c v + C − 6 ≥ c v + 58 > c v + 10. \begin{aligned}
aLS_M=c_v+C-\frac{3(1-a^2)(c_v+C)}{K} \\
&>c_v+C-3o_va^2>c_v+C-6\ge c_v+58>c_v+10.
\end{aligned} a L S M = c v + C − K 3 ( 1 − a 2 ) ( c v + C ) > c v + C − 3 o v a 2 > c v + C − 6 ≥ c v + 58 > c v + 10.
The remaining link inequality follows from 3 ( b + 1 ) ( 1 + a ) / K < 6 ( b + 1 ) / K < 1 3(b+1)(1+a)/K<6(b+1)/K<1 3 ( b + 1 ) ( 1 + a ) / K < 6 ( b + 1 ) / K < 1 . Since c v > b + 1 ≥ b v c_v>b+1\ge b_v c v > b + 1 ≥ b v , we also have c v > b v c_v>b_v c v > b v and a L S M > b v aLS_M>b_v a L S M > b v .
Using S H = 2 a 2 C S_H=2a^2C S H = 2 a 2 C ,
L S H = ( 1 − 3 ( 1 − a 2 ) K ) 2 C > 15 16 2 C ≥ 120 > 10. LS_H=\left(1-\frac{3(1-a^2)}{K}\right)2C>\frac{15}{16}2C\ge120>10. L S H = ( 1 − K 3 ( 1 − a 2 ) ) 2 C > 16 15 2 C ≥ 120 > 10.
Also L + η = a − 2 − ( 3 / 2 − τ ) w < a − 2 L+\eta=a^{-2}-(3/2-\tau)w<a^{-2} L + η = a − 2 − ( 3/2 − τ ) w < a − 2 , so ( L + η ) S H < 2 C < c v (L+\eta)S_H<2C<c_v ( L + η ) S H < 2 C < c v . Because 0 < τ < 1 / 2 0<\tau<1/2 0 < τ < 1/2 , we have η < w \eta<w η < w , L + η < U L+\eta<U L + η < U , and
a ( U + η ) = 1 a − a ( 1 / 2 − τ ) w < 1 a . a(U+\eta)=\frac{1}{a}-a(1/2-\tau)w<\frac{1}{a}. a ( U + η ) = a 1 − a ( 1/2 − τ ) w < a 1 .
Together with a L > ( 1 + a ) / ( 2 a ) aL>(1+a)/(2a) a L > ( 1 + a ) / ( 2 a ) , these are the required reference bounds and imply 1 < L < U 1<L<U 1 < L < U . Since a L , a U > 1 aL,aU>1 a L , a U > 1 , each anchor count strictly exceeds its reference supply. Also 0 < θ < 1 0<\theta<1 0 < θ < 1 gives F v > S L + S M F_v>S_L+S_M F v > S L + S M , while ( L + η ) S H < c v (L+\eta)S_H<c_v ( L + η ) S H < c v and L + η > 1 L+\eta>1 L + η > 1 give c v > S H c_v>S_H c v > S H .
Decoding error. The identity L − 1 = ( 1 − a 2 ) ( K − 3 ) / ( a 2 K ) L-1=(1-a^2)(K-3)/(a^2K) L − 1 = ( 1 − a 2 ) ( K − 3 ) / ( a 2 K ) yields
6 a 2 w ( 1 + τ ) L − 1 + 2 τ = 12 a 2 ( 1 + τ ) K − 3 + 2 τ < 14 a 2 K + 2 τ . \frac{6a^2w(1+\tau)}{L-1}+2\tau
=\frac{12a^2(1+\tau)}{K-3}+2\tau
<\frac{14a^2}{K}+2\tau. L − 1 6 a 2 w ( 1 + τ ) + 2 τ = K − 3 12 a 2 ( 1 + τ ) + 2 τ < K 14 a 2 + 2 τ .
The last inequality uses K ≥ 48 K\ge48 K ≥ 48 and τ ≤ κ / 100 < 1 / 100 \tau\le\kappa/100<1/100 τ ≤ κ /100 < 1/100 . Since K ≥ 200 / ( κ a 2 ) K\ge200/(\kappa a^2) K ≥ 200/ ( κ a 2 ) ,
14 a 2 K + 2 τ ≤ 14 κ a 4 200 + 2 κ 100 < 9 κ 100 < κ 10 . \frac{14a^2}{K}+2\tau\le\frac{14\kappa a^4}{200}+\frac{2\kappa}{100}<\frac{9\kappa}{100}<\frac{\kappa}{10}. K 14 a 2 + 2 τ ≤ 200 14 κ a 4 + 100 2 κ < 100 9 κ < 10 κ .
Finally, η / w = τ ≤ κ / 100 < κ / 4 \eta/w=\tau\le\kappa/100<\kappa/4 η / w = τ ≤ κ /100 < κ /4 . The same lower bound on K K K gives w ≤ κ ( 1 − a 2 ) / 100 < κ / 4 w\le\kappa(1-a^2)/100<\kappa/4 w ≤ κ ( 1 − a 2 ) /100 < κ /4 . □ \square □
Lemma A.3 (Balancing goods). For a nonempty graph, N > G l i s t e d N>G_{\mathrm{listed}} N > G listed . Hence the balancing group Z \mathcal{Z} Z is nonempty, and the completed market has the same number of buyers and goods.
Proof. Counting each wire population at its source gives
N = ∑ v ∈ V ( b v + c v + F v + o v K + A F v R + A U v R ) . (31) N=\sum_{v\in V}\left(b_v+c_v+F_v+o_vK+A_{F_v}^{R}+A_{U_v}^{R}\right). \tag*{(31)} N = v ∈ V ∑ ( b v + c v + F v + o v K + A F v R + A U v R ) . (31)
The number of goods before adding Z \mathcal{Z} Z is
G l i s t e d = ∑ v ∈ V ( S L + S M + S H + S F v R + S U v R ) . G_{\mathrm{listed}}=\sum_{v\in V}\left(S_L+S_M+S_H+S_{F_v}^{R}+S_{U_v}^{R}\right). G listed = v ∈ V ∑ ( S L + S M + S H + S F v R + S U v R ) .
At each vertex, Lemma A.1 gives F v > S L + S M F_v>S_L+S_M F v > S L + S M , c v > S H c_v>S_H c v > S H , A F v R > S F v R A_{F_v}^{R}>S_{F_v}^{R} A F v R > S F v R , and A U v R > S U v R A_{U_v}^{R}>S_{U_v}^{R} A U v R > S U v R . The remaining terms b v + o v K b_v+o_vK b v + o v K in N N N are positive. Summing over a nonempty graph yields N > G l i s t e d N>G_{\mathrm{listed}} N > G listed , so adding N − G l i s t e d N-G_{\mathrm{listed}} N − G listed zero-utility goods makes total supply equal to the number of buyers. □ \square □
:::
Quantitative estimates for robustness
We prove the demand estimates used in Lemma 4.9 and the local decoding statement of Lemma 5.6 . Fix a normalized additive ε \varepsilon ε -equilibrium of the market in § 3 , and equalize prices within each group using Lemma 2.3 . Retain the notation w = U − L w=U-L w = U − L , η = τ w \eta=\tau w η = τ w , and ( t v , z v ) (t_v,z_v) ( t v , z v ) from (4) . Retain the unapproved expenditure W v W_v W v from Subsection 4.5, and let B j ( v ) B_j(v) B j ( v ) contain the vertices at undirected distance at most j j j from v v v .
All implicit constants depend only on a a a , uniformly over the graph, admissible K K K , and 0 < τ ≤ κ / 100 0<\tau\le\kappa/100 0 < τ ≤ κ /100 .
Demand estimates
For buyer i i i , write E i + E_i^+ E i + and E i 0 E_i^0 E i 0 for expenditure on goods with u i j > 0 u_{ij}>0 u ij > 0 and u i j = 0 u_{ij}=0 u ij = 0 , respectively, and write Q i 0 Q_i^0 Q i 0 for her total quantity of goods with u i j = 0 u_{ij}=0 u ij = 0 . For a demand dual ( β i , μ i ) (\beta_i,\mu_i) ( β i , μ i ) , the reduced slack of good j j j is β i p j + μ i − u i j \beta_i p_j+\mu_i-u_{ij} β i p j + μ i − u ij .
Lemma B.1 (Allocated slack and demand deficits). Choose an optimal demand dual ( β i , μ i ) (\beta_i,\mu_i) ( β i , μ i ) for buyer i i i :
β i ≥ 0 , β i p j + μ i ≥ u i j , β i + μ i = V i ( p ) . \beta_i\ge0,\qquad\beta_i p_j+\mu_i\ge u_{ij},\qquad\beta_i+\mu_i=V_i(p). β i ≥ 0 , β i p j + μ i ≥ u ij , β i + μ i = V i ( p ) . Then 0 ≤ β i , μ i ≤ 1 0\le\beta_i,\mu_i\le1 0 ≤ β i , μ i ≤ 1 , and her allocated reduced slack satisfies
∑ j ( β i p j + μ i − u i j ) x i j = V i ( p ) − U i ( x i ) + β i ( p ⋅ x i − 1 ) ≤ 2 ε . (32) \sum_j(\beta_i p_j+\mu_i-u_{ij})x_{ij}=V_i(p)-U_i(x_i)+\beta_i(p\cdot x_i-1)\le2\varepsilon. \tag*{(32)} j ∑ ( β i p j + μ i − u ij ) x ij = V i ( p ) − U i ( x i ) + β i ( p ⋅ x i − 1 ) ≤ 2 ε . (32) If β i > 0 \beta_i>0 β i > 0 , then
E i 0 ≤ 2 ε β i , 1 − ε β i ≤ E i + ≤ 1 + ε . E_i^0\le\frac{2\varepsilon}{\beta_i},\qquad1-\frac{\varepsilon}{\beta_i}\le E_i^+\le1+\varepsilon. E i 0 ≤ β i 2 ε , 1 − β i ε ≤ E i + ≤ 1 + ε . If μ i > 0 \mu_i>0 μ i > 0 , then Q i 0 ≤ 2 ε / μ i Q_i^0\le2\varepsilon/\mu_i Q i 0 ≤ 2 ε / μ i . For a population of M M M identical buyers using one common optimal dual, a group with reduced slack s > 0 s>0 s > 0 receives at most 2 M ε / s 2M\varepsilon/s 2 M ε / s quantity and 2 M ε p / s 2M\varepsilon p/s 2 M εp / s expenditure, where p p p is its price.
Proof. Normalization supplies a zero-price good. Its dual constraint gives μ i ≥ 0 \mu_i\ge0 μ i ≥ 0 , and β i + μ i = V i ( p ) ≤ 1 \beta_i+\mu_i=V_i(p)\le1 β i + μ i = V i ( p ) ≤ 1 bounds both variables by one. Expanding the left side of (32) and using the unit row sum gives the identity. The utility error contributes at most ε \varepsilon ε , and the budget error contributes at most β i ε ≤ ε \beta_i\varepsilon\le\varepsilon β i ε ≤ ε .
On unapproved goods the slack is β i p j + μ i \beta_i p_j+\mu_i β i p j + μ i , which gives the bounds on E i 0 E_i^0 E i 0 and Q i 0 Q_i^0 Q i 0 . On approved goods, dual feasibility and total quantity at most one give U i ( x i ) ≤ β i E i + + μ i U_i(x_i)\le\beta_i E_i^++\mu_i U i ( x i ) ≤ β i E i + + μ i . Comparing with U i ( x i ) ≥ β i + μ i − ε U_i(x_i)\ge\beta_i+\mu_i-\varepsilon U i ( x i ) ≥ β i + μ i − ε proves E i + ≥ 1 − ε / β i E_i^+\ge1-\varepsilon/\beta_i E i + ≥ 1 − ε / β i . The same lower bound holds for total expenditure, and both expenditures are at most 1 + ε 1+\varepsilon 1 + ε . Finally, sum the allocated-slack bound over a population sharing one dual and retain the contribution of the specified group.
We will also use the following consequence when a group price is not yet bounded: if its reduced slack satisfies s ≥ c ( p − p 0 ) > 0 s\ge c(p-p_0)>0 s ≥ c ( p − p 0 ) > 0 , with c > 0 c>0 c > 0 depending only on a a a and p 0 = O a ( 1 ) p_0=O_a(1) p 0 = O a ( 1 ) , then p / s = O a ( 1 + 1 / ( p − p 0 ) ) p/s=O_a(1+1/(p-p_0)) p / s = O a ( 1 + 1/ ( p − p 0 )) .
Lemma B.2 (A uniform utility gap). There are positive rational constants d a , g a , c a d_a,g_a,c_a d a , g a , c a , depending only on a a a , such that, for all sufficiently large admissible K K K and ε ≤ c a \varepsilon\le c_a ε ≤ c a , every group valued at one by some buyer has price greater than 1 + d a 1+d_a 1 + d a , and every buyer satisfies V i ( p ) ≤ 1 − g a V_i(p)\le1-g_a V i ( p ) ≤ 1 − g a .
Proof. Put r ∗ = ( 1 + a ) / ( 2 a ) > 1 r_*=(1+a)/(2a)>1 r ∗ = ( 1 + a ) / ( 2 a ) > 1 and s = 1 − 1 / r ∗ = ( 1 − a ) / ( 1 + a ) > θ s=1-1/r_*=(1-a)/(1+a)>\theta s = 1 − 1/ r ∗ = ( 1 − a ) / ( 1 + a ) > θ . The parameter bounds give a U > a L ≥ r ∗ aU>aL\ge r_* a U > a L ≥ r ∗ . Choose positive rational d , c d,c d , c so that
c < s , 1 r ∗ + c < 1 1 + d , d + c 1 − a + 3 c < s − θ , d + c 1 − a < 1 2 . c<s,\qquad\frac{1}{r_*}+c<\frac{1}{1+d},\qquad\frac{d+c}{1-a}+3c<s-\theta,\qquad\frac{d+c}{1-a}<\frac{1}{2}. c < s , r ∗ 1 + c < 1 + d 1 , 1 − a d + c + 3 c < s − θ , 1 − a d + c < 2 1 .
These choices are possible because r ∗ > 1 r_*>1 r ∗ > 1 and s > θ s>\theta s > θ . Assume ε ≤ c \varepsilon\le c ε ≤ c .
A reference with price r r r , anchor count A A A , and supply S S S satisfies A / S ≥ r ∗ A/S\ge r_* A / S ≥ r ∗ . If r ≤ 1 r\le1 r ≤ 1 , every anchor has optimum one and must receive at least 1 − ε 1-\varepsilon 1 − ε reference quantity. This contradicts A ( 1 − ε ) > S A(1-\varepsilon)>S A ( 1 − ε ) > S . Hence r > 1 r>1 r > 1 , the anchor optimum is 1 / r 1/r 1/ r , and supply feasibility gives
1 r ≤ S A + ε ≤ 1 r ∗ + ε , \frac{1}{r}\le\frac{S}{A}+\varepsilon\le\frac{1}{r_*}+\varepsilon, r 1 ≤ A S + ε ≤ r ∗ 1 + ε ,
and the choice of c c c implies r > 1 + d r>1+d r > 1 + d .
Suppose a middle price satisfies m ≤ 1 + d m\le1+d m ≤ 1 + d . Every floor buyer then has optimum at least 1 / ( 1 + d ) 1/(1+d) 1/ ( 1 + d ) . If her middle and reference quantities are X M , X R X_M,X_R X M , X R , all her other goods have utility at most a a a , and hence
X M ≥ 1 / ( 1 + d ) − a − ε 1 − a − X R ≥ s − d + ε 1 − a − 3 ε > θ . X_M\ge\frac{1/(1+d)-a-\varepsilon}{1-a}-X_R\ge s-\frac{d+\varepsilon}{1-a}-3\varepsilon>\theta. X M ≥ 1 − a 1/ ( 1 + d ) − a − ε − X R ≥ s − 1 − a d + ε − 3 ε > θ .
The second inequality uses X R ≤ ( 1 + ε ) / r F ≤ 1 / r ∗ + 3 ε X_R\le(1+\varepsilon)/r_F\le1/r_*+3\varepsilon X R ≤ ( 1 + ε ) / r F ≤ 1/ r ∗ + 3 ε . Summing X M > θ X_M>\theta X M > θ over the floor population contradicts F v θ > S L + S M F_v\theta>S_L+S_M F v θ > S L + S M . Therefore m > 1 + d m>1+d m > 1 + d .
If a high price were at most 1 + d 1+d 1 + d , each upper buyer would require at least [ 1 / ( 1 + d ) − a − ε ] / ( 1 − a ) > 1 / 2 [1/(1+d)-a-\varepsilon]/(1-a)>1/2 [ 1/ ( 1 + d ) − a − ε ] / ( 1 − a ) > 1/2 high quantity. For large K K K , the inequality c v > 2 S H c_v>2S_H c v > 2 S H rules this out.
References, middle goods, and high goods exhaust the groups valued at one. A budget-one bundle contains at most 1 / ( 1 + d ) 1/(1+d) 1/ ( 1 + d ) total quantity from these groups; every other good has utility at most a a a . Consequently
V i ( p ) ≤ a + 1 − a 1 + d = 1 − g , g = ( 1 − a ) d 1 + d > 0. V_i(p)\le a+\frac{1-a}{1+d}=1-g,\qquad g=\frac{(1-a)d}{1+d}>0. V i ( p ) ≤ a + 1 + d 1 − a = 1 − g , g = 1 + d ( 1 − a ) d > 0.
Take d a = d d_a=d d a = d , g a = g g_a=g g a = g , and c a = c c_a=c c a = c .
Local price estimates
The next three lemmas hold with common constants K a K_a K a and c a > 0 c_a>0 c a > 0 under
K ≥ K a , K 2 ε ≤ c a , 0 ≤ ζ ≤ c a . K\ge K_a,\qquad K^2\varepsilon\le c_a,\qquad0\le\zeta\le c_a. K ≥ K a , K 2 ε ≤ c a , 0 ≤ ζ ≤ c a .
Here K K K is admissible and 0 < τ ≤ κ / 100 0<\tau\le\kappa/100 0 < τ ≤ κ /100 , as above. The proofs choose K a K_a K a large enough and c a c_a c a small enough, depending only on a a a .
Lemma B.3 (Preliminary local prices). Under the stated small-error conditions , if W v ≤ ζ W_v\le\zeta W v ≤ ζ , then
a L − O a ( ε ) ≤ r F v ≤ a ( L + η ) + O a ( ε ) + ζ S F v R , aL-O_a(\varepsilon)\le r_{Fv}\le a(L+\eta)+O_a(\varepsilon)+\frac{\zeta}{S^R_{Fv}}, a L − O a ( ε ) ≤ r F v ≤ a ( L + η ) + O a ( ε ) + S F v R ζ , a U − O a ( ε ) ≤ r U v ≤ a ( U + η ) + O a ( ε ) + ζ S U v R . aU-O_a(\varepsilon)\le r_{Uv}\le a(U+\eta)+O_a(\varepsilon)+\frac{\zeta}{S^R_{Uv}}. a U − O a ( ε ) ≤ r U v ≤ a ( U + η ) + O a ( ε ) + S U v R ζ . These references lie in a fixed compact subinterval of ( 1 , ∞ ) (1,\infty) ( 1 , ∞ ) , and, for some constant c > 0 c>0 c > 0 ,
max { r F v , r U v } ≤ 1 / a − c / K , r U v − r F v ≥ c / K . \max\{r_{Fv},r_{Uv}\}\le1/a-c/K,\qquad r_{Uv}-r_{Fv}\ge c/K. max { r F v , r U v } ≤ 1/ a − c / K , r U v − r F v ≥ c / K .
The target prices satisfy
q v ≥ a r F v − O a ( ε ) , m v ≥ r F v − O a ( ε ) , q_v \ge a r_{Fv} - O_a(\varepsilon), \qquad m_v \ge r_{Fv} - O_a(\varepsilon), q v ≥ a r F v − O a ( ε ) , m v ≥ r F v − O a ( ε ) ,
p v ≥ r F v / a − O a ( K ε ) ≥ L − O a ( K ε ) , p_v \ge r_{Fv}/a - O_a(K\varepsilon) \ge L - O_a(K\varepsilon), p v ≥ r F v / a − O a ( K ε ) ≥ L − O a ( K ε ) ,
a 2 L − O a ( K ε ) ≤ q v ≤ 1 + O a ( 1 / K ) < a L − c . a^2L - O_a(K\varepsilon) \le q_v \le1 + O_a(1/K) < aL - c. a 2 L − O a ( K ε ) ≤ q v ≤ 1 + O a ( 1/ K ) < a L − c .
An optimal dual shared by all floor buyers satisfies
μ = O a ( ε ) , s R = β r F v + μ − 1 = O a ( ε ) , β = 1 / r F v + O a ( ε ) ≥ c . \mu= O_a(\varepsilon), \qquad s_R = \beta r_{Fv} + \mu- 1 = O_a(\varepsilon), \qquad\beta= 1/r_{Fv} + O_a(\varepsilon) \ge c. μ = O a ( ε ) , s R = β r F v + μ − 1 = O a ( ε ) , β = 1/ r F v + O a ( ε ) ≥ c .
No bounds on neighboring endpoint prices are required.
Proof. Suppress the vertex subscript.
For a reference with price r r r , supply S S S , anchor count A A A , and M M M nonanchor approvers, anchor utility and revenue clearing give
r ≥ A / S 1 + ε A / S , r S ≤ ( A + M ) ( 1 + ε ) + ζ . r \ge\frac{A/S}{1+\varepsilon A/S}, \qquad rS \le(A+M)(1+\varepsilon)+\zeta. r ≥ 1 + ε A / S A / S , r S ≤ ( A + M ) ( 1 + ε ) + ζ .
Substitute the counts in (5) to obtain the two reference intervals. Since 1 / S R = O a ( η / K ) 1/S^R = O_a(\eta/K) 1/ S R = O a ( η / K ) , η = τ w \eta=\tau w η = τ w , and w = Θ a ( 1 / K ) w=\Theta_a(1/K) w = Θ a ( 1/ K ) , their errors are smaller than the endpoint gaps in (8) when K 2 ε K^2\varepsilon K 2 ε and ζ \zeta ζ are sufficiently small. This proves the remaining reference bounds and also gives
1 / r F ≥ a + c / K , 1 − 1 / r F ≥ θ + c 1/r_F \ge a+c/K, \qquad1-1/r_F \ge\theta+c 1/ r F ≥ a + c / K , 1 − 1/ r F ≥ θ + c
for a possibly smaller c > 0 c>0 c > 0 .
Next average the F F F identical floor rows and denote their quantities by X ‾ L , X ‾ M , X ‾ R , X ‾ 0 \overline{X}_L,\overline{X}_M,\overline{X}_R,\overline{X}_0 X L , X M , X R , X 0 . Supply feasibility gives
X ‾ L ≤ S L / F , X ‾ M ≤ S M / F , X ‾ L + X ‾ M ≤ θ . \overline{X}_L \le S_L/F,\qquad\overline{X}_M \le S_M/F,\qquad\overline{X}_L+\overline{X}_M \le\theta. X L ≤ S L / F , X M ≤ S M / F , X L + X M ≤ θ .
Both target supplies are of order K K K , with S L / ( S L + S M ) S_L/(S_L+S_M) S L / ( S L + S M ) bounded below by a positive constant depending only on a a a . The separate supply bounds and θ ≤ a \theta\le a θ ≤ a imply
a X ‾ L + X ‾ M ≤ θ a S L + S M S L + S M ≤ a − c . a\overline{X}_L+\overline{X}_M \le\theta\frac{aS_L+S_M}{S_L+S_M}\le a-c. a X L + X M ≤ θ S L + S M a S L + S M ≤ a − c .
The optimum of a floor buyer is at least 1 / r F ≥ a + c / K 1/r_F\ge a+c/K 1/ r F ≥ a + c / K , so approximate optimality requires X ‾ R ≥ c \overline{X}_R\ge c X R ≥ c after reducing c c c if necessary. On the other hand, the budget gives X ‾ R ≤ ( 1 + ε ) / r F = a + O a ( 1 / K + ε ) \overline{X}_R\le(1+\varepsilon)/r_F=a+O_a(1/K+\varepsilon) X R ≤ ( 1 + ε ) / r F = a + O a ( 1/ K + ε ) . Together with θ ≤ ( 1 − a ) / 2 \theta\le(1-a)/2 θ ≤ ( 1 − a ) /2 and the unit row sums, this implies X ‾ 0 ≥ ( 1 − a ) / 3 \overline{X}_0\ge(1-a)/3 X 0 ≥ ( 1 − a ) /3 for large K K K .
Use one optimal dual for the whole floor population. By Lemma B.1 , the positive average reference quantity forces s R = O a ( ε ) s_R=O_a(\varepsilon) s R = O a ( ε ) , and the positive average unapproved quantity forces μ = O a ( ε ) \mu=O_a(\varepsilon) μ = O a ( ε ) . Consequently β = 1 / r F + O a ( ε ) ≥ c \beta=1/r_F+O_a(\varepsilon)\ge c β = 1/ r F + O a ( ε ) ≥ c . The low and middle dual constraints now give q ≥ a r F − O a ( ε ) q\ge ar_F-O_a(\varepsilon) q ≥ a r F − O a ( ε ) and m ≥ r F − O a ( ε ) m\ge r_F-O_a(\varepsilon) m ≥ r F − O a ( ε ) .
To bound the high price, note that all groups approved by an upper buyer cost more than one by Lemma B.2 . We may therefore choose an optimal dual with
μ U = 0 , β U = max { 1 / p , a / m , a / r U } . \mu_U=0,\qquad\beta_U=\max\{1/p,a/m,a/r_U\}. μ U = 0 , β U = max { 1/ p , a / m , a / r U } .
The reference bound gives β U ≥ c \beta_U\ge c β U ≥ c , hence approved expenditure 1 + O a ( ε ) 1+O_a(\varepsilon) 1 + O a ( ε ) per buyer. Suppose Δ = r F / a − p > H a K ε \Delta=r_F/a-p>H_aK\varepsilon Δ = r F / a − p > H a K ε for a sufficiently large constant H a H_a H a . Then m ≥ r F − O a ( ε ) m\ge r_F-O_a(\varepsilon) m ≥ r F − O a ( ε ) and r U > r F r_U>r_F r U > r F imply a p < m , r U ap<m,r_U a p < m , r U . High goods uniquely maximize utility per dollar, and each alternative’s reduced slack is bounded below by a constant times its price minus a p ap a p . The population estimate in Lemma B.1 bounds total expenditure on the alternatives by
O a ( K ε ( 1 + 1 / Δ ) ) = O a ( K ε + 1 / H a ) = O a ( 1 ) . O_a(K\varepsilon(1+1/\Delta))=O_a(K\varepsilon+1/H_a)=O_a(1). O a ( K ε ( 1 + 1/Δ )) = O a ( K ε + 1/ H a ) = O a ( 1 ) .
The price-to-slack estimate above applies even if m m m is unbounded. The upper population would therefore spend c v − O a ( 1 ) c_v-O_a(1) c v − O a ( 1 ) on high goods, whereas their revenue is p S H = O a ( 1 ) pS_H=O_a(1) p S H = O a ( 1 ) . This is impossible for large K K K , proving p ≥ r F / a − O a ( K ε ) p\ge r_F/a-O_a(K\varepsilon) p ≥ r F / a − O a ( K ε ) .
It remains to bound q q q from above. The floor dual satisfies
s L = β ( q − a r F ) + ( 1 − a ) μ + a s R ≥ β ( q − a r F ) . s_L=\beta(q-ar_F)+(1-a)\mu+as_R\ge\beta(q-ar_F). s L = β ( q − a r F ) + ( 1 − a ) μ + a s R ≥ β ( q − a r F ) .
If q > a r F + H a K ε q>ar_F+H_aK\varepsilon q > a r F + H a K ε , Lemma B.1 bounds floor expenditure on L v L_v L v by O a ( K ε + 1 / H a ) O_a(K\varepsilon+1/H_a) O a ( K ε + 1/ H a ) . Choose H a H_a H a large and K 2 ε K^2\varepsilon K 2 ε small so that this is at most one. Only lower links and outgoing wires supply other approved expenditure, giving
q S L ≤ ( o v K + b v ) ( 1 + ε ) + 1 + ζ . qS_L\le(o_vK+b_v)(1+\varepsilon)+1+\zeta. q S L ≤ ( o v K + b v ) ( 1 + ε ) + 1 + ζ .
If instead q ≤ a r F + H a K ε q\le ar_F+H_aK\varepsilon q ≤ a r F + H a K ε , the reference upper bound and smallness of K 2 ε K^2\varepsilon K 2 ε give q < 1 q<1 q < 1 . In both cases, q ≤ 1 + O a ( 1 / K ) q\le1+O_a(1/K) q ≤ 1 + O a ( 1/ K ) , and the lower bound on q q q gives q ≥ a 2 L − O a ( K ε ) q\ge a^2L-O_a(K\varepsilon) q ≥ a 2 L − O a ( K ε ) . Since a L → 1 / a > 1 aL\to1/a>1 a L → 1/ a > 1 , we also have q < a L − c q<aL-c q < a L − c for large K K K .
Lemma B.4 (Approximate price relations). Under the stated small-error conditions, suppose W u ≤ ζ W_u\le\zeta W u ≤ ζ for u = v u=v u = v and every incoming neighbor u u u of v v v . Then
∣ q v − a 2 p v ∣ + ∣ m v − a p v ∣ = O a ( K ε ) , \lvert q_v-a^2p_v\rvert+\lvert m_v-ap_v\rvert=O_a(K\varepsilon), ∣ q v − a 2 p v ∣ + ∣ m v − a p v ∣ = O a ( K ε ) , L − O a ( K ε ) ≤ p v ≤ U + 2 η + O a ( K ε ) , q v < 1. L-O_a(K\varepsilon)\le p_v\le U+2\eta+O_a(K\varepsilon),\qquad q_v<1. L − O a ( K ε ) ≤ p v ≤ U + 2 η + O a ( K ε ) , q v < 1.
All three target prices consequently lie in fixed compact intervals.
Proof. Apply Lemma B.3 at v v v and its incoming neighbors. We first bound the expenditure of incoming wires on H v H_v H v ; this forces the upper population to purchase high goods.
For an incoming wire, write q q q for the source low price and p p p for the destination high price. The preliminary bounds give
q ≤ 1 + O a ( 1 / K ) , p ≥ a − 2 − O a ( 1 / K ) , q / p ≤ a 2 + O a ( 1 / K ) < a − c q\le1+O_a(1/K),\qquad p\ge a^{-2}-O_a(1/K),\qquad q/p\le a^2+O_a(1/K)<a-c q ≤ 1 + O a ( 1/ K ) , p ≥ a − 2 − O a ( 1/ K ) , q / p ≤ a 2 + O a ( 1/ K ) < a − c
for some c > 0 c>0 c > 0 . Thus the low option has strictly greater utility per dollar, even when p p p is unbounded. If q ≥ 1 q\ge1 q ≥ 1 , its optimal dual is ( a / q , 0 ) (a/q,0) ( a / q , 0 ) , and the high slack is at least c p cp c p ; high spending per buyer is O a ( ε ) O_a(\varepsilon) O a ( ε ) . If q < 1 q<1 q < 1 , the mixed dual is
β = 1 − a p − q , μ = a p − q p − q ≥ c . \beta=\frac{1-a}{p-q},\qquad\mu=\frac{ap-q}{p-q}\ge c. β = p − q 1 − a , μ = p − q a p − q ≥ c .
The buyer’s unapproved quantity is O a ( ε ) O_a(\varepsilon) O a ( ε ) . Writing Y Y Y for her high quantity, the unit row and budget bounds give
p Y ≤ p p − q ( 1 − q + O a ( ε ) ) ≤ L − O a ( K ε ) L − 1 − O a ( K ε ) ( 1 − a 2 L + O a ( K ε ) ) . pY\le\frac{p}{p-q}(1-q+O_a(\varepsilon))\le\frac{L-O_a(K\varepsilon)}{L-1-O_a(K\varepsilon)}(1-a^2L+O_a(K\varepsilon)). p Y ≤ p − q p ( 1 − q + O a ( ε )) ≤ L − 1 − O a ( K ε ) L − O a ( K ε ) ( 1 − a 2 L + O a ( K ε )) .
There are at most 2 K 2K 2 K incoming buyers. Multiplying this bound by 2 K 2K 2 K gives a leading term tending to six. Including the q ≥ 1 q\ge1 q ≥ 1 case, their total high expenditure is at most 9 + O a ( K 2 ε ) 9+O_a(K^2\varepsilon) 9 + O a ( K 2 ε ) . High revenue is at least L S H − O a ( K ε ) > 10 LS_H - O_a(K\varepsilon) > 10 L S H − O a ( K ε ) > 10 . Since at most ζ \zeta ζ of it is unapproved expenditure, upper buyers must spend at least 1 / 2 1/2 1/2 on high goods. Choose their common optimal dual μ U = 0 \mu_U = 0 μ U = 0 , β U = max { 1 / p , a / m , a / r U } \beta_U = \max\{1/p, a/m, a/r_U\} β U = max { 1/ p , a / m , a / r U } . Their high expenditure multiplied by β U − 1 / p \beta_U - 1/p β U − 1/ p is its contribution to allocated slack. Therefore
β U − 1 / p = O a ( c v ε ) = O a ( K ε ) . \beta_U - 1/p = O_a(c_v\varepsilon) = O_a(K\varepsilon). β U − 1/ p = O a ( c v ε ) = O a ( K ε ) .
Since β U ≥ a / r U ≥ c \beta_U \ge a/r_U \ge c β U ≥ a / r U ≥ c , this bounds p p p from above. Substituting this bound back into the inequality gives p ≤ r U / a + O a ( K ε ) p \le r_U/a + O_a(K\varepsilon) p ≤ r U / a + O a ( K ε ) and m ≥ a p − O a ( K ε ) m \ge ap - O_a(K\varepsilon) m ≥ a p − O a ( K ε ) .
Suppose Δ = m − a p > H a K ε \Delta= m-ap > H_aK\varepsilon Δ = m − a p > H a K ε , for a sufficiently large H a H_a H a . The upper buyers’ middle expenditure is O a ( K ε + 1 / H a ) O_a(K\varepsilon+ 1/H_a) O a ( K ε + 1/ H a ) , and is at most one for large H a H_a H a and small K 2 ε K^2\varepsilon K 2 ε . The lower bound on p p p gives m − r F ≥ Δ − O a ( K ε ) m-r_F \ge\Delta- O_a(K\varepsilon) m − r F ≥ Δ − O a ( K ε ) , so the floor population’s middle expenditure is also at most one. Lower links contribute at most b v ( 1 + ε ) b_v(1+\varepsilon) b v ( 1 + ε ) and unapproved buyers at most ζ \zeta ζ . These cannot cover
m S M ≥ a L S M − O a ( K 2 ε ) > c v + 10 − O a ( K 2 ε ) , mS_M \ge aLS_M - O_a(K^2\varepsilon) > c_v + 10 - O_a(K^2\varepsilon), m S M ≥ a L S M − O a ( K 2 ε ) > c v + 10 − O a ( K 2 ε ) ,
using c v > b + 1 ≥ b v c_v > b+1 \ge b_v c v > b + 1 ≥ b v . Thus ∣ m − a p ∣ = O a ( K ε ) |m-ap| = O_a(K\varepsilon) ∣ m − a p ∣ = O a ( K ε ) .
We next compare q q q with a m am am . Suppose first that Δ = q − a m > H a K ε \Delta= q-am > H_aK\varepsilon Δ = q − am > H a K ε . An optimal lower-link bundle uses middle goods and filler, and its dual gives low slack Δ / m ≥ c Δ \Delta/m \ge c\Delta Δ/ m ≥ c Δ . Since m ≥ r F − O a ( K ε ) m \ge r_F-O_a(K\varepsilon) m ≥ r F − O a ( K ε ) , the floor low slack has the same lower bound after increasing H a H_a H a . Their combined low quantity is at most one, whereas unapproved buyers receive at most ζ / q = O a ( ζ ) \zeta/q = O_a(\zeta) ζ / q = O a ( ζ ) low quantity. Outgoing wires receive at most o v K o_vK o v K . This contradicts S L = o v K + C S_L = o_vK+C S L = o v K + C and C ≥ 64 C \ge64 C ≥ 64 . Hence q ≤ a m + O a ( K ε ) q \le am + O_a(K\varepsilon) q ≤ am + O a ( K ε ) . Together with m = a p + O a ( K ε ) m = ap+O_a(K\varepsilon) m = a p + O a ( K ε ) and p ≤ r U / a + O a ( K ε ) p \le r_U/a+O_a(K\varepsilon) p ≤ r U / a + O a ( K ε ) , this gives q < 1 q<1 q < 1 for sufficiently small K 2 ε K^2\varepsilon K 2 ε .
For the reverse bound, suppose Δ = a m − q > H a K ε \Delta= am-q > H_aK\varepsilon Δ = am − q > H a K ε . The lower bound q ≥ a r F − O a ( ε ) q \ge ar_F-O_a(\varepsilon) q ≥ a r F − O a ( ε ) implies m − r F ≥ Δ / a − O a ( ε ) m-r_F \ge\Delta/a-O_a(\varepsilon) m − r F ≥ Δ/ a − O a ( ε ) , so floor middle expenditure is at most one. For a lower link, q < 1 < m q<1<m q < 1 < m and its mixed dual is
β = 1 − a m − q ≥ c , μ = a m − q m − q ≥ c Δ . \beta= \frac{1-a}{m-q} \ge c,\qquad\mu= \frac{am-q}{m-q} \ge c\Delta. β = m − q 1 − a ≥ c , μ = m − q am − q ≥ c Δ.
Its unapproved quantity is O a ( ε / Δ ) O_a(\varepsilon/\Delta) O a ( ε /Δ ) . The row and budget bounds therefore limit its middle expenditure to
m m − q ( 1 − q + O a ( ε + ε / Δ ) ) ≤ 1 1 − a ( 1 − q + O a ( ε + ε / Δ ) ) = O a ( 1 / K + K ε + ε / Δ ) . \frac{m}{m-q}(1-q+O_a(\varepsilon+\varepsilon/\Delta)) \le\frac{1}{1-a}(1-q+O_a(\varepsilon+\varepsilon/\Delta)) = O_a(1/K+K\varepsilon+\varepsilon/\Delta). m − q m ( 1 − q + O a ( ε + ε /Δ )) ≤ 1 − a 1 ( 1 − q + O a ( ε + ε /Δ )) = O a ( 1/ K + K ε + ε /Δ ) .
There are only b v = O a ( 1 ) b_v = O_a(1) b v = O a ( 1 ) lower links, so this is below one in total for large K K K . Upper buyers spend at most c v ( 1 + ε ) c_v(1+\varepsilon) c v ( 1 + ε ) and unapproved buyers at most ζ \zeta ζ . Together, these expenditures are less than the required revenue m S M > c v + 10 − O a ( K 2 ε ) mS_M > c_v+10-O_a(K^2\varepsilon) m S M > c v + 10 − O a ( K 2 ε ) , a contradiction. Thus ∣ q − a m ∣ = O a ( K ε ) |q-am| = O_a(K\varepsilon) ∣ q − am ∣ = O a ( K ε ) .
Combining this bound with ∣ m − a p ∣ = O a ( K ε ) |m-ap| = O_a(K\varepsilon) ∣ m − a p ∣ = O a ( K ε ) gives ∣ q − a 2 p ∣ = O a ( K ε ) |q-a^2p| = O_a(K\varepsilon) ∣ q − a 2 p ∣ = O a ( K ε ) . The reference bound and 1 / S U R = O a ( η / K ) 1/S_U^R = O_a(\eta/K) 1/ S U R = O a ( η / K ) imply r U / a ≤ U + η + O a ( ε ) + O a ( ζ η / K ) ≤ U + 2 η + O a ( ε ) r_U/a \le U+\eta+O_a(\varepsilon)+O_a(\zeta\eta/K) \le U+2\eta+O_a(\varepsilon) r U / a ≤ U + η + O a ( ε ) + O a ( ζ η / K ) ≤ U + 2 η + O a ( ε ) . Together with r F / a − O a ( K ε ) ≤ p ≤ r U / a + O a ( K ε ) r_F/a-O_a(K\varepsilon) \le p \le r_U/a+O_a(K\varepsilon) r F / a − O a ( K ε ) ≤ p ≤ r U / a + O a ( K ε ) , this gives the stated interval for p v p_v p v . □
Lemma B.5 (Approximate local accounting). Suppose W v ≤ ζ W_v \le\zeta W v ≤ ζ for every u ∈ B 2 ( v ) u \in B_2(v) u ∈ B 2 ( v ) . Under the stated small-error conditions, evaluate the rational wire payments (13) and residual (16) at the ideal low and middle prices a 2 p u , a p u a^2p_u, ap_u a 2 p u , a p u , keeping the actual high prices p u p_u p u . Denote this residual by Φ v ( p ) \Phi_v(p) Φ v ( p ) and abbreviate it to Φ v \Phi_v Φ v in the estimates below. Let W v W_v W v and V v V_v V v be the actual approved expenditures of floor and upper buyers, respectively, on the three targets of v v v . Then
Φ v = W v + ( V v − c v ) + O a ( K 2 ε + ζ ) , (33) \Phi_v = W_v + (V_v-c_v) + O_a(K^2\varepsilon+\zeta), \tag*{(33)} Φ v = W v + ( V v − c v ) + O a ( K 2 ε + ζ ) , (33) ∣ Φ v 2 − ( ∑ u → v z u − 1 2 ) ∣ ≤ O a ( 1 / K + τ + K 2 ε ) . (34) \left|\frac{\Phi_v}{2} - \left(\sum_{u\to v} z_u-\frac{1}{2}\right)\right| \le O_a(1/K+\tau+K^2\varepsilon). \tag*{(34)} 2 Φ v − ( u → v ∑ z u − 2 1 ) ≤ O a ( 1/ K + τ + K 2 ε ) . (34)
Proof. Every incoming neighbor of v v v or of a neighbor of v v v lies in B 2 ( v ) B_2(v) B 2 ( v ) . Lemma B.4 therefore applies at both endpoints of every wire incident to v v v .
For each such wire, both optimal dual multipliers are bounded below by positive constants. Lemma B.1 gives approved quantity and expenditure 1 + O a ( ε ) 1 + O_a(\varepsilon) 1 + O a ( ε ) per buyer. Solving for the low and high quantities then gives expenditures within O a ( ε ) O_a(\varepsilon) O a ( ε ) of the exact mixed-demand payments at the actual endpoint prices. The denominators are bounded away from zero. Replacing the source low price q u q_u q u by a 2 p u a^2p_u a 2 p u changes each buyer’s payment by O a ( K ε ) O_a(K\varepsilon) O a ( K ε ) , and the whole population’s payment by O a ( K 2 ε ) O_a(K^2\varepsilon) O a ( K 2 ε ) .
The actual target revenue is q v S L + m v S M + p v S H q_vS_L + m_vS_M + p_vS_H q v S L + m v S M + p v S H . Replacing q v , m v q_v,m_v q v , m v by a 2 p v , a p v a^2p_v,ap_v a 2 p v , a p v changes this by O a ( K 2 ε ) O_a(K^2\varepsilon) O a ( K 2 ε ) and yields the ideal revenue R v R_v R v used in (16) . Each lower link has a bounded-price utility-one option and the uniform utility gap, so its dual β \beta β is bounded below. Its approved expenditure is therefore 1 + O a ( ε ) 1 + O_a(\varepsilon) 1 + O a ( ε ) ; the whole lower population contributes b v + O a ( ε ) b_v + O_a(\varepsilon) b v + O a ( ε ) . Actual column clearing, the wire comparison, and at most ζ \zeta ζ unapproved target expenditure now give (33) .
To prove the threshold expansion, apply identity (18) to these prices. The approximate price relations give
− O a ( K 2 ε ) ≤ t u ≤ 1 + 2 τ + O a ( K 2 ε ) , ∣ t u − z u ∣ = O a ( τ + K 2 ε ) . -O_a(K^2\varepsilon) \le t_u \le1 + 2\tau+ O_a(K^2\varepsilon), \qquad|t_u-z_u| = O_a(\tau+ K^2\varepsilon). − O a ( K 2 ε ) ≤ t u ≤ 1 + 2 τ + O a ( K 2 ε ) , ∣ t u − z u ∣ = O a ( τ + K 2 ε ) .
For each incident edge, its ideal payment is I u v = 3 − 2 t u + e u v I_{uv} = 3 - 2t_u + e_{uv} I uv = 3 − 2 t u + e uv , with
e u v = ( 3 − 2 t u ) a 2 ( p u − p v ) p v − a 2 p u . e_{uv} = (3 - 2t_u)\frac{a^2(p_u-p_v)}{p_v-a^2p_u}. e uv = ( 3 − 2 t u ) p v − a 2 p u a 2 ( p u − p v ) .
The extended price interval gives p u − p v = O a ( w ) p_u-p_v = O_a(w) p u − p v = O a ( w ) and 3 − 2 t u = O a ( 1 ) 3 - 2t_u = O_a(1) 3 − 2 t u = O a ( 1 ) , while p v − a 2 p u p_v-a^2p_u p v − a 2 p u is bounded away from zero. Thus e u v = O a ( 1 / K ) e_{uv} = O_a(1/K) e uv = O a ( 1/ K ) . There are at most four incident edge contributions to e v e_v e v , and (18) becomes Φ v = 2 ∑ u → v t u − 1 − e v \Phi_v = 2\sum_{u\to v}t_u - 1 - e_v Φ v = 2 ∑ u → v t u − 1 − e v . The displayed clipping bound now proves (34) . □
Proof of the local decoding lemma
Proof of Lemma 5.6. The hypothesis W u ≤ ζ W_u \le\zeta W u ≤ ζ on B 2 ( v ) B_2(v) B 2 ( v ) supplies all local estimates used below. Lemma B.3 only requires the module at its vertex; Lemma B.4 also requires the preliminary bounds at incoming neighbors. Consequently, the price relations hold at v v v and at both endpoints of each incident wire, and Lemma B.5 applies. No price bounds outside B 2 ( v ) B_2(v) B 2 ( v ) are used.
Fix a constant C a C_a C a large enough to dominate the error constants in these lemmas and in the slack estimates below. Take c a c_a c a small enough to satisfy their hypotheses, the endpoint-gap estimates below, and c a ≤ 1 / ( 24 C a ) c_a \le1/(24C_a) c a ≤ 1/ ( 24 C a ) . Increase K a K_a K a so that K a ≥ 8 C a / κ K_a \ge8C_a/\kappa K a ≥ 8 C a / κ . Under the hypotheses of the local decoding lemma,
C a ( 1 K + τ + K 2 ε κ + ζ ) ≤ κ 4 ≤ κ 2 . C_a\left(\frac{1}{K}+\tau+\frac{K^2\varepsilon}{\kappa}+\zeta\right)\le\frac{\kappa}{4}\le\frac{\kappa}{2}. C a ( K 1 + τ + κ K 2 ε + ζ ) ≤ 4 κ ≤ 2 κ .
In particular, the error in (34) is less than κ / 2 \kappa/2 κ /2 . We prove the two threshold implications separately.
Suppose ∑ u → v z u > 1 / 2 + κ \sum_{u\to v}z_u > 1/2+\kappa ∑ u → v z u > 1/2 + κ and z v > κ z_v>\kappa z v > κ . The threshold expansion gives Φ v > κ \Phi_v>\kappa Φ v > κ , while the decoder gives p v > L + κ w p_v>L+\kappa w p v > L + κ w . The price relations and reference upper bound imply
q v − a r v ≥ a 2 ( κ w − η ) − O a ( K ε + ζ η / K ) , q_v-ar_v \ge a^2(\kappa w-\eta)-O_a(K\varepsilon+\zeta\eta/K), q v − a r v ≥ a 2 ( κ w − η ) − O a ( K ε + ζ η / K ) ,
m v − r v ≥ a ( κ w − η ) − O a ( K ε + ζ η / K ) . m_v-r_v \ge a(\kappa w-\eta)-O_a(K\varepsilon+\zeta\eta/K). m v − r v ≥ a ( κ w − η ) − O a ( K ε + ζ η / K ) .
Because η = τ w \eta=\tau w η = τ w and w = Θ a ( 1 / K ) w=\Theta_a(1/K) w = Θ a ( 1/ K ) , the assumptions τ ≤ c a κ \tau\le c_a\kappa τ ≤ c a κ , K 2 ε ≤ c a κ 2 K^2\varepsilon\le c_a\kappa^2 K 2 ε ≤ c a κ 2 , and ζ ≤ c a κ \zeta\le c_a\kappa ζ ≤ c a κ make both differences at least a positive constant times κ w \kappa w κ w when c a c_a c a is sufficiently small. For the floor dual supplied by Lemma B.3 , β ≥ c > 0 \beta\ge c>0 β ≥ c > 0 , μ ≥ 0 \mu\ge0 μ ≥ 0 , and s R ≥ 0 s_R\ge0 s R ≥ 0 . The exact identities
s L = β ( q v − a r v ) + ( 1 − a ) μ + a s R , s M = β ( m v − r v ) + s R s_L=\beta(q_v-ar_v)+(1-a)\mu+as_R,\qquad s_M=\beta(m_v-r_v)+s_R s L = β ( q v − a r v ) + ( 1 − a ) μ + a s R , s M = β ( m v − r v ) + s R
therefore give s L , s M ≥ c κ w s_L, s_M \ge c\kappa w s L , s M ≥ c κ w . Lemma B.1 , the bounded target prices, and F v = O a ( K ) F_v = O_a(K) F v = O a ( K ) imply
W v = O a ( K 2 ε / κ ) , V v − c v ≤ c v ε = O a ( K ε ) . W_v = O_a(K^2\varepsilon/\kappa), \qquad V_v - c_v \le c_v\varepsilon= O_a(K\varepsilon). W v = O a ( K 2 ε / κ ) , V v − c v ≤ c v ε = O a ( K ε ) .
Substitution in (33) gives Φ v ≤ C a ( K 2 ε / κ + ζ ) < κ / 2 \Phi_v \le C_a(K^2\varepsilon/\kappa+ \zeta) < \kappa/2 Φ v ≤ C a ( K 2 ε / κ + ζ ) < κ /2 , contradicting Φ v > κ \Phi_v > \kappa Φ v > κ . This proves the first implication.
Now suppose ∑ u → v z u < 1 / 2 − κ \sum_{u\to v} z_u < 1/2 - \kappa ∑ u → v z u < 1/2 − κ and z v < 1 − κ z_v < 1-\kappa z v < 1 − κ . Then Φ v < − κ \Phi_v < -\kappa Φ v < − κ and p v < U − κ w p_v < U-\kappa w p v < U − κ w . The lower reference bound gives r v U − a p v ≥ a κ w − O a ( ε ) r^U_v - ap_v \ge a\kappa w - O_a(\varepsilon) r v U − a p v ≥ aκ w − O a ( ε ) . Choose the upper population’s optimal dual as μ U = 0 \mu_U = 0 μ U = 0 and β U = max { 1 / p v , a / m v , a / r v U } \beta_U = \max\{1/p_v, a/m_v, a/r^U_v\} β U = max { 1/ p v , a / m v , a / r v U } . Its reference slack satisfies
β U r v U − a ≥ r v U − a p v p v ≥ c κ w . \beta_U r^U_v-a \ge\frac{r^U_v-ap_v}{p_v} \ge c\kappa w. β U r v U − a ≥ p v r v U − a p v ≥ c κ w .
The upper population therefore spends O a ( K 2 ε / κ ) O_a(K^2\varepsilon/\kappa) O a ( K 2 ε / κ ) on its reference. Its total approved expenditure is c v + O a ( K ε ) c_v + O_a(K\varepsilon) c v + O a ( K ε ) by Lemma B.1 , so
V v − c v ≥ − O a ( K 2 ε / κ ) , W v ≥ 0. V_v-c_v \ge-O_a(K^2\varepsilon/\kappa), \qquad W_v \ge0. V v − c v ≥ − O a ( K 2 ε / κ ) , W v ≥ 0.
Equation (33) now gives Φ v ≥ − C a ( K 2 ε / κ + ζ ) > − κ / 2 \Phi_v \ge-C_a(K^2\varepsilon/\kappa+\zeta) > -\kappa/2 Φ v ≥ − C a ( K 2 ε / κ + ζ ) > − κ /2 , contradicting Φ v < − κ \Phi_v < -\kappa Φ v < − κ . This proves the second implication. □ \square □
Rational approximate witnesses
Proof of Lemma 4.11. Take a normalized exact equilibrium ( p , x ) (p,x) ( p , x ) with minimum-expenditure tie-breaking, supplied by [9 Theorem 5.1, conference version] . Clearing and the budget constraints give ∑ j p j ≤ N \sum_j p_j \le N ∑ j p j ≤ N . Put Q = ⌈ ( N + 1 ) / ε ⌉ Q=\lceil(N+1)/\varepsilon\rceil Q = ⌈( N + 1 ) / ε ⌉ and p j ′ = ⌊ Q p j ⌋ / Q p'_j=\lfloor Qp_j\rfloor/Q p j ′ = ⌊ Q p j ⌋ / Q . A zero-price good remains free.
Round x x x to a doubly stochastic matrix x ′ x' x ′ with entries in Q − 1 Z Q^{-1}\mathbb{Z} Q − 1 Z and ∣ x i j ′ − x i j ∣ ≤ 1 / Q |x'_{ij}-x_{ij}|\le1/Q ∣ x ij ′ − x ij ∣ ≤ 1/ Q . Such a matrix exists by integrality of the transportation problem with row and column sums Q Q Q and bounds ⌊ Q x i j ⌋ ≤ y i j ≤ ⌈ Q x i j ⌉ \lfloor Qx_{ij}\rfloor\le y_{ij}\le\lceil Qx_{ij}\rceil ⌊ Q x ij ⌋ ≤ y ij ≤ ⌈ Q x ij ⌉ : Q x Qx Q x is feasible, so an integral feasible y y y gives x ′ = y / Q x'=y/Q x ′ = y / Q . The rounding errors satisfy
p ′ ⋅ x i ′ ≤ 1 + N Q , U i ( x i ′ ) ≥ V i ( p ) − N Q . p'\cdot x'_i\le1+\frac{N}{Q},\qquad U_i(x'_i)\ge V_i(p)-\frac{N}{Q}. p ′ ⋅ x i ′ ≤ 1 + Q N , U i ( x i ′ ) ≥ V i ( p ) − Q N .
A unit bundle affordable at p ′ p' p ′ costs at most 1 + 1 / Q 1+1/Q 1 + 1/ Q at p p p . Scaling it by 1 / ( 1 + 1 / Q ) 1/(1+1/Q) 1/ ( 1 + 1/ Q ) and adding free filler loses at most 1 / Q 1/Q 1/ Q utility. Hence V i ( p ′ ) ≤ V i ( p ) + 1 / Q V_i(p')\le V_i(p)+1/Q V i ( p ′ ) ≤ V i ( p ) + 1/ Q , and
U i ( x i ′ ) ≥ V i ( p ′ ) − N + 1 Q . U_i(x'_i)\ge V_i(p')-\frac{N+1}{Q}. U i ( x i ′ ) ≥ V i ( p ′ ) − Q N + 1 .
Both errors are at most ε \varepsilon ε . Row and column sums remain exact, and prices remain normalized. Finally, Q = O ( N / ε ) Q=O(N/\varepsilon) Q = O ( N / ε ) and p j ′ ≤ N p'_j\le N p j ′ ≤ N , which gives the bit bound.
AI methodology statement
GPT-6 Astra helped simplify and calibrate the construction in § 3 –§ 4 , refine the rational-witness argument in Appendix § 10 , and improve the algorithm presentation and running-time analysis in § 6 . It also helped review the proofs, including the conditional hardness result in § 5 , check references, and improve exposition, notation, and figures. The authors take full responsibility for the correctness, originality, and integrity of the paper, including its references.