PaperlayerView exact revision on arXiv

Source-linked AI summary

Exploring the Tractability Frontier of Hylland-Zeckhauser Models

Ioannis Panageas, Avi Shein, Shayan Taherijam, Vijay V. Vazirani

arXiv:2610.35848v1cs.GT

TL;DR

The tractability of HZ equilibrium computation between bi-valued and four-valued utilities leaves open whether three common utility values suffice for hardness. The paper studies linear three-value utilities and concave utilities with common marginal slopes, proving hardness for the former and polynomial-time exact solvability for the two-slope case. It also relates constant-accuracy hardness on its constructed family to PCP for PPAD.

  • Problem

    The tractability boundary between bi-valued HZ utilities and the known four-value hardness result leaves open whether three common utility values already suffice for PPAD-hardness.

    Source: §7 · p. 58

  • Method

    The paper studies linear utilities with a third value and separable concave utilities with common marginal slopes, using price-encoding market gadgets and an increasing-price algorithm.

    Source: §1 · p. 3, §1.2 · p. 7

  • Results

    For every fixed rational a in (0, 1), normalized additive ε∗(a)/N-equilibrium computation is PPAD-hard over common utilities {0, a, 1}; exact equilibrium computation is polynomial-time with two common marginal slopes.

    Source: §7 · p. 58

  • Takeaways & Limitations

    Three common utility values and three common marginal slopes are hard cases, while two common marginal slopes remain exactly tractable; under PCP for PPAD, general {0, a, 1} markets admit no PTAS unless PPAD ⊆ P.

    Source: §7 · p. 58

    The quantitative hardness construction fixes its parameters before the input graph and ultimately fixes τ as a rational constant depending on a.

    Source: §4.5 · p. 26

Abstract

from arXiv · show

The Hylland-Zeckhauser (HZ) mechanism provides a market-based approach to one-sided matching, making efficient equilibrium computation central to its implementation. Bi-valued utilities admit a strongly polynomial-time algorithm [VY], whereas with four values per buyer, the problem is PPAD-hard under inverse polynomial approximation [CCPY]. To understand the tractability boundary, we study two extensions of the bi-valued case: a third linear utility value and separable concave utilities with two common marginal slopes. For every fixed rational $a\in(0,1)$, we prove that computing a normalized additive $\varepsilon_{*}(a)/N$-equilibrium in an $N$-buyer HZ market is PPAD-hard for some constant $\varepsilon_{*}(a)>0$, even when all utilities belong to the same prescribed set $\{0,a,1\}$. This resolves the main question left open by [VY, CCPY]: whether three utility values already suffice for PPAD-hardness. Using the same market gadgets, we show that hardness at a specified constant accuracy on the recognizable family generated by our construction is equivalent to the PCP-for-PPAD conjecture. Consequently, assuming that conjecture, general markets over $\{0,a,1\}$ admit no PTAS unless $\mathrm{PPAD}\subseteq\mathrm{P}$. For the concave extension, we compute an exact equilibrium in polynomial time with two marginal slopes common across goods for each buyer and arbitrary rational buyer--good breakpoints. The algorithm selects a cheapest utility-maximizing bundle for each buyer. With three common marginal slopes, suitable breakpoints encode the three valued linear case, yielding PPAD-hardness. Thus, our paper identifies two thresholds separating tractable and intractable cases of HZ models with utility functions specified by utility values or marginal slopes. In both cases, the tractability threshold lies between two and three.

1 Introduction

The paper studies whether adding a third utility value or allowing diminishing marginal utility changes the tractability of Hylland–Zeckhauser markets. It establishes hardness for common three-value utilities, while identifying a polynomial-time exact algorithm for concave utilities with two common marginal slopes.

1.3 Further related work

  • Prior work gives a strongly polynomial algorithm for at most two utility values per buyer and PPAD-hardness with at most four values per buyer [CCPY22], leaving the three-value case open.The cited four-value hardness concerns inverse-polynomial approximation.Source: §1 · p. 3

1 Introduction

  • The paper separates the effects of adding a third linear utility value and imposing diminishing returns, with both extensions containing the tractable bi-valued case.In the concave extension, each buyer has two marginal slopes shared across goods but may have buyer–good-specific breakpoints.Source: §1 · p. 3, §1.1 · p. 4

