Nonexistence of Simultaneously EF1 and Pareto Optimal Allocations for Submodular Valuations

Harish Chandramouleeswaran; Prajakta Nimbhorkar

REVIEW 4 major objections 4 minor 1 cited by

Nonexistence of Simultaneously EF1 and Pareto Optimal Allocations for Submodular Valuations

T0 review · 4 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read The paper constructs a two-agent, six-item instance with unweighted coverage valuations in which no allocation is simultaneously envy-free up to one item and Pareto optimal, settling the submodular case negatively, and proves that deciding

desk verdict The 2-agent coverage counterexample is real and settles the open problem if the write-up is tightened; the NP-hardness section has loose ends but nothing that smells fatal. read the letter →

arxiv 2607.18220 v1 pith:SRGTLYR3 submitted 2026-07-20 cs.GT cs.DS

Harish Chandramouleeswaran , Prajakta Nimbhorkar This is my paper · ORCID

classification cs.GTcs.DS MSC 91B3268Q17

keywords fairdivisionEF1ParetooptimalitysubmodularvaluationsunweightedcoverageNP-hardnesschoresindivisiblegoods

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

This paper tries to establish that the longstanding open problem of whether fair-and-efficient allocations always exist under monotone submodular valuations has a negative answer. It presents a two-agent, six-item example, where each agent's valuation counts how many coverage elements its items cover, and proves that no allocation is both envy-free up to one item (EF1) and Pareto optimal (PO). The same six-item table also works when items are chores rather than goods. The paper further proves that deciding whether an EF1+PO allocation exists is NP-hard for three agents with monotone submodular valuations. If correct, this pins the existence frontier between matroid-rank valuations, where EF1+PO always exists, and broader subadditive valuations, where it can already fail.

What carries the argument

Unweighted coverage valuations — each item is a set of elements and a bundle's value is the number of distinct elements covered — form the central mechanism: they are monotone submodular but simpler than general submodular functions. The six-item table is engineered so that value 7 is attainable only with p1 and p2 together, and the proof uses indicator-variable formulas for the two valuations to argue that the only Pareto-optimal allocations are the two displayed. For NP-hardness, the reduction attaches one item per graph vertex and makes agent 1's value combine the coverage table with the number of edges covered by chosen vertices, forcing a balanced vertex cover.

What would settle it

Enumerate all 64 allocations of the six items in Table 1 and test each for EF1 and Pareto optimality under the two coverage valuations; in particular, check whether any Pareto-optimal allocation with utility pair (6,5) or (5,6) exists, since the proof does not explicitly rule those out. A single EF1+PO allocation would disprove Theorem 1.

Watch

Extended reading notes

Core claim

The core claim is Theorem 1: the two-agent, six-item coverage-valuation instance in Table 1 has no EF1+PO allocation. The proof characterizes Pareto-optimal allocations as those giving one agent value 7 and the other value 5, lists the two candidate allocations, and observes that in each case removing any good from the 7-bundle leaves the other agent's envy. The paper extends the same table to chores (Theorem 2) and uses a reduction from balanced vertex cover to prove NP-hardness for three-agent instances (Theorem 3).

Load-bearing premise

The proof asserts, without a full derivation, that the only Pareto-optimal allocations in the six-item instance are the two listed; if a Pareto-optimal allocation with utilities (6,5) or (5,6) existed, the EF1 check would be incomplete.

Editorial extensions

If this is right

If the main theorem stands, EF1+PO is not guaranteed for any valuation class that contains unweighted coverage valuations, so positive results for additive and matroid-rank valuations cannot be extended further in that direction.
The same example shows nonexistence for chores with unweighted coverage costs, ruling out a positive guarantee in that setting as well.
Deciding existence of EF1+PO becomes NP-hard with three agents even under monotone submodular valuations, so no efficient universal detection algorithm exists unless P=NP.
The paper records that identical monotone submodular valuations still always admit EF1+PO via leximin allocations, so the obstruction is genuinely about heterogeneous preferences.
The paper's open question about positive marginal values suggests a possible recovery: if every good adds positive value to every partial bundle, EF1+PO may exist even when coverage valuations fail.

Reading between the lines

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

