Pith. sign in

REVIEW 4 minor 18 references

Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO

T0 review · 0 major / 4 minor · reviewed 2026-07-31 · deepseek-v4-flash

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

Pith's one-line read For two agents with strictly increasing valuations, seven goods always admit an EF1 and Pareto-optimal allocation, while an eight-good submodular counterexample shows eight is the exact threshold.

desk verdict A tight two-agent threshold for EF1+PO under strictly increasing valuations, with a clean combinatorial proof and a verified submodular counterexample; only minor presentation blemishes. read the letter →

arxiv 2607.23367 v1 pith:5HFCU55Y submitted 2026-07-25 cs.GT cs.AIecon.TH

Nicholas Teh This is my paper · ORCID
classification cs.GTcs.AIecon.TH MSC 91B3268Q17
keywords fairdivisionEF1Paretooptimalitystrictlyincreasingvaluationssubmodularindivisiblegoodstwo-agentthresholdNP-hardness
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 settles an open question by showing that strictly positive marginal values do not guarantee the existence of an allocation that is both envy-free up to one good (EF1) and Pareto optimal (PO). It establishes that the exact two-agent threshold is eight goods: every instance with at most seven goods and strictly increasing valuations admits an EF1+PO allocation, regardless of submodularity, while an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations has none—every EF1 allocation there is strictly Pareto dominated. The positive proof is a combinatorial argument built around a counting lemma on cross-intersecting bundle families, and the counterexample is a perturbation of a known submodular construction. A separate result tightens the computational hardness of the three-agent problem, confining all zero marginal values to eight fixed agent-good pairs involving a single agent.

What carries the argument

The argument runs on two instruments. First, a perturbation of a known submodular counterexample: the paper scales a known example by 12 and adds |S| to every bundle value, making every marginal strictly positive while preserving the structure of EF1 violations and Pareto improvements. The resulting instance is count-based—three A-goods and five B-goods—and its marginal arrays are all positive and nonincreasing, which certifies strict increase and submodularity. Second, the positive side uses a violation-threshold method: for each agent, identify the family of EF1-violating bundles, take the maximum value τ among them, and consider bundles of value above τ; bundles derived from a worst viola

What would settle it

A brute-force search over all two-agent, seven-good instances with normalized, integer-valued, strictly increasing valuations (e.g., count-based tables) looking for an instance with no EF1+PO allocation would settle the threshold; the paper's theorem predicts none exists.

Watch

Extended reading notes

Core claim

The paper's central discovery is that, for two agents with strictly increasing valuations, EF1 and PO compatibility fails exactly when the number of goods reaches eight. It constructs an eight-good, normalized, integer-valued, strictly increasing, submodular instance in which every EF1 allocation is strictly Pareto dominated, and it proves that no such incompatibility can occur with seven or fewer goods for any strictly increasing valuations. The open question of whether strictly positive marginals restore EF1+PO is therefore answered in the negative, but the threshold is tight: the construction is minimal. The paper further strengthens a known NP-hardness result to the case where all zero m

Load-bearing premise

The positive theorem rests on the counting claim that the two agents' threshold-exceeding 'add-or-delete-one-good' families cannot be pairwise intersecting on fewer than eight goods, and the hardness theorem relies on a cited NP-hardness result for balanced vertex cover; should either fail, the corresponding result collapses.

Editorial extensions

If this is right

  • The open problem is closed: strictly positive marginal values do not in general restore compatibility of EF1 and PO, even for two agents.
  • For two agents, the sharp number of goods is eight: seven or fewer always admit an EF1+PO allocation, and eight can fail.
  • The positive result holds without submodularity—any strictly increasing valuations over at most seven goods are covered.
  • The three-agent existence problem is NP-hard even when zero marginals are limited to eight fixed agent-good pairs, all involving one agent.
  • Because the counterexample also violates weak Pareto optimality for every EF1 allocation, the incompatibility is robust to the choice of PO variant.

Reading between the lines

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

  • The counting-lemma technique used for up to seven goods may generalize to k-agent instances, suggesting that the minimum number of goods for incompatibility grows with the number of agents; the paper leaves this open.
  • The perturbation recipe—adding |S| to a known zero-marginal counterexample—could be applied to other fair-division constructions to convert them into strictly increasing instances, potentially revealing whether positive marginals ever restore compatibility in larger settings.
  • Because the counterexample uses only two types of goods (count-based valuations), it hints that the obstruction is a matter of count structure rather than item-specific interactions; one could test whether every two-agent, eight-good incompatibility instance can be represented in this count-based form.
  • The NP-hardness result with a constant-size zero-marginal core suggests a natural next question: whether hardness persists when every valuation is strictly increasing, as the paper notes.
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, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies whether strictly positive marginal values guarantee the existence of EF1 and PO allocations for two agents. It proves a tight threshold: every two-agent instance with at most seven goods and strictly increasing valuations admits an EF1+PO allocation (Theorem 4.4), while an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations has every EF1 allocation strictly Pareto dominated (Theorem 3.1). It also strengthens a three-agent NP-hardness result by confining all zero marginals to eight fixed agent–good pairs involving a single agent (Theorem 5.1). The proofs are combinatorial and self-contained, with explicit tables and appendices.