1.1 Our results

  • For every fixed rational a in (0, 1), computing a normalized additive ε∗(a)/N-equilibrium is PPAD-hard even when all buyers share utilities {0, a, 1}.The construction also limits the number of buyers who value any good positively to a constant depending on a.Source: §1.1 · p. 3
  • Constant-accuracy hardness on the recognizable constructed family is equivalent to the polynomial-time PCP-for-PPAD formulation, and that conjecture rules out a PTAS for general {0, a, 1} markets unless PPAD ⊆ P.The converse equivalence is for the constructed family at the specified accuracy.Source: §1.1 · p. 4
  • With two marginal slopes common across goods for each buyer, an exact normalized equilibrium is computable in polynomial time for rational inputs and arbitrary buyer–good breakpoints.Each buyer receives a minimum-expenditure bundle among her utility-maximizing affordable bundles.Source: §1.1 · p. 4
  • Three common slopes 1, a, 0 yield PPAD-hardness because suitable breakpoints encode the three-valued linear case.The breakpoint pairs (0, 0), (0, 1), and (1, 1) encode per-unit values 0, a, and 1 on [0, 1].Source: §1.1 · p. 4, §1.2 · p. 7

1.2 Technical overview

  • The reduction encodes threshold-game variables in prices and uses wire buyers to transfer effects between vertices; common three-value utilities require new price relations that force mixing.The construction also uses revenue cancellation to enforce threshold behavior.Source: §1.2 · pp. 5–6

1.3 Further related work

  • The paper distinguishes its budget and utility error guarantees from prior approximate envy guarantees in matching markets.It also situates the two-slope algorithm as an extension of the increasing-price HZ method.Source: §1.3 · p. 7

2 Preliminaries

The preliminaries define a bounded-degree threshold game as the source problem and normalized HZ equilibrium as the target. They also establish how group-price demand can be analyzed using filler and linear-programming demand facts.

2.1 The source problem: a threshold game [PP21]

  • In the threshold game, each vertex receives a value in [0, 1] that must be near zero or one when its incoming sum is sufficiently above or below the threshold; finding a solution is PPAD-complete even with both degrees at most two.The reduction must recover a threshold solution from every permitted equilibrium output.Source: §2.1 · p. 8

2.2 The target problem: HZ equilibrium

  • A normalized exact HZ equilibrium pairs a feasible allocation with minimum price zero, where each buyer’s bundle costs at most one and attains her budget-one optimal value.An additive ε-equilibrium relaxes the buyer-specific budget and utility conditions; ε = 0 gives the exact case.Source: §2.2 · p. 9

2.3 Groups, approval, and notation

  • A group is a set of distinct unit-supply goods, and the construction fixes its parameters before the input graph while bounded degrees keep buyers and goods per vertex constant.All constructed groups are disjoint; a buyer approves a good exactly when its utility is positive.Source: §2.3 · p. 10

2.4 Optimal purchases at group prices

  • For individual demand, unapproved goods can be replaced by free filler without changing optimal utility, and buyers with two approved groups may demand both when quantity and budget constraints bind.The two-group demand cases depend on the relative prices and utility ratio.Source: §2.4 · pp. 10–11

3 The market construction

The construction encodes a threshold-game value at each vertex through linked groups of goods, reference prices, and edge-connected buyers. Its price and revenue constraints are designed so approximate market equilibria decode to threshold solutions.

3 The market construction

  • The market family fixes its parameters before the input graph, and balancing goods make the completed market have N buyers and N goods.For fixed parameters, each vertex and edge contributes a constant number of goods and buyers, independent of input size.Source: §3 · pp. 11–12, §3.1 · p. 13, §3.3 · p. 14

3.1 Goods and buyer populations

  • Three target groups per vertex encode its value through low, middle, and high prices, while floor and upper references constrain their range.Lower-link buyers value the low and middle groups at a and 1; upper buyers value the middle and high groups at a and 1.Source: §3.1 · p. 12
  • Each directed edge adds K wire buyers who value the source’s low goods at a and the destination’s high goods at 1.Thus edge-linked demand makes a vertex depend on its incoming neighbors’ values.Source: §3 · p. 11, §3.1 · p. 12

3.2 Group prices and the decoder

  • After equalizing prices within each group, the decoder maps the high-group price from [L, U] to 0 or 1 at the endpoints, clipping prices outside the interval.The group price is the minimum reported price among goods in that group.Source: §3.2 · pp. 13–14