The proof as written leaves an enumeration gap: it asserts, rather than derives, that the only Pareto-optimal utility pairs are (7,5) and (5,7), skipping the (6,5) and (5,6) cases; this is a proof-level gap, not a counterexample, and a brute-force check would close it.
Because the NP-hardness reduction embeds the two-agent counterexample, any revision that weakens Theorem 1 would also destabilize Theorem 3; conversely, if Theorem 1 holds, the hardness persists under a very constrained valuation class.
The chores result is essentially a byproduct of the symmetry between the two valuations; one can test whether small perturbations, such as giving each item a private coverage element, restore existence, which would align with the paper's open problem.

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.

Desk Editor's Note

read the letter

You should know: the main claim is likely correct. The six-item coverage instance in Table 1 genuinely admits no EF1+PO allocation for monotone submodular valuations. The reader's enumeration checks out: the only PO utility pairs are (7,5) and (5,7), and both fail EF1 because removing any item from the value-7 bundle leaves value 6. That is a real counterexample, and it moves the nonexistence frontier from subadditive to unweighted coverage valuations.

What's new: the explicit 2-agent 6-item instance; the corollary for chores (prior work already had chores nonexistence, but this is a cleaner coverage example); and the NP-hardness reduction for 3 agents. The construction is simple and the paper is honest about related work.

The main weakness is the proof of Theorem 1. The paper shows no (6,6), and that a 7-valued bundle leaves the other agent at most 5, but then jumps to "hence the only PO allocations are ..." without spelling out why (6,5) or (5,6) can't be PO. They are dominated by the exhibited (7,5)/(5,7) allocations, but the text needs to say that. It's a short missing argument, not a hole in the result. Claim 5.3 says "a3 EF1-envies a1" in allocation (i); the envier is a2, as in Theorem 1. The NP-hardness reduction also assumes Balanced Vertex Cover with n even; the paper doesn't say so, and the proof's |X1∩P| > n/2 step uses that. The chores section is terse and hard to follow, but the claims seem plausible.

If I were refereeing, I'd ask for the missing domination argument, a correction of the envier label, and a note on the parity assumption. None of these should sink the paper.

Bottom line: this is a good paper for the fair division crowd. It deserves a serious referee. I would bring it to reading group and would cite the main theorem once it's publicly vetted.

Referee Report

4 major / 4 minor

Summary. The paper addresses the open question of whether EF1 and Pareto-optimal allocations of indivisible goods always exist when agents have monotone submodular valuations. It proposes a negative answer via a two-agent, six-item instance with unweighted coverage valuations for which no EF1+PO allocation is claimed to exist (Theorem 1), a chores analogue (Theorem 2), and an NP-hardness result for deciding EF1+PO existence with three agents (Theorem 3). The central construction is explicit and directly checkable; the main weaknesses are in the proof of the Pareto-optimal frontier and in the NP-hardness reduction.

Significance. If correct, this settles a longstanding open problem and strengthens the nonexistence frontier from monotone subadditive valuations to unweighted coverage valuations, a strict subclass of monotone submodular valuations. The explicit two-agent example is a valuable, falsifiable construction, and the NP-hardness companion is a natural further contribution. However, acceptance requires a rigorous derivation of the Pareto frontier; the current text contains a false enumeration of value-7 bundles, an unsupported PO-characterization step, and the stated reduction has an odd-n issue. These problems appear fixable, but they are load-bearing as written.

major comments (4)