Significance. The main result resolves an open problem of Chandramouleeswaran and Nimbhorkar and gives the exact threshold in the number of goods. This is a clean and significant contribution to the fair-division literature. The paper is unusually checkable: the counterexample provides full marginal arrays, the EF1 splits are classified by explicit σ tables, the strict Pareto dominations are displayed, and the counting lemma (Lemma 4.3) is verified by a short cell-count argument. The NP-hardness strengthening is a substantial additional contribution. I found the proofs consistent, with no load-bearing gaps.

minor comments (4)
  1. [Section 4, Theorem 4.4 proof] The paragraph beginning “It remains to impose Pareto optimality without crossing either threshold” appears twice, with two different arguments (one by Pareto maximality, one by sum maximization). Please delete one version and keep a single, coherent argument.
  2. [Abstract] There are spacing/formatting artifacts such as “uptoonegood” and “Paretooptimality”. These should be corrected.
  3. [Section 5, core fact (C1)] The phrase “coreEF1 differences” is missing a space; it should read “core EF1 differences”.
  4. [Section 4, proof of Theorem 4.4] In the first sentence of the PO enhancement, “we impose Pareto optimality without crossing either threshold” is slightly misleading: the subsequent argument maximizes within the set of allocations that stay above the thresholds. Consider rephrasing for clarity.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity found; all load-bearing claims are proven directly.

full rationale

The derivation chain is self-contained. The eight-good counterexample is given by explicit integer tables (1)–(2); the paper verifies strict increase and submodularity via Lemma 3.2 using the marginal arrays in Appendix A, enumerates all EF1 splits through the σ1,σ2 differences in Appendix B, and exhibits explicit strictly dominating splits in table (7). The reference to Mackenzie and Suzuki [15] explains the provenance of the construction, but every asserted property is checked directly from the tables, so no unverified imported result is load-bearing. The positive side (Theorem 4.4) reduces to Lemma 4.3, a purely combinatorial statement about two bipartitions into four cells; the proof establishes the exact condition p≥1, q≥2, r≥2, s≥3 by explicit set-intersection arguments and does not invoke any theorem whose conclusion includes the target result. The final Pareto-optimality step is a finite maximization over allocations, not a fitted parameter or a renamed input. The NP-hardness reduction depends on the external balanced vertex cover hardness of Conitzer–Sandholm [11, Lemma 1], which is a standard dependency and is explicitly reduced from the exactly-n/2 to the at-most-n/2 formulation; the zero-marginal structure is constructed, not assumed. The self-citations [7], [13], and [18] appear only in related-work paragraphs and are not used in any proof. No equation or construction reduces by definition to its own input, and no fitted value is relabeled as a prediction.

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

No fitted parameters: the counterexample tables are fixed explicit integers, and the scaling constants (ε=1/6, factor 12) are part of the construction, not tuned to data. The only external assumption is NP-hardness of balanced vertex cover; no new theoretical entities are introduced.

assumptions (2)
  • domain assumption Balanced Vertex Cover (even n, cover size ≤ n/2) is NP-hard
    Source problem for the reduction in Section 5; cited to Conitzer and Sandholm [11, Lemma 1]. The paper argues equivalence of 'at most n/2' and 'exactly n/2' cover sizes.
  • domain assumption Valuations w1, w2, w3 admit polynomial-size descriptions and are evaluable in polynomial time
    Stated in Footnote 2 and used implicitly throughout Section 5 so that the NP-hardness decision problem is well-formed.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO." pith.science (2026). https://pith.science/paper/5HFCU55Y

@misc{pith2026260723367,
  author       = {Pith},
  title        = {Pith review of: Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5HFCU55Y}},
  note         = {Machine review of arXiv:2607.23367}
}
read the original abstract