3.3 The properties the construction must enforce

  • For fixed construction parameters, every normalized additive ε*(a)/N-equilibrium decodes to a threshold solution when K is sufficiently large.The construction uses price bounds and wire-payment revenue differences to enforce the threshold game's two responses.Source: §3.3 · p. 14

4 Equilibrium analysis and inverse polynomial hardness

The equilibrium analysis chooses market sizes so that equilibrium prices and revenues encode the threshold condition. The resulting decoding applies to exact equilibria and extends to approximate equilibria.

4 Equilibrium analysis and inverse polynomial hardness

  • The chosen group supplies and buyer counts ensure every permitted equilibrium decodes to a threshold solution.For exact equilibria, reference-price bounds and market clearing force qv = a mv = a²pv, after which wire payments and target revenues yield the threshold condition.Source: §4 · p. 14
  • The analysis extends the exact decoding argument to approximate equilibria.The construction's multiplicities are chosen independently of any equilibrium.Source: §4 · pp. 14–15
  • The exact analysis holds for 0 < τ ≤ κ/100 and every permitted K above an explicit bound.Multiplicities depend on a, τ, K, and local degrees, not on an equilibrium.Source: §4 · p. 15

4.1 Reference prices and the lower bounds on qv, mv

The analysis first bounds reference prices, then uses floor-buyer demand to constrain the low and middle target prices. These bounds also identify when floor buyers can spend on target goods.

4.1.1 Bounding the reference prices rFv, rUv

  • When a reference has more anchors than goods, its equilibrium price exceeds 1 and satisfies rS = A + E, with other-approver spending 0 ≤ E ≤ T.The reference-price construction uses anchor counts and supplies to place the rescaled floor and upper references near their target intervals.Source: §4.1.1 · p. 15

4.1.2 Choosing the floor population

  • If either qv < a rFv or mv < rFv, each floor buyer demands at least θ low-and-middle quantity, so Fvθ > SL + SM contradicts supply feasibility.The argument rules out a floor buyer bundle containing both reference goods and filler, yielding a positive lower bound on target quantity.Source: §4.1.2 · p. 16
  • Floor buyers spend on low goods only when qv = a rFv and on middle goods only when mv = rFv.Together with qv = a mv = a²pv, either target can receive floor spending only at pv = rFv/a.Source: §4.1.2 · p. 16

4.2 Forcing the price chain

The construction forces a price chain at each vertex, using supply and spending margins to constrain group prices and encode values.

4.2.1 A lower bound on pv

  • pv ≥ rFv/a ≥ L > 1 at every vertex, by the high-floor bound.Source: §4.2.1 · p. 17

4.2.2 Choosing the low supply and the encoding interval

  • Setting SL = ovK + C leaves more low supply than outgoing wires can absorb while keeping incoming wires’ high-group spending bounded.Source: §4.2.2 · pp. 17–18

4.2.3 The equality mv = apv and the ceiling on pv

  • The upper-link and ceiling arguments force mv = apv and pv ≤ rUv/a, using high-group demand and middle-supply margins.Source: §4.2.3 · p. 18
  • Every exact equilibrium satisfies qv = amv = a^2pv and qv < 1 < mv < pv after group prices are equalized.Source: §4.2.4 · p. 19

4.3 Wire payments and the choice of target sizes

Wire payments and target revenues are calibrated so that clearing at a vertex reflects its incoming encoded values, with controlled error.

4.3.1 The payment carried by one wire

  • Each wire buyer spends her full budget across the source low group Lu and destination high group Hv, with quantities determined by their prices.Source: §4.3.1 · p. 20

The error satisfies

  • The wire-payment error measures deviation from the source-price term 3 − 2(pu − L)/(U − L); a narrow price interval limits destination-price dependence.Source: §4.3.1 · p. 20

4.3.2 Choosing supplies and counts for the threshold condition

  • The chosen buyer counts and target supplies make the revenue difference’s leading term twice the incoming encoded sum minus one.Source: §4.3.2 · pp. 21–22

4.3.3 The sign of the revenue difference

4.3.4 Clipping and total error

  • The wire payment is not exactly source-dependent, and prices may lie in a clipping strip above U, so the proof bounds their combined error.Source: §4.3.4 · p. 23