[§3, proof of Theorem 1] The statement "for agent1, the only bundles of value 7 are {p1,p2,p3,r}, {p1,p2,p3,r1}, and {p1,p2,q,r1}" is false. Using the displayed formula for v1, the bundle {p1,p2,r,r1} satisfies all seven indicator terms: p1 and p2 are present, the p3∨r1 term is true, the r∨r1 term is true, and all three r-containing terms are true. Hence v1({p1,p2,r,r1})=7. This omitted case is not covered by the subsequent list of complements, and the conclusion that the only PO allocations are (i) and (ii) rests on this list. The theorem may still be true, but a correct derivation of the PO frontier must be supplied.
[§3, proof of Theorem 1 (after Claims 3.1–3.2)] The inference "Hence the only Pareto optimal allocations should assign a bundle of value 7 to one agent and a bundle of value 5 to another agent" is not justified. Claims 3.1–3.2 rule out a (6,6) utility pair and bound complements of 7-bundles, but they do not rule out allocations with utility pairs such as (6,5), (5,6), (7,4), or (4,7), nor do they argue that every such pair is Pareto dominated by (7,5) or (5,7). A complete proof can be obtained by enumerating the 64 allocations or by an explicit domination argument; the text currently supplies neither.
[§5, Claim 5.3] The assertion "any allocation X where |X1∩P| > n/2 is not EF1 as a3 EF1-envies a1" is false for odd n. For n=2k+1 and |X1∩P|=k+1, agent 3 holds k P-items, and after removing one P-item from X1 the value to a3 is k, so agent 3 does not EF1-envy a1. The actual EF1 condition for a3 is |S|-1 ≤ n-|S|, i.e., |S| ≤ (n+1)/2. The reduction therefore needs to restrict Balanced Vertex Cover to even n, or state an appropriate threshold; otherwise Claim 5.3 is incorrect as stated.
[§5, Claims 5.2–5.3] The Pareto-optimality arguments in the reduction are asserted rather than proved. In particular, the sentence "From Theorem 1, X2 is the best possible bundle for a2, and there is no Pareto dominating allocation of items in M" does not establish full PO, because a full allocation can also reallocate P-items between a1 and a3, and agent 3's valuation is zero on M; such reallocations are not analyzed. Similarly, the claims that every PO allocation must give a2 no P-items and a1 no strict superset of a vertex cover require proofs that rule out compensating trades involving M-items. Without these arguments, the correctness of the reduction is not established.

minor comments (4)

[§3, proof of Theorem 1] In the EF1-check for allocation (i), the text writes "v2(X2\{g})=6 for any g∈X1"; this should be "v2(X1\{g})=6" (or similar), since the item removed should be from the envied bundle X1.
[§5, Definition 5.1] Balanced Vertex Cover is stated as "vertex cover of size at most n/2" without specifying whether n is even. Since the proof has a parity-sensitive step, the definition should say "n even" or "at most floor(n/2)" and the reduction should be adjusted accordingly.
[Table 1] The rendering of Table 1 makes the coverage sets hard to verify. It would be clearer to list each item's covered universe explicitly, e.g., p1={u1,u5}, p2={u2,u6}, p3={u3,u7}, q={u5,u6,u7}, r={u4,u5,u6,u7}, r1={u3,u4}, as in the formulas.
[§4, Claims 4.1–4.3] The chores proof is dense and the PO-frontier is assembled informally. A compact table of the Pareto frontier, or an explicit statement that the listed disutility pairs are exhaustive and attained, would make the proof much easier to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1 is a direct two-agent coverage construction; the flagged omitted enumeration is a proof gap, not a circular reduction.

full rationale

The derivation chain does not fit parameters, rename an existing result, or import a load-bearing conclusion from the authors' own prior work. The top-level nonexistence claim rests on an explicit 6-item/universe-7 coverage instance and a case analysis: Claim 3.1 bounds the other agent's value when one agent receives value 7, Claim 3.2 excludes the (6,6) utility profile, and the remaining EF1 check is carried out on the two named allocations. The text's inference "Hence the only Pareto optimal allocations should assign a bundle of value 7 to one agent and a bundle of value 5 to another agent" (Theorem 1 proof, immediately after Claim 3.2) is asserted rather than exhaustively justified—utility profiles (6,5)/(5,6) are not explicitly eliminated—but this is an omitted case analysis, not an assumption that already encodes the conclusion; the construction does not define Pareto optimality in terms of the target allocation. The NP-hardness reduction inherits this characterization from Theorem 1, so the same non-circular gap propagates. The chores theorem is a separate direct analysis of the same table. Appendix A invokes BCIZ21, Lemma 3.5 as an external transferability lemma, and the cited lemma is independent of the present paper's claims; it is not a self-citation. Self-citations appear only in ordinary context (e.g., references to prior work in the introduction), none load-bearing. Thus the circularity score is 0; correctness risk from the unproven PO enumeration should be assessed separately.

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

