{"id":"eba56d32-d16a-486c-9d4c-59e7b0b13f6c","arxiv_id":"2606.06317","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Poly-time 1/e-approx algorithm for general HZ equilibria via stratification reduction to bi-valued case, plus 5x5 counterexample showing irrational exact equilibria for tri-valued utilities.","lead":"The paper gives a polynomial-time algorithm for a 1/e-approximate Hylland-Zeckhauser equilibrium in markets with arbitrary multi-valued utilities by mapping them to bi-valued instances. It also exhibits a small tri-valued instance whose exact equilibria are all irrational.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"Utility-stratification embedding must map equilibria such that 1/e factor is preserved exactly from the bi-valued exact solution","rationale":"The reader's weakest assumption correctly isolates the single step whose failure would invalidate the polynomial-time claim. The irrationality result is a separate, self-contained statement about a concrete 5x5 instance and does not affect the algorithmic result. Because the embedding argument is the only non-obvious reduction step and is not accompanied by an equation-level derivation in the provided abstract, the verdict remains CONDITIONAL pending verification of that step.","tokens_in":1698,"tokens_out":375,"duration_ms":16445,"concrete_test":"Take the smallest non-trivial multi-valued instance (e.g., 2 agents, 2 items, utilities in {0, 0.3, 1}); construct the stratified bi-valued instance exactly as described in the paper; compute its exact HZ equilibrium via the known bi-valued solver; map the resulting prices and allocations back to the original instance and measure the approximation ratio directly against the definition of HZ equilibrium; if the ratio is worse than 1/e on this instance the transfer argument does not hold.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central algorithmic claim rests on the stratification construction embedding an arbitrary multi-valued instance into a structured bi-valued market so that an exact HZ equilibrium of the latter yields a 1/e-approximate equilibrium of the former. The abstract states that this embedding lets the algorithm invoke the Vazirani-Yannakakis exact solver for bi-valued markets, but supplies no explicit statement of the distance or scaling between the two equilibrium notions. If the embedding distorts the utility thresholds or the market-clearing conditions by more than a constant factor that is independent of the instance size, the 1/e guarantee fails to transfer.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1812,"tokens_out":508,"duration_ms":9445,"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":[{"comment":"§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.","section":"§3"},{"comment":"§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).","section":"§4"}],"minor_comments":[{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"§3"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"[§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."},{"response":"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_made":"yes","referee_comment":"[§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)."}],"tokens_in":1346,"tokens_out":488,"duration_ms":14528,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The two things to know are the 1/e approximation algorithm for arbitrary multi-valued utilities and the 5x5 tri-valued instance where every equilibrium is irrational. Both are presented as firsts relative to the bi-valued exact results in the literature.\n\nThe approximation comes from a utility-stratification step that turns a general instance into a structured bi-valued market, then invokes the Vazirani-Yannakakis exact solver on the latter. The irrationality result is a concrete 5x5 market with utilities restricted to {0, 1/2, 1} whose equilibria all require irrational prices or allocations. The example is small enough to be verifiable by hand or machine, which is useful.\n\nThe construction itself looks like the main technical lift. If the stratification preserves the 1/e factor without instance-dependent distortion in the clearing conditions or utility thresholds, the reduction works. The abstract states that it does, but the letter should flag that the distance between the embedded equilibrium and the original needs to be bounded by a constant independent of n. The stress-test note on this point is reasonable to raise until the proof is read.\n\nNo circularity or self-referential fitting appears in the claims. The citation pattern stays within the relevant computational market design line. The irrationality example is a clean negative result that stands on its own.\n\nThis is for people working on equilibrium computation in assignment markets or approximation algorithms for fixed-point problems. A reader who already knows the bi-valued case will see the extension and the barrier clearly. The paper is worth sending to referees because the claims are specific, the example is falsifiable, and the algorithmic reduction is a concrete technique even if the constant needs tightening in revision.","headline":"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.","tokens_in":2309,"tokens_out":435,"would_cite":false,"duration_ms":11089,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"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.","keywords":["Hylland-Zeckhauser equilibria","approximation algorithms","market equilibria","irrational equilibria","computational game theory","one-sided matching"],"falsifier":"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.","tokens_in":2576,"feed_emoji":"📊","tokens_out":703,"duration_ms":11875,"temperature":0.7,"pith_summary":"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.","feed_headline":"Poly-time 1/e approximation for any HZ equilibrium","feed_subtitle":"Exact solutions turn irrational with three utility values in a 5x5 market.","key_machinery":"The utility-stratification construction that embeds a multi-valued market into a structured bi-valued instance while preserving the 1/e approximation guarantee.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["1/e HZ approx in poly time for arbitrary utilities","5x5 tri-valued HZ yields irrational equilibria only","Stratify utilities to reduce HZ to bi-valued exact","Rationality fails in HZ beyond two utility values"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The embedding of any multi-valued instance into a bi-valued instance preserves the 1/e approximation factor.","fun_headline_variants_meta":{"raw":{"variants":["1/e HZ approx in poly time for arbitrary utilities","5x5 tri-valued HZ yields irrational equilibria only","Stratify utilities to reduce HZ to bi-valued exact","Rationality fails in HZ beyond two utility values"]},"model":"grok-4.3","cost_usd":0.0046,"raw_usage":{"total_tokens":2257,"prompt_tokens":619,"num_sources_used":0,"completion_tokens":60,"cost_in_usd_ticks":45999500,"prompt_tokens_details":{"text_tokens":619,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1578,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":619,"tokens_out":60,"duration_ms":10092,"temperature":1.0,"reasoning_tokens":1578,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-27T23:05:46.310562+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}