4.4 Fixing the parameters and completing exact decoding

The parameter choices meet the construction’s integer, supply-margin, and decoding-error requirements, completing exact decoding.

4.4.3 Verification of the size and error bounds

  • The fixed parameters satisfy the strict margins used to force the price chain and ensure the balancing-good set is nonempty, completing the market with equal numbers of buyers and goods.Source: §4.4 · p. 23, §4.4.1 · p. 24, §4.4.3 · p. 26

4.4.1 A simultaneous choice of integer sizes

  • The simultaneous parameter choice yields positive integer supplies and buyer counts, reference intervals with 1 < L < U, and the required margins.Source: §4.4.1 · pp. 23–24

4.4.2 Exact decoding with slack

  • When the revenue difference is positive, exact accounting forces the floor switch and a decoded value at most τ; when negative, it forces the upper switch and decoded value 1.Source: §4.4.2 · p. 24

4.5 Quantitative robustness of the construction

The section quantifies how approximate demand can cause unapproved spending and shows how controlling it preserves local decoding. It bounds failed vertices uniformly and shows that inverse-linear accuracy forces every vertex to decode correctly.

4.5.1 Market size and the error in a buyer’s demand

  • The construction has N = Θa(Kn/η) buyers for an n-vertex graph; after fixing τ, this gives market size proportional to Kn with constants depending only on a.Here η = τ(U − L), and the bounds hold for sufficiently large admissible K.Source: §4.5 · p. 26, §4.5.1 · p. 27

4.5.2 Bounding total unapproved expenditure

  • For sufficiently large admissible K, every normalized additive ε-equilibrium with ε ≤ min{ca, 1/(CaK)} has groups valued at one priced above 1 + da, buyer optimal utility at most 1 − ga, and total zero-utility expenditure at most 2CaNε.The positive rational constants da, ga, ca, and Ca depend only on a.Source: §4.5.2 · pp. 27–29

4.5.3 Correct decoding in one neighborhood

  • After equalizing prices within groups in an ε-equilibrium, if every module within undirected distance two of a root receives at most ζ total expenditure from buyers who do not approve the purchased group, the original minimum-price decoder satisfies the root’s κ-threshold condition.The conclusion uses only these modules and their incident wire rows; prices at exterior endpoints may be arbitrary.Source: §4.5.3 · p. 29
  • The local lemma’s claims use only specified modules and incident wire rows, with estimates permitting arbitrary prices at exterior endpoints.Claim 3 concludes the lemma.Source: §4.5.3 · p. 33

4.5.4 A uniform bound on the number of failed vertices

  • For fixed rational a, uniform constants bound decoding failures across admissible K and graphs by combining local guarantees with a global expenditure estimate.Each high-expenditure module can affect at most 21 roots within distance two; the total expenditure bounds how many such modules occur.Source: §4.5.4 · pp. 33–34

4.5.5 Inverse-linear accuracy protects every vertex

  • At accuracy ε*(a)/N, every vertex in the constructed market satisfies both κ-threshold implications after decoding.The bound on failed vertices is at most 1/2, hence zero because the count is an integer.Source: §4.5.5 · p. 34

4.6 Completing the reduction

The section completes an unconditional search reduction by constructing polynomial-size three-valued HZ markets and decoding any permitted approximate equilibrium into a solution of the threshold instance. It also establishes that such approximate equilibria have polynomial-length rational witnesses.

4.6 Completing the reduction

  • Every HZ market with utilities in [0, 1] has a rational normalized additive ε-equilibrium with coordinate bit length O(1 + log N + log(1/ε)).The proof rounds prices and allocations while preserving exact row and column sums.Source: §4.6 · p. 35
  • The fixed-parameter construction uses only utilities 0, a, or 1 and has N = O_a(|V| + |E|), so its explicit market and decoder are polynomial-time computable.Each vertex and edge contributes only a fixed number of buyers and goods.Source: §4.6 · p. 35
  • Every normalized additive ε*(a)/N-equilibrium decodes to a solution of every threshold condition, yielding a polynomial-time search reduction from a PPAD-complete problem.The decoder uses polynomial-time rational arithmetic on reported prices.Source: §4.6 · p. 36

5 Constant error approximation and PCP for PPAD