No fitted parameters or invented entities are introduced. The load-bearing external fact is the NP-completeness of Balanced Vertex Cover; the only non-derived component is the small frontier enumeration for the central example, which is asserted rather than fully exhibited.

assumptions (3)

standard math Balanced Vertex Cover is NP-complete (Conitzer-Sandholm [CS06, Lemma 1]).
The NP-hardness reduction in Theorem 3 reduces from Balanced Vertex Cover.
standard math Weighted and unweighted coverage valuations are normalized monotone submodular valuations.
Used to place the constructed instance inside the submodular class and to justify that the weighted combination in the NP-hardness reduction is still coverage/submodular.
ad hoc to paper The utility frontier of the Table 1 instance consists only of (7,5) and (5,7) Pareto-optimal pairs, with no (6,6), (6,5), or (5,6) PO allocations.
The proof of Theorem 1 asserts this after Claims 3.1-3.2 without an exhaustive enumeration. It is true, but a reader must carry out the 64-allocation check to confirm it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nonexistence of Simultaneously EF1 and Pareto Optimal Allocations for Submodular Valuations." pith.science (2026). https://pith.science/paper/SRGTLYR3

@misc{pith2026260718220,
  author       = {Pith},
  title        = {Pith review of: Nonexistence of Simultaneously EF1 and Pareto Optimal Allocations for Submodular Valuations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SRGTLYR3}},
  note         = {Machine review of arXiv:2607.18220}
}

read the original abstract

The existence of allocations of indivisible goods that are simultaneously fair (envy-free up to one item (EF1)) and efficient (Pareto optimal (PO)) when agents have monotone submodular valuations has been a longstanding open problem. We settle this question negatively by giving an example with two agents where no allocation is simultaneously EF1 and PO. We also show that determining the existence of such allocations is NP-hard for monotone submodular valuations. Our example uses (unweighted) coverage valuations, which is a strict subclass of monotone submodular valuations. Since EF1+PO allocations are known to always exist for additive valuations via the maximization of Nash Social Welfare (Caragiannis et al. (ACM TEAC 2019)), and for matroid-rank valuations (Benabbou et al. (ACM TEAC 2021)), nonexistence was known only for monotone subadditive valuations (Caragiannis et al. (ACM TEAC 2019)). Our work moves the nonexistence frontier to unweighted coverage valuations. We also show that the example we designed for goods also proves nonexistence of EF1+PO in general, for chores with unweighted coverage costs, by interpreting the valuations as disutilities.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO
cs.GT 2026-07 accept novelty 7.0 of 10

For two agents with strictly increasing valuations, EF1 and Pareto optimality are always compatible up to seven goods, and an eight-good submodular counterexample shows this is tight.

Reference graph

Works this paper leans on

24 extracted references · cited by 1 Pith paper

[1]

Fair division of indivisible goods: Recent progress and open questions , year =

Amanatidis, Georgios and Aziz, Haris and Birmpas, Georgios and Filos-Ratsikas, Aris and Li, Bo and Moulin, Herv\'. Fair division of indivisible goods: Recent progress and open questions , year =. doi:10.1016/j.artint.2023.103965 , journal =

arXiv 2023
[2]

Haris Aziz and Ioannis Caragiannis and Ayumi Igarashi and Toby Walsh , title =. Auton. Agents Multi Agent Syst. , volume =. 2022 , url =

2022
[3]

Thirty-Fifth

Moshe Babaioff and Tomer Ezra and Uriel Feige , title =. Thirty-Fifth. 2021 , url =

2021
[4]

Proceedings of the 2018

Siddharth Barman and Sanath Kumar Krishnamurthy and Rohit Vaish , title =. Proceedings of the 2018. 2018 , url =

2018
[5]

Proceedings of the 2026 Annual

Siddharth Barman and Mashbat Suzuki , title =. Proceedings of the 2026 Annual. 2026 , url =

2026
[6]

Thirty-Sixth

Siddharth Barman and Paritosh Verma , title =. Thirty-Sixth. 2022 , url =

2022
[7]

2021 , url =

Nawal Benabbou and Mithun Chakraborty and Ayumi Igarashi and Yair Zick , title =. 2021 , url =

