Pith. sign in

REVIEW 2 major objections 2 minor 20 references

Approximation and Irrationality in Hylland--Zeckhauser Equilibria

T0 review · 2 major / 2 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A polynomial-time algorithm computes 1/e-approximate Hylland-Zeckhauser equilibria for arbitrary multi-valued utilities by embedding them into bi-valued markets, but exact equilibria become irrational already with three utility values.

desk verdict The paper delivers a 1/e poly-time approx for general HZ via stratification to bi-valued plus a small explicit tri-valued irrationality example, but the embedding's approximation transfer is the part that needs the closest check. read the letter →

arxiv 2606.06317 v2 pith:XHQXDL3I submitted 2026-06-04 cs.GT

Yonglei Yan , Zhengyang Liu This is my paper · ORCID
classification cs.GT
keywords Hylland-Zeckhauserequilibriaapproximationalgorithmsmarketirrationalcomputationalgametheoryone-sidedmatching
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes a constant-factor approximation for computing Hylland-Zeckhauser equilibria when agents have general multi-valued utilities. It does so by reducing any such market to a specially structured bi-valued market on which an exact algorithm already exists, then lifting the solution back. The same work shows that exact equilibria lose their rational character at the next level of complexity: a concrete 5-by-5 market with utilities restricted to {0, 1/2, 1} forces every equilibrium price vector to be irrational. A reader cares because HZ equilibria are the canonical solution concept for one-sided matching markets with money, and these results separate what can be computed efficiently from what can be represented exactly.

What carries the argument

The utility-stratification construction that embeds a multi-valued market into a structured bi-valued instance while preserving the 1/e approximation guarantee.

What would settle it

Either exhibit a polynomial-time algorithm that returns a strictly better than 1/e approximation for some multi-valued instance, or exhibit a rational equilibrium for the specific 5-by-5 tri-valued instance given in the paper.

Watch

Extended reading notes

Core claim

For any instance with arbitrary utility values, a utility-stratification construction produces a bi-valued instance whose exact HZ equilibrium yields a 1/e-approximate equilibrium for the original market; the reduction runs in polynomial time. Separately, there exists a 5-by-5 instance whose utilities lie in {0, 1/2, 1} and whose every HZ equilibrium has at least one irrational coordinate.

Load-bearing premise

The embedding of any multi-valued instance into a bi-valued instance preserves the 1/e approximation factor.

Editorial extensions

If this is right

  • Exact HZ equilibria cannot be guaranteed to be rational once utilities take three distinct values.
  • Bi-valued markets remain the only regime in which exact equilibria are known to be computable in polynomial time.
  • Any future exact algorithm for tri-valued or richer instances must output algebraic numbers rather than rationals.
  • Approximation algorithms can safely treat the bi-valued case as a computational primitive.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Mechanism designers may need to accept approximate rather than exact clearing prices when agent preferences are expressed with more than two numbers.
  • The appearance of irrationality at five agents and five items suggests that symbolic or algebraic methods, rather than rational arithmetic, will be required for exact solutions in modestly sized markets.
  • It is open whether the 1/e factor can be improved while retaining polynomial time, or whether the stratification technique extends to other equilibrium notions such as competitive equilibria with indivisible goods.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper claims two main results on Hylland-Zeckhauser (HZ) equilibria: (1) a polynomial-time algorithm computing a 1/e-approximate HZ equilibrium for general multi-valued utilities via a utility-stratification embedding that reduces the problem to an exact solver for structured bi-valued instances (Vazirani-Yannakakis); (2) a 5×5 counterexample with utilities in {0, 1/2, 1} whose equilibria are all irrational, showing that rationality fails already for tri-valued utilities.

Significance. If the embedding construction and the 5×5 instance hold, the work supplies the first constant-factor approximation guarantee for general HZ markets and a concrete separation between bi-valued (exact, rational) and tri-valued (irrational) cases. This is a substantive contribution to the computational theory of market equilibria, particularly because it leverages an existing exact algorithm rather than developing a new one from scratch.

major comments (2)
  1. [§3] §3 (Utility Stratification): the claim that the embedding preserves a 1/e approximation factor requires an explicit bound showing that any exact HZ equilibrium of the constructed bi-valued instance maps back to a 1/e-approximate equilibrium of the original multi-valued instance; the current description leaves the scaling of prices and the clearing error under the stratification map unstated.
  2. [§4] §4 (Irrationality Counterexample): the 5×5 instance is asserted to have only irrational equilibria, but the manuscript must exhibit the explicit utility matrix, the system of equilibrium conditions, and the algebraic proof that all solutions have irrational coordinates (e.g., by showing the minimal polynomial is irreducible of degree >1).