The paper asks whether HZ hardness persists at constant accuracy, rather than the inverse-market-size accuracy established earlier. It relates constant-accuracy hardness on its constructed market family to PCP for PPAD through forward and reverse reductions.

5 Constant error approximation and PCP for PPAD

  • The conjecture states PPAD-hardness for satisfying all but a small constant fraction of generalized-circuit gates to fixed accuracy; the paper's constant-error result remains conditional on it.The cited conjecture's original formulation asks for a stronger quasilinear-size reduction.Source: §5 · p. 36
  • Constant-accuracy HZ hardness on the recognizable constructed family is equivalent to the PCP-for-PPAD conjecture.The forward implication also gives hardness for unrestricted utility matrices over {0, a, 1}.Source: §5 · pp. 36–37
  • The forward reduction composes weak Pure-Circuit-to-threshold reduction with the shared market construction and its quantitative robustness theorem.The argument extends the circuit construction to weak solutions by counting failures.Source: §5 · p. 36
  • The reverse reduction uses a weak generalized circuit and an allocation repair that converts some failed gates into an equilibrium guarantee for every buyer.The repair is specific to the constructed family.Source: §5 · pp. 36–37

5.1 From weak Pure-Circuit to weak threshold games

This section reduces weak Pure-Circuit instances to weak threshold games by translating gate constraints into bounded-degree graph gadgets and decoding assignments while controlling failures. Under PCP for PPAD, the resulting weak threshold problem is PPAD-hard.

5.1.1 Pure-Circuit and its weak variants

  • A Pure-Circuit instance uses NOR and PURIFY gates; weak δ-solutions may fail at most δ|G| gates, and input-once instances use each node as an input exactly once.NOR has two inputs and one output; PURIFY has one input and two outputs.Source: §5.1.1 · p. 37

5.1.2 Threshold games and weak threshold solutions

  • A weak (κ, ρ)-threshold solution may violate at most ρ|V| vertex constraints, with κ = 1/200 and graph degrees bounded by indegree two and outdegree one or two.The parameter ρ measures failed vertices, unlike δ, which measures failed circuit gates.Source: §5.1.2 · pp. 37–38

5.1.3 From the circuit to the threshold graph

  • The reduction creates one graph vertex per circuit node, adds NOR input-to-output edges, and replaces each PURIFY gate with four fresh private vertices and its gadget edges.The construction is performed directly on the gate list without evaluating or ordering the circuit.Source: §5.1.3 · p. 38

(b) PURIFY

  • PURIFY's threshold gadget uses four fresh vertices; the figure distinguishes these dashed orange nodes from original solid blue circuit nodes and shows its one-input, two-output roles.Only gate-contributed edges are shown; other incidences of original nodes are omitted.Source: Figure 3 · p. 39

5.1.4 Decoding and correctness of the circuit reduction

  • The decoder maps each original node through Dκ, and local gadget correctness lets failed threshold constraints be charged to disjoint gate blocks, giving conditional PPAD-hardness for weak threshold solutions.With ρ chosen at most δ/6, the bounded-size blocks control the fraction of decoded gate failures.Source: §5.1.4 · pp. 39–40

5.2 From weak threshold games to HZ

The forward reduction maps bounded-degree threshold games to a shared family of HZ markets and decodes sufficiently accurate equilibria back to threshold solutions. Under PCP for PPAD, it yields constant-accuracy hardness for this family.

5.2 From weak threshold games to HZ

  • The reduction constructs M(G; a, τa, K) with shared reference tolerance η = τa(U − L), leaving buyer populations, supplies, and figures unchanged.K is chosen so both reduction directions use the same accuracy.Source: §5.2 · p. 40
  • Every normalized additive saρ/K^2-equilibrium of M(G; a, τa, K) decodes to a (κ, ρ)-threshold solution.The guarantee holds for every rational 0 < ρ ≤ 1 and every sufficiently large admissible K.Source: §5.2 · p. 40
  • Under PCP for PPAD, the reduction gives constant-accuracy hardness because saρ/K^2 is fixed independently of graph size.The construction and decoder run in polynomial time, and N = Oa,K(n).Source: §5.2 · p. 40

5.3 Reverse reduction: from HZ to a weak circuit