2021
[8]

Journal of Political Economy , volume=

The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes , author=. Journal of Political Economy , volume=. 2011 , publisher=

2011

Show all 24 references

[9]

Proceedings 7th

Vincent Conitzer and Tuomas Sandholm , title =. Proceedings 7th. 2006 , url =

2006
[10]

CoRR , volume =

Uriel Feige and Assaf Fine , title =. CoRR , volume =
[11]

The Unreasonable Fairness of Maximum Nash Welfare , journal =

Ioannis Caragiannis and David Kurokawa and Herv. The Unreasonable Fairness of Maximum Nash Welfare , journal =. 2019 , url =

2019
[12]

1966 , volume=

Resource allocation and the public sector , author=. 1966 , volume=

1966
[13]

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems,

Pooja Kulkarni and Rucha Kulkarni and Ruta Mehta , title =. Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems,. 2023 , url =

2023
[14]

Euiwoong Lee , title =. Inf. Process. Lett. , volume =. 2017 , url =

2017
[15]

I. M. D. Little , title =
[16]

Lipton and Evangelos Markakis and Elchanan Mossel and Amin Saberi , title =

Richard J. Lipton and Evangelos Markakis and Elchanan Mossel and Amin Saberi , title =. Proceedings 5th. 2004 , url =

2004
[17]

Web and Internet Economics - 21st International Conference,

Ryoga Mahara , title =. Web and Internet Economics - 21st International Conference,. 2025 , url =

2025
[18]

Proceedings of the 2026 Annual

Ryoga Mahara , title =. Proceedings of the 2026 Annual. 2026 , url =

2026
[19]

Computational complexity and approximability of social welfare optimization in multiagent resource allocation , journal =

Nhan. Computational complexity and approximability of social welfare optimization in multiagent resource allocation , journal =. 2014 , url =

2014
[20]

2020 , url =

Benjamin Plaut and Tim Roughgarden , title =. 2020 , url =

2020
[21]

Varian , title =

Hal R. Varian , title =. Journal of Economic Theory , volume =. 1974 , doi =

1974
[22]

Proceedings of the 24th

Vignesh Viswanathan and Yair Zick , title =. Proceedings of the 24th. 2023 , url =

2023
[23]

Umang Bhaskar and A. R. Sricharan and Rohit Vaish , title =. Proceedings of the 3rd Games, Agents, and Incentives Workshop , year =
[24]

Fair Distribution of Delivery Orders , journal =

Hadi Hosseini and Shivika Narang and Tomasz W. Fair Distribution of Delivery Orders , journal =. 2025 , doi =

2025

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

Fair division of indivisible goods: Recent progress and open questions , year =

Amanatidis, Georgios and Aziz, Haris and Birmpas, Georgios and Filos-Ratsikas, Aris and Li, Bo and Moulin, Herv\'. Fair division of indivisible goods: Recent progress and open questions , year =. doi:10.1016/j.artint.2023.103965 , journal =

arXiv 2023

[2] [2]

Haris Aziz and Ioannis Caragiannis and Ayumi Igarashi and Toby Walsh , title =. Auton. Agents Multi Agent Syst. , volume =. 2022 , url =

2022

[3] [3]

Thirty-Fifth

Moshe Babaioff and Tomer Ezra and Uriel Feige , title =. Thirty-Fifth. 2021 , url =

2021

[4] [4]

Proceedings of the 2018

Siddharth Barman and Sanath Kumar Krishnamurthy and Rohit Vaish , title =. Proceedings of the 2018. 2018 , url =

2018

[5] [5]

Proceedings of the 2026 Annual

Siddharth Barman and Mashbat Suzuki , title =. Proceedings of the 2026 Annual. 2026 , url =

2026

[6] [6]

Thirty-Sixth

Siddharth Barman and Paritosh Verma , title =. Thirty-Sixth. 2022 , url =

2022

[7] [7]

2021 , url =

Nawal Benabbou and Mithun Chakraborty and Ayumi Igarashi and Yair Zick , title =. 2021 , url =

2021

[8] [8]

Journal of Political Economy , volume=

The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes , author=. Journal of Political Economy , volume=. 2011 , publisher=

2011