minor comments (2)
  1. [Abstract] The abstract and introduction should clarify whether the 1/e guarantee is with respect to the standard additive or multiplicative notion of approximate market clearing used in the HZ literature.
  2. [§3] Notation for the stratification map (e.g., how utility levels are mapped to the bi-valued {0,1} instance) should be introduced with a small illustrative example before the general construction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The two major comments identify places where the manuscript would benefit from greater explicitness. We address each below and will incorporate the requested details in the revision.

read point-by-point responses

  1. Referee: [§3] §3 (Utility Stratification): the claim that the embedding preserves a 1/e approximation factor requires an explicit bound showing that any exact HZ equilibrium of the constructed bi-valued instance maps back to a 1/e-approximate equilibrium of the original multi-valued instance; the current description leaves the scaling of prices and the clearing error under the stratification map unstated.

    Authors: We agree that the mapping requires an explicit quantitative statement. The stratification embeds each original utility level into a distinct bi-valued layer with uniform price scaling. In the revised manuscript we will add Lemma 3.3, which states: if (p',x') is an exact HZ equilibrium of the constructed bi-valued instance, then the projected prices p and allocations x satisfy u_i(x_i) ≥ (1/e)·OPT_i for every agent i, with total market-clearing violation bounded by the number of strata. The proof tracks the price scaling factor (equal to 1) and uses the exact clearing of the bi-valued solver together with the harmonic-mean property of the 1/e guarantee. revision: yes

  2. Referee: [§4] §4 (Irrationality Counterexample): the 5×5 instance is asserted to have only irrational equilibria, but the manuscript must exhibit the explicit utility matrix, the system of equilibrium conditions, and the algebraic proof that all solutions have irrational coordinates (e.g., by showing the minimal polynomial is irreducible of degree >1).

    Authors: The 5×5 utility matrix appears in Section 4, but the algebraic verification is only outlined. We will expand the section to display the full matrix, write out the complete system of polynomial equations arising from market clearing and budget exhaustion, and supply the explicit algebraic argument: assuming a rational solution yields a quadratic equation whose discriminant is not a perfect square, hence the minimal polynomial over Q is irreducible of degree 2. This establishes that every equilibrium coordinate is irrational. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: reduction to external solver and explicit counterexample instance

full rationale

The claimed 1/e-approximation algorithm is obtained by an explicit utility-stratification embedding of a multi-valued market into a bi-valued instance, after which the paper invokes the independent Vazirani-Yannakakis exact solver for the latter; the approximation factor is asserted to transfer from this construction rather than from any fitted parameter or self-referential definition. The irrationality claim is witnessed by an explicit 5x5 instance with utilities in {0,1/2,1}. No load-bearing self-citation, self-definitional step, or renaming of a known result appears in the abstract or described derivation chain. The result is therefore self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the reduction and counterexample are asserted without visible supporting structure.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximation and Irrationality in Hylland--Zeckhauser Equilibria." pith.science (2026). https://pith.science/paper/XHQXDL3I

@misc{pith2026260606317,
  author       = {Pith},
  title        = {Pith review of: Approximation and Irrationality in Hylland--Zeckhauser Equilibria},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XHQXDL3I}},
  note         = {Machine review of arXiv:2606.06317}
}
abstract

We study the computation of Hylland--Zeckhauser (HZ) equilibria beyond the bi-valued setting. First, we give a polynomial-time algorithm that, for general multi-valued utilities, computes an $1/e$-approximate HZ equilibrium. This yields, to our knowledge, the first polynomial-time constant-error approximation guarantee for this setting. The key technical ingredient is a utility-stratification construction that embeds a multi-valued market into a structured bi-valued instance, allowing us to apply the exact algorithm of Vazirani and Yannakakis. Second, we show that the rational structure of exact equilibria breaks down already for tri-valued utilities: there exists a $5\times5$ HZ instance with utilities in $\{0,\frac12,1\}$ such that all of whose equilibria are irrational. Taken together, these results show that while the bi-valued case can be used as a base for approximation algorithms, rational exact equilibria cannot be guaranteed even for tri-valued utilities.

Figures

Figures reproduced from arXiv: 2606.06317 by the authors.