We study whether strictly positive marginal values restore the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) for indivisible goods. For two agents, we identify the exact threshold in the number of goods. Every instance with at most seven goods and strictly increasing valuations admits an allocation that is both EF1 and PO, without any submodularity assumption. In contrast, we construct an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations in which every EF1 allocation is strictly Pareto dominated. Thus, eight goods are necessary and sufficient for a two-agent counterexample. Finally, we strengthen the three-agent NP-hardness result of Chandramouleeswaran and Nimbhorkar (2026): deciding whether an EF1 and PO allocation exists remains NP-hard for normalized, integer-valued, monotone submodular valuations even when zero marginals are confined to eight fixed agent-good pairs, all involving a single agent.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 3 linked inside Pith

  1. [1]

    Voudouris, and Xiaowei Wu

    Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions.Artificial Intelligence, 322(C), 2023. 12

    2023

  2. [2]

    Fair allocation of indivisible goods and chores.Autonomous Agents and Multi-Agent Systems, 36(3), 2022

    Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. Fair allocation of indivisible goods and chores.Autonomous Agents and Multi-Agent Systems, 36(3), 2022

    2022

  3. [3]

    Compatibility of fairness and Nash welfare under subadditive valuations

    Siddharth Barman and Mashbat Suzuki. Compatibility of fairness and Nash welfare under subadditive valuations. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1724–1746, 2026

    2026

  4. [4]

    Finding fair and efficient allocations

    Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. InProceedings of the 19th ACM Conference on Economics and Computation (EC), pages 557–574, 2018

    2018

  5. [5]

    Finding fair and efficient allocations for matroid rank valuations.ACM Transactions on Economics and Computation, 9: 1–41, 2021

    Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick. Finding fair and efficient allocations for matroid rank valuations.ACM Transactions on Economics and Computation, 9: 1–41, 2021

    2021

  6. [6]

    Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On approximate envy-freeness for indivisible chores and mixed resources. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 1:1–1:23, 2021

    2021

  7. [7]

    Fair division with binary valuations: Characterizations

    Florian Brandl, Warut Suksompong, and Nicholas Teh. Fair division with binary valuations: Characterizations. InProceedings of the 19th International Symposium on Algorithmic Game Theory (SAGT), 2026. Extended version available at arXiv:2607.10064

    arXiv 2026

  8. [8]

    The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy, 119(6):1061–1103, 2011

    Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy, 119(6):1061–1103, 2011

    2011

Show all 18 references
  1. [9]

    Procaccia, Nisarg Shah, and Junxing Wang

    Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum Nash welfare.ACM Transactions on Economics and Computation, 7(3):12:1–12:32, 2019

    2019

  2. [10]

    Nonexistence of simultaneously EF1 and pareto optimal allocations for submodular valuations.arXiv preprint arXiv:2607.18220, 2026

    Harish Chandramouleeswaran and Prajakta Nimbhorkar. Nonexistence of simultaneously EF1 and pareto optimal allocations for submodular valuations.arXiv preprint arXiv:2607.18220, 2026

    2026 arXiv

  3. [11]

    Computing the optimal strategy to commit to

    Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy to commit to. In Proceedings of the 7th ACM Conference on Electronic Commerce (EC), pages 82–90, 2006

    2006

  4. [12]

    Fair distribution of delivery orders.Artificial Intelligence, 347:104389, 2025

    Hadi Hosseini, Shivika Narang, and Tomasz Wąs. Fair distribution of delivery orders.Artificial Intelligence, 347:104389, 2025

    2025

  5. [13]

    The cost of EFX: Generalized-mean welfare and complexity dichotomies with few surplus items.arXiv preprint arXiv:2601.12849, 2026

    Eugene Lim, Tzeh Yuan Neoh, and Nicholas Teh. The cost of EFX: Generalized-mean welfare and complexity dichotomies with few surplus items.arXiv preprint arXiv:2601.12849, 2026

    2026

  6. [14]

    Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi

    Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. InProceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 125–131, 2004

    2004

  7. [15]

    When one good is not enough: EF1 and pareto optimality are not compatible for submodular valuations.arXiv preprint arXiv:2607.17811, 2026

    Simon Mackenzie and Mashbat Suzuki. When one good is not enough: EF1 and pareto optimality are not compatible for submodular valuations.arXiv preprint arXiv:2607.17811, 2026

    2026 arXiv

  8. [16]

    Existence of fair and efficient allocation of indivisible chores

    Ryoga Mahara. Existence of fair and efficient allocation of indivisible chores. InProceedings of the 37th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 6742–6766, 2026. 13

    2026

  9. [17]

    Almost envy-freeness with general valuations.SIAM Journal on Discrete Mathematics, 34(2):1039–1068, 2020

    Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations.SIAM Journal on Discrete Mathematics, 34(2):1039–1068, 2020

    2020

  10. [18]

    Computing fair and efficient indivisible chore allocations with bounded surplus

    Nicholas Teh. Computing fair and efficient indivisible chore allocations with bounded surplus. InProceedings of the 19th International Symposium on Algorithmic Game Theory (SAGT), 2026. A Marginal Arrays for the Eight-Good Instance For rows indexed byxand columns indexed byy, ...

    2026

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.