{"id":"473c49d4-33e3-40e4-a90b-4745c40bd496","arxiv_id":"2412.17134","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"HZ pricing equilibria and earnings equilibria are equivalent, so the Hylland-Zeckhauser framework carries over from goods to chores and mixed manna.","lead":"This paper extends the classic Hylland-Zeckhauser matching-market mechanism to chores and mixed manna, where items can be unpleasant. It shows that a pricing equilibrium and an earnings-based equilibrium coincide, and that several goods-only results transfer automatically.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's proof assumes pmax>1, but valid HZ equilibria can have pmax<=1; the theorem is true, but the printed construction is incomplete.","rationale":"The reader's weakest_assumption and my stress-test identify the same load-bearing issue: Theorem 5 divides by pmax-1 without proving pmax>1, and there are valid HZ equilibria with pmax<=1. I found the same two-agent, two-good instance, though the reader's statement that 'all HZ price vectors have pmax=1' is slightly overstrong: p=(0.5,0.5) is also an HZ equilibrium for the same allocation and has pmax<1. The essential point stands: for the canonical allocation in that instance, no supporting price vector has pmax>1, so the printed formula cannot be applied. I also checked the other identified issue, Lemma 6. The displayed equation has a sign error, but the intended inequality is correct: since y2-x2 = -(y1-x1), Pareto improvement gives u1.y2 = u1.x2 - u1.(y1-x1) <= u1.x2, which is exactly the direction the proof needs. Thus Lemma 6 is a typo, not a second load-bearing flaw. The utility-shifting arguments in Section 3 are sound: the proof of Lemma 4 correctly uses that both relevant bundles sum to 1, and the analogous earnings argument also works. The central equivalence is likely true and repairable by a piecewise-affine transform, so the paper should not be rejected; however, as printed, the proof of the central theorem is incomplete for a nonempty class of valid equilibria. This matches the reader's CONDITIONAL verdict, so I do not change the verdict.","tokens_in":10883,"tokens_out":18312,"duration_ms":170218,"concrete_test":"Instantiate Theorem 5 with A={1,2}, G={a,b}, u1=(1,0), u2=(0,1), x = (1,0),(0,1), p=(1,1). Verify that (x,p) satisfies Definition 1, then attempt to compute q_j=(pmax-p_j)/(pmax-1) and observe that the denominator is zero. Next test the repaired transform q_j=2-p_j, obtaining q=(1,1), and verify that (x,q) satisfies Definition 4. This separates a false theorem from an incomplete proof: the printed proof fails, while the equivalence relation still holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing gap is the normalization assumption in Theorem 5. The proof defines q_j = (pmax - p_j)/(pmax - 1), which is meaningful only when pmax > 1. No such normalization is established, and it does not hold for valid HZ equilibria. Example: two agents and two goods with u1=(1,0), u2=(0,1), allocation x = (1,0),(0,1), and prices p=(1,1). This is an HZ equilibrium: each agent spends exactly 1, receives utility 1, and every affordable bundle has cost at most 1 and utility at most 1, so the bundle is optimal and cheapest. Yet pmax = 1 and the formula divides by zero. The same allocation is also supported by p=(0.5,0.5), for which the formula yields q=(0,0), which fails the earnings condition q.x_i >= 1. For this fixed allocation, every supporting HZ price vector must have p1<=1 and p2<=1, because agent 1 must be able to afford a full unit of good 1 and agent 2 a full unit of good 2; hence no choice of HZ prices for this x gives pmax>1. The converse direction has the same issue: an earnings equilibrium with qmax=1, e.g. q=(1,1), makes the inverse formula undefined. The equivalence statement itself is true and can be repaired by a piecewise-affine transform, such as q_j = 2 - p_j when pmax<=1, but the construction printed in Theorem 5 does not cover valid instances. Since Theorem 6 relies on Theorem 5, the proof of earnings-equilibrium existence is incomplete as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper extends Hylland-Zeckhauser (HZ) matching-market mechanisms from goods to chores and mixed manna. It defines an HZ earnings equilibrium (Definition 4), proves that such equilibria are envy-free and Pareto-optimal (Theorems 3 and 4), and observes in Section 3 that adding agent-specific constants to all utilities preserves envy-freeness, Pareto-optimality, and both equilibrium notions. The central claim is Theorem 5: HZ pricing equilibria and HZ earnings equilibria are the same object up to a transformation of prices into wages. The paper also gives a polynomial-time algorithm for bivalued utilities (Theorem 7), an LP-based EF+PO algorithm for two agent types (Section 6), and counterexamples showing that two Nash-bargaining generalizations fail to be fair for chores (Section 7).","tokens_in":11141,"tokens_out":10720,"duration_ms":94209,"significance":"If the proof gaps are repaired, the paper is a useful and well-scoped contribution: it is the first systematic treatment of chores and mixed manna in one-sided cardinal matching markets, it gives a clean conceptual reduction from chores to goods via utility shifts, and it identifies an earnings-based equilibrium notion that is natural for chores and equivalent to the HZ equilibrium. Theorems 3 and 4, the shifting lemmas in Section 3, and the Section 7 counterexamples are straightforward and appear correct. The bivalued result correctly builds on known algorithms of Vazirani-Yannakakis and Bogomolnaia-Moulin. The main conceptual claim, however, is not proven as printed: the proof of Theorem 5 divides by pmax - 1 without handling pmax <= 1, and the two-type EF+PO algorithm in Section 6 rests on a sign error and a mismatched LP. These are repairable but load-bearing.","major_comments":[{"comment":"The transform q_j = (pmax - p_j)/(pmax - 1) is undefined when pmax = 1 and produces negative payments when pmax < 1, yet the proof never establishes that an HZ price vector with pmax > 1 exists. It does not exist for every HZ equilibrium: for two agents with u1=(1,0), u2=(0,1) and allocation x1=(1,0), x2=(0,1), both p=(1,1) and p=(1/2,1/2) are valid HZ prices, and every supporting price vector for this allocation has pmax <= 1 because each agent must be able to afford a full unit of their preferred good. The converse direction has the same issue when qmax = 1. The equivalence statement is plausibly true and can be repaired by a piecewise-affine transform (e.g., q_j = 1 for all j when pmax <= 1), but the printed construction does not cover valid instances. Since Theorem 6 and the bivalued earnings-equilibrium claim in Section 5 rely on Theorem 5, this gap is load-bearing.","section":"Section 4, Theorem 5"},{"comment":"The proof contains a sign error. The displayed chain u1·y2 = u1·x2 + u1·(y2 - x2) = u1·x2 + u1·(y1 - x1) >= u1·x2 is wrong: since y2 - x2 = x1 - y1, the second equality should have a minus sign, and the inequality should be reversed. The conclusion the proof needs is u1·y2 <= u1·x2, which follows after the correction, so the lemma statement appears true. As printed, however, the derivation does not prove the lemma. Lemma 6 is the step that turns an optimum of the envy-free polytope into a globally Pareto-optimal allocation, so the issue affects the polynomial-time EF+PO claim for two types.","section":"Section 6, Lemma 6"},{"comment":"The displayed LP enforces u_i·x_i >= u_i·x_i' for all agents i, i', but Definition 6 defines envy-freeness with demands as u_i·x_i/d_i >= u_i·x_i'/d_i'. The LP thus optimizes over a different feasible set, and its optimal solution need not be envy-free in the demand model. The fix is straightforward (divide both sides by the corresponding demands), but as printed the polynomial-time EF+PO result for two agent types is not supported.","section":"Section 6, LP formulation"}],"minor_comments":[{"comment":"There is a typo in the third paragraph: 'Our s is first paper' should be 'Ours is the first paper'.","section":"Introduction"},{"comment":"References [27] and [28] appear to be the same paper (He, Miralles, Pycia, and Yan); one duplicate should be removed or the citations should be merged.","section":"References"},{"comment":"In the LP, 'xij >= 0 for all i in a' uses a lowercase 'a' where the agent set A is meant.","section":"Section 6"},{"comment":"The phrase 'HZ envy-freeness' is imprecise; envy-freeness is a property of allocations, not of the HZ mechanism. Consider rewording to 'envy-freeness of the allocation x'.","section":"Section 3"},{"comment":"In the proof of Theorem 5, the definitions of pmax and qmax are given inline; since the normalization issue is central, the proof would benefit from explicitly stating the domain assumption (or handling the pmax <= 1 case separately) before the formula is introduced.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the scope of a theory/CS-GT journal and the main idea is attractive. The proof gaps in Theorem 5, Lemma 6, and the Section 6 LP are repairable, but they are central enough that the paper should not be accepted in its present form. The duplicate reference and a few typos should also be cleaned up."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper extends HZ matching markets to chores and mixed manna via two ideas: utility shifting (Section 3) and an affine price-wage transform (Theorem 5). The shifting observation is simple and correct—EF, PO, and HZ equilibria are invariant under adding agent-specific constants because every feasible bundle sums to one. That immediately gives HZ existence for arbitrary utilities, and it is a genuinely useful trick. The earnings equilibrium equivalence is the conceptual centerpiece, and the intended theorem is true, but the printed proof is incomplete. The transform q_j = (pmax - p_j)/(pmax - 1) divides by pmax-1, and the paper never shows pmax>1. There are valid HZ equilibria with pmax=1, e.g., two agents with u1=(1,0), u2=(0,1), x diagonal, p=(1,1). So the construction as printed does not cover all instances. A piecewise affine transform fixes it, but that repair is not in the manuscript. Lemma 6 has a sign error: y2 - x2 = -(y1 - x1), not +(y1 - x1), so the displayed chain is invalid. The lemma may still be true, but the proof needs rewriting. These are exactly the kind of errors a careful referee would catch, and they are repairable. The bivalued and two-type algorithms inherit from prior work and are fine; the Nash bargaining counterexamples are genuinely useful—they show why naive generalizations fail. The citation pattern looks reasonable, and the self-citations are to the authors' own algorithms where appropriate. If the two proof gaps are fixed, this is a solid contribution to matching-market theory. As it stands, it is a good paper with two load-bearing but fixable flaws. The paper is aimed at people working on HZ, fair division with chores, or pseudo-markets; they will get real value from Section 3 and the counterexamples. My recommendation: send it to peer review, with a referee asked to verify the two proofs. It does not deserve a desk reject.","headline":"Worth a serious referee: the utility-shifting idea is clean and the earnings equivalence is a real result, but the printed proofs of Theorem 5 and Lemma 6 have repairable gaps.","tokens_in":11761,"tokens_out":2400,"would_cite":true,"duration_ms":21269,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B26","91B68","91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper extends HZ matching markets from goods to chores and mixed manna, and proves the pricing-based and earnings-based equilibrium notions coincide.","keywords":["matching markets","chores","mixed manna","HZ equilibrium","earnings equilibrium","envy-freeness","Pareto-optimality","bivalued utilities"],"falsifier":"Consider the two-agent instance with utilities $u_1 = (1,0)$ and $u_2 = (0,1)$. Every HZ equilibrium in this instance has both prices equal to 1, so the transform $q_j = (1 - p_j)/(1 - 1)$ in the proof of Theorem 5 is undefined and the printed proof cannot convert this pricing equilibrium into an earnings equilibrium. Checking whether the equivalence statement still holds for such boundary equilibria, for example via a piecewise affine transform, would isolate the gap between the theorem and its proof.","tokens_in":10599,"feed_emoji":"🧹","tokens_out":9612,"duration_ms":75999,"temperature":0.7,"pith_summary":"This paper argues that matching markets, where every agent receives exactly one unit of allocation and every item is fully assigned, are a natural setting for fair division of chores and mixed manna. It shows that because each bundle sums to one, adding a constant to an agent's utilities preserves envy-freeness, Pareto-optimality, and both equilibrium notions, so goods-only results transfer to chores for free. Its central equivalence theorem states that the classic Hylland–Zeckhauser pricing equilibrium (agents spend one unit of fake money) and a newly formulated earnings equilibrium (agents must earn one unit of money by accepting chores) are the same object under an affine transform of prices into wages. The paper also provides polynomial-time EF+PO algorithms for bivalued utilities and for two agent types, and demonstrates with counterexamples that two natural Nash-bargaining extensions fail for chores.","feed_headline":"For chores, pricing and earnings equilibria coincide","feed_subtitle":"Utility shifting transfers goods-only matching results to chores and mixed manna, preserving fairness and efficiency.","key_machinery":"The central machinery has two parts: the utility-shifting operation (adding an agent-specific constant $c_i$ to every $u_{ij}$), which preserves envy-freeness, Pareto-optimality, and both equilibrium notions because every feasible bundle sums to one; and the affine price-wage transform $p \\mapsto q$ with $q_j = (p_{\\max} - p_j)/(p_{\\max} - 1)$, which maps 'spending at most one unit of fake money' to 'earning at least one unit' while preserving the ordering of bundles by utility and by cost. The transform is the bridge that makes the earnings-based equilibrium coincide with the pricing-based equilibrium.","core_discovery":"The paper's central claim is that the chores setting needs no new equilibrium theory once the matching constraint is exploited. Lemmas 4 and 5 show that shifting an agent's utilities by a constant ($u \\mapsto u + c$) leaves HZ equilibria and HZ earnings equilibria unchanged, which transfers existence, envy-freeness, and Pareto-optimality from goods to chores and mixed manna. Theorem 5 makes the sharper structural statement: an allocation is an HZ equilibrium under prices $p$ if and only if it is an HZ earnings equilibrium under wages $q$, where $q_j = (p_{\\max} - p_j)/(p_{\\max} - 1)$ and $p_{\\max}$ is the maximum price. Thus the earnings-based equilibrium, the natural notion when all items are chores, is the same mathematical object as the pricing-based equilibrium of Hylland and Zeckhauser. The paper then derives a polynomial-time EF+PO algorithm for instances with two agent types and for bivalued utilities, and shows that both direct minimization of the product of disutilities and Pareto-constrained Nash bargaining fail to yield bounded envy in chores matching markets.","pith_inferences":["The equivalence theorem implies that any normalization convention for HZ prices (e.g., a free good with price zero) has a wages counterpart, namely a chore with zero wage; exploiting that symmetry could yield simpler computational characterizations for chores.","Since utility shifting transfers hardness results as well as algorithmic ones, the PPAD-hardness of EF+PO allocations for goods applies verbatim to chores and mixed manna, reinforcing the focus on approximation.","The two-type EF+PO result rests on the lemma that Pareto improvements preserve envy-freeness when there are only two agent types; testing whether this lemma extends to a constant number of types is a natural next step suggested by the proof structure.","A testable extension is to replace the affine price-wage transform with a piecewise affine map that handles equilibria where all prices are at most 1; the equivalence would then hold for all equilibria, closing the normalization gap in the printed proof."],"forward_implications":["Goods-only HZ algorithms, such as the polynomial-time scheme for bivalued utilities, apply unchanged to chores and mixed manna after shifting utilities.","HZ earnings equilibria always exist and inherit envy-freeness and Pareto-optimality from the pricing-based HZ equilibrium.","Strategyproofness results that hold for dichotomous goods preferences (Bogomolnaia–Moulin) extend to the bivalued chores case by the same shifting argument.","No constant-factor envy-freeness bound is achievable via the two natural Nash-bargaining generalizations; both fail with unbounded envy on simple two-agent examples.","A polynomial-time algorithm for approximately fair and efficient cardinal-utility matching markets with chores remains open, and the mixed setting first needs a suitable notion of approximate fairness."],"supporting_citations":[{"why":"Defines the HZ pricing equilibrium and proves existence plus envy-freeness and Pareto-optimality; the baseline the paper extends.","marker":"[31]"},{"why":"Introduces the earnings-based competitive equilibrium for chores in fair division, which the paper adapts to matching markets.","marker":"[11]"},{"why":"Provides the polynomial-time algorithm for dichotomous (0/1) utilities that the bivalued result invokes after shifting.","marker":"[41]"},{"why":"Supplies strategyproofness of the dichotomous HZ mechanism, giving the bivalued mechanism its incentive guarantee.","marker":"[10]"},{"why":"Proposes Nash-bargaining-based matching market models whose chores-side generalizations the paper tests with counterexamples.","marker":"[30]"},{"why":"Gives the envy-free polytope vertex argument and PPAD-hardness background that frame the EF+PO algorithms.","marker":"[39]"},{"why":"Studies competitive equilibrium with chores, including the Pareto-constrained Nash bargaining idea the paper shows fails for matchings.","marker":"[13]"}],"fun_headline_variants":["Chores in matching markets: pricing and earnings coincide","Pricing equals earnings for chores in matching markets","Utility shift unifies goods and chores in matching markets","One equilibrium concept for chores and goods in matching","Chores in matching markets need no new equilibrium theory"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the equilibrium-equivalence theorem divides by $p_{\\max} - 1$, so it assumes an HZ price vector can be normalized so that some price is strictly greater than 1; the paper does not prove such a normalization always exists, and it can fail when all equilibrium prices are 1.","fun_headline_variants_meta":{"raw":{"variants":["Chores in matching markets: pricing and earnings coincide","Pricing equals earnings for chores in matching markets","Utility shift unifies goods and chores in matching markets","One equilibrium concept for chores and goods in matching","Chores in matching markets need no new equilibrium theory"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000563,"raw_usage":{"total_tokens":2646,"prompt_tokens":892,"completion_tokens":1754,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":508,"completion_tokens_details":{"reasoning_tokens":1680}},"tokens_in":508,"tokens_out":1754,"duration_ms":10397,"temperature":1.0,"reasoning_tokens":1680,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:49:04.556593+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Consider the two-agent instance with utilities $u_1 = (1,0)$ and $u_2 = (0,1)$. Every HZ equilibrium in this instance has both prices equal to 1, so the transform $q_j = (1 - p_j)/(1 - 1)$ in the proof of Theorem 5 is undefined and the printed proof cannot convert this pricing equilibrium into an earnings equilibrium. Checking whether the equivalence statement still holds for such boundary equilibria, for example via a piecewise affine transform, would isolate the gap between the theorem and its proof.","supporting_citations":[{"cited_title":"The efficient all ocation of individuals to positions","cited_arxiv_id":null,"evidence_quote":"Defines the HZ pricing equilibrium and proves existence plus envy-freeness and Pareto-optimality; the baseline the paper extends."},{"cited_title":"Competitive division of a mixed manna","cited_arxiv_id":null,"evidence_quote":"Introduces the earnings-based competitive equilibrium for chores in fair division, which the paper adapts to matching markets."},{"cited_title":"Computationa l complexity of the hylland-zeckhauser scheme for one-sided matching markets","cited_arxiv_id":null,"evidence_quote":"Provides the polynomial-time algorithm for dichotomous (0/1) utilities that the bivalued result invokes after shifting."},{"cited_title":"Random matching und er dichotomous preferences","cited_arxiv_id":null,"evidence_quote":"Supplies strategyproofness of the dichotomous HZ mechanism, giving the bivalued mechanism its incentive guarantee."},{"cited_title":"Nash-bargainin g-based models for matching markets: One- sided and two-sided; fisher and arrow-debreu","cited_arxiv_id":null,"evidence_quote":"Proposes Nash-bargaining-based matching market models whose chores-side generalizations the paper tests with counterexamples."},{"cited_title":"Competitive equilibrium with chores: Combinatorial algorithm and hardness","cited_arxiv_id":null,"evidence_quote":"Studies competitive equilibrium with chores, including the Pareto-constrained Nash bargaining idea the paper shows fails for matchings."}],"review_version":1}