Figure 1
Figure 1. Illustration of the utility-stratification construction. Each utility level of an original agent induces a binary threshold type, and each original good is replicated W times. The resulting expanded market is bi-valued. Observe that the new HZ market constructed in this way is bi-valued: for every i ∈ [n], k ∈ [ti ], a ∈ [ni,k], the utilities of agent i (k,a) satisfy ui (k,a) ∈ {0, 1}. By Theorem 2.7, we can compute… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 4 canonical work pages

  1. [1]

    Journal of Political Economy , year = 1979, volume = 87, number = 2, pages =

    Aanund Hylland and Richard Zeckhauser , title =. Journal of Political Economy , year = 1979, volume = 87, number = 2, pages =

    1979

  2. [2]

    Vazirani and Mihalis Yannakakis , title =

    Vijay V. Vazirani and Mihalis Yannakakis , title =. doi:10.1137/23M157586X , pages =

    work page doi:10.1137/23m157586x

  3. [3]

    2026 , eprint=

    Hardness of Approximate Hylland-Zeckhauser Equilibria , author=. 2026 , eprint=

    2026

  4. [4]

    Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA) , year = 2022, pages =

    Thomas Chen and Xi Chen and Binghui Peng and Mihalis Yannakakis , title =. Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA) , year = 2022, pages =

    2022

  5. [5]

    Proceedings of the 2017 ACM Conference on Economics and Computation (EC) , year = 2017, pages =

    Saeed Alaei and Pooya Jalaly Khalilabadi and Eva Tardos , title =. Proceedings of the 2017 ACM Conference on Economics and Computation (EC) , year = 2017, pages =

    2017

  6. [6]

    A New Algorithm to Find a Point in Every Cell Defined by a Family of Polynomials , booktitle =

    Saugata Basu and Richard Pollack and Marie-Fran. A New Algorithm to Find a Point in Every Cell Defined by a Family of Polynomials , booktitle =

  7. [7]

    Econometrica , year = 1998, volume = 66, number = 3, pages =

    Ati̇la Abdulkadi̇roğlu and Tayfun Sönmez , title =. Econometrica , year = 1998, volume = 66, number = 3, pages =

    1998

  8. [8]

    Fair Division in the Internet Age , journal =

    Herv. Fair Division in the Internet Age , journal =. doi:10.1146/annurev-economics-080218-025559 , volume = 11, number = 1, pages =

    work page doi:10.1146/annurev-economics-080218-025559

Show all 20 references
  1. [9]

    A New Solution to the Random Assignment Problem , journal =

    Anna Bogomolnaia and Herv. A New Solution to the Random Assignment Problem , journal =

  2. [10]

    American Economic Review , volume = 111, number = 11, pages =

    Federico Echenique and Antonio Miralles and Jun Zhang , title =. American Economic Review , volume = 111, number = 11, pages =

  3. [11]

    1908.04336 , archiveprefix =

    Fairness and efficiency for probabilistic allocations with participation constraints , author =. 1908.04336 , archiveprefix =

    1908

  4. [12]

    2009.10320 , archiveprefix =

    One-Sided Matching Markets with Endowments: Equilibria and Algorithms , author =. 2009.10320 , archiveprefix =

    2009

  5. [13]

    Journal of Political Economy , year = 2011, volume = 119, number = 6, pages =

    Eric Budish , title =. Journal of Political Economy , year = 2011, volume = 119, number = 6, pages =

    2011

  6. [14]

    American Economic Journal: Microeconomics , year = 2018, volume = 10, number = 3, pages =

    Yinghua He and Antonio Miralles and Marek Pycia and Jianye Yan , title =. American Economic Journal: Microeconomics , year = 2018, volume = 10, number = 3, pages =

    2018

  7. [15]

    International Journal of Economic Theory , year = 2017, volume = 13, number = 4, pages =

    Phuong Le , title =. International Journal of Economic Theory , year = 2017, volume = 13, number = 4, pages =

    2017

  8. [16]

    Andy McLennan , title =

  9. [17]

    Games and Economic Behavior , volume=

    Public goods games in directed networks , author=. Games and Economic Behavior , volume=. 2023 , doi=

    2023

  10. [18]

    Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science , pages =

    Babichenko, Yakov and Papadimitriou, Christos and Rubinstein, Aviad , title =. Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science , pages =. 2016 , doi =

    2016

  11. [19]

    G. B. Dantzig , title =

  12. [20]

    V. Chv. Linear Programming , publisher =

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.