This section establishes the reverse reduction from constructed HZ markets to weak generalized circuits, decoding approximate local revenue balance and repairing exceptional vertices to obtain prices and allocations with a utility guarantee for every buyer. It proves a regret bound below ε and shows that the constructed-market family can be recognized and decoded in polynomial time from its utility matrix.

5.3.4 Decoding the circuit and the required guarantees

  • The input utility matrix alone suffices: the reduction recovers a generating graph and labels, constructs a weak circuit, and decodes its solution into prices and an exceptional set.The exceptional set is computable and has size at most βn; vertices outside it satisfy the required price and revenue implications.Source: §5.3 · p. 41, §5.3.4 · p. 44

5.3.6 Correctness of the circuit and the repair

  • The repair preserves exact row sums, column sums, and budgets, with approximation confined to utility optimality.The reverse construction’s estimates hold uniformly for sufficiently large admissible K and 0 < τ ≤ κ/100.Source: §5.3 · p. 41, §5.3.4 · p. 44

5.3.1 Generalized circuits and their weak variants

  • Weak GCircuit+ permits a constant fraction of failed gates while keeping interval constraints mandatory, and converts to ordinary weak GCircuit with positive constant tolerances [DFHM26].The paper uses the equivalence between the weak GCircuit, weak Pure-Circuit, and GCircuit+ formulations of the PCP-for-PPAD conjecture [DFHM26].Source: §5.3.1 · p. 42

5.3.2 The price box and local revenue functions

  • The reverse reduction defines a price box and local rational revenue-balance functions on the entire box, without assuming that prices are an equilibrium.A circuit evaluates the local balance conditions, after which allocation repair turns approximate balance outside a small exceptional set into a guarantee for every buyer.Source: §5.3.2 · pp. 42–43

5.3.3 Constructing the circuit

  • Each vertex’s circuit block approximates its local revenue function by a constant-size piecewise-linear circuit over at most five price coordinates.The price is represented by a normalized coordinate in [0, 1], and the final clipped gate constrains the reported coordinate without requiring iteration to find a fixed point.Source: §5.3.3 · p. 43

5.3.4 Decoding the circuit and the required guarantees

  • Weak circuit solutions yield prices outside a small exceptional set that can be repaired into an approximate equilibrium for every buyer.The repair gives exact row sums, column sums, and budgets; only utility optimality is approximate.Source: §5.3 · p. 41, §5.3.4 · p. 44

5.3.5 Constructing the allocation from the decoded prices

  • The allocation repair clears low, high, middle, and reference groups, then uses balancing goods to fill remaining row capacities and clear every unit-supply good.Expenditure assigned to a buyer population is split uniformly within that population.Source: §5.3.5 · pp. 44–46

5.3.6 Correctness of the circuit and the repair

  • With ε ≥ Q_a/K^3 and suitably chosen rational tolerances, every buyer's regret is below ε, with all computations having polynomial bit complexity.The remaining error terms are made smaller than ε by choosing the tolerances and enlarging the constant in the hypothesis as needed.Source: §5.3.6 · p. 49

5.3.7 Recovering the construction from the utility matrix

  • For fixed a, τ, and K, membership in C_a,τ,K and recovery of a generating graph and all group and population labels are decidable in polynomial time.The input is the utility matrix alone, whose rows and columns may be arbitrarily permuted.Source: §5.3.7 · p. 49
  • The recovery procedure identifies anchors, floor and upper populations, and links and wires from utility patterns, then checks graph degrees, supplies, counts, and multiplicities.It rejects unclassified rows or columns; the checks are necessary and sufficient to reconstruct the specified matrix.Source: §5.3.7 · p. 49

5.4 A common accuracy and the equivalence

The section calibrates a common accuracy for the forward and reverse reductions and proves an equivalence between PCP for PPAD and hardness on the recognizable constructed market family. Under the conjecture, constant-error hardness also holds for unrestricted input matrices over {0, a, 1}.

5.4 A common accuracy and the equivalence

  • For fixed τ and failure fraction ρ, the forward reduction allows error of order ρ/K^2, while allocation repair requires error at least of order K^-3; sufficiently large fixed K makes these requirements compatible.Source: §5.4 · p. 50
  • For every fixed rational a ∈ (0, 1), PCP for PPAD is equivalent to PPAD-hardness at a fixed accuracy on the recognizable family Ca,τa,K.For fixed admissible (ρ, K), the accuracy is ε0 from (47), and the market problem reduces in polynomial time to weak generalized circuit.Source: §5.4 · p. 51
  • Under PCP for PPAD, constant-error hardness extends to unrestricted input matrices over {0, a, 1}; the reverse implication is stated for the recognizable constructed family.The forward reduction maps threshold solutions to circuit assignments, while the reverse reduction recovers the graph and repairs a weak-circuit solution into an equilibrium.Source: §5.4 · pp. 51–52

6 Two common marginal slopes

The section gives a polynomial-time algorithm for exact normalized equilibria with two common marginal slopes and arbitrary rational buyer–good breakpoints. It then shows that allowing three common slopes recovers the hard three-value linear instances.

6 Two common marginal slopes

  • With two marginal slopes common across goods for each buyer, arbitrary buyer–good breakpoints specify where utility changes; normalization preserves utility-maximizing and cheapest maximizing bundles.When every breakpoint is 0 or 1, the normalized utilities are linear and bi-valued.Source: §6 · p. 52

6.1 The algorithm

  • The algorithm tests a common price for unpriced goods using a flow network whose capacities encode useful purchases and each buyer’s remaining budget and bundle quantity.It first assigns zero prices to free goods, then commits closed groups at increasing positive prices, and finally uses remaining free supply to complete bundles.Source: §6.1 · p. 53

6.2 Correctness

  • At each positive-price stage, the committed closed set is nonempty and fully allocated; surviving buyers receive their full thresholds, and any next price is strictly larger.There are at most N positive-price stages; the final filling step clears goods and completes bundles without changing utility or expenditure, and buyers receive optimal affordable bundles at minimum expenditure.Source: §6.2 · p. 55

6.3 Encoding lengths and running time

  • The algorithm’s prices, budgets, quantities, flows, and final allocations have polynomial encoding length, supporting its binary polynomial-time running time.A common denominator argument bounds encoding growth across at most N price stages.Source: §6.3 · pp. 56–57
  • The algorithm computes an exact normalized equilibrium with minimum-expenditure tie-breaking in binary polynomial time.It uses one initial maximum-flow computation, at most N price linear programs, and residual reachability searches, all on polynomial-size instances with polynomial-length rational data.Source: §6.2 · p. 55, §6.3 · p. 57

6.4 Three common marginal slopes

  • Three common slopes 1, a, 0 can encode the three-valued linear instances, so computing a normalized additive ε*(a)/N-equilibrium remains PPAD-hard.Suitable breakpoints preserve buyers’ utilities and demands, and the transformation has polynomial size.Source: §6.4 · pp. 57–58

7 Discussion

The discussion places the linear HZ tractability boundary between two and three utility values, and the concave-utility boundary between two and three common marginal slopes. It states a conditional consequence for general three-value markets and identifies unresolved extensions and approximation questions.

7 Discussion

  • For every fixed rational a in (0, 1), normalized additive ε*(a)/N-equilibrium computation is PPAD-hard even when all buyers share utilities {0, a, 1}.The construction fixes the intermediate value for everyone, so the reduction encodes through preference patterns rather than varying utility values.Source: §7 · p. 58
  • Two common marginal slopes permit exact equilibrium computation with arbitrary rational buyer–good breakpoints, while three common slopes 1, a, 0 recover hard linear instances.The tractability boundary concerns slopes shared across goods for each buyer, not arbitrary separable concave utilities with two pieces per good.Source: §7 · p. 58
  • Under PCP for PPAD, general markets over {0, a, 1} admit no PTAS unless PPAD ⊆ P; constant-accuracy hardness on the constructed family is equivalent to the conjecture’s polynomial-time formulation.The converse applies to the recognizable constructed family at the specified accuracy.Source: §7 · p. 58

Open questions

  • Whether constant-accuracy PPAD-hardness extends beyond the constructed family to all three-value markets with bounded positive-degree structure remains open.Such an extension would require a repair procedure preserving exact market clearing and unit quantities while ensuring approximate optimality for every buyer.Source: Open questions · pp. 58–59
  • For utilities {0, a, 1}, the cited construction gives an a(1 − a)-approximation, leaving open whether the guarantee can be improved, including below 1/4 when a = 1/2.The discussion also asks whether polynomial-time approximation is possible when only a fixed number of buyers use all three values.Source: Open questions · p. 59
Loading 2610.35848v1…