Pith. sign in

REVIEW 6 minor 28 references

Dividing Conflicting Items Fairly

T0 review · 0 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read For two agents with any conflict graph, a maximal EF1 allocation always exists.

desk verdict This paper settles the two-agent maximal-EF1 existence question for arbitrary conflict graphs and adds a clean three-agent negative result plus NP-hardness; it deserves serious peer review. read the letter →

arxiv 2506.14149 v1 pith:FJ66XTOF submitted 2025-06-17 cs.GT

Ayumi Igarashi , Pasin Manurangsi , Hirotaka Yoneda This is my paper · ORCID
classification cs.GT MSC 91B3205C6968Q17
keywords fairdivisionconflictgraphEF1maximalallocationindependentsetmonotonevaluationsindivisiblegoodschores
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 asks whether a set of indivisible goods with pairwise conflicts, represented by a graph whose edges forbid an agent from holding both endpoints, can still be divided fairly, where fairness means envy-free up to one good (EF1) and efficiency means the allocation is maximal (no unallocated good can be added to anyone's bundle). It answers this question positively for two agents with monotone (non-decreasing) valuations: a maximal EF1 allocation exists for every conflict graph, extending the previously known interval-graph case, and can be found in polynomial time for additive valuations and pseudo-polynomial time for monotone valuations. For three or more agents the picture changes sharply: there is a three-agent instance with identical monotone valuations in which no maximal EF1 allocation exists, and deciding existence is NP-hard for every fixed number of agents $n \geq 3$. All of these results carry over to the allocation of chores.

What carries the argument

The workhorse is the gapless chain: a sequence of maximal allocations $A^{(0)},\ldots,A^{(k)}$ such that $v(A^{(0)}_1) \geq v(A^{(0)}_2)$, $v(A^{(k)}_1) \leq v(A^{(k)}_2)$, and each consecutive pair is ordered adjacent, meaning $|A^{(i-1)}_1 \setminus A^{(i)}_1| \leq 1$ and $|A^{(i)}_2 \setminus A^{(i-1)}_2| \leq 1$. Any gapless chain must contain an EF1 allocation. The proof is carried by a lemma showing that when the sign flips between adjacent allocations, one of the two is EF1, and by Algorithm 1, which constructs such a chain from any maximal independent set $S$ with $v(S) \geq v(X_1)$ and $v(S) \geq v(X_2)$.

What would settle it

Run an exhaustive search over all maximal allocations of the 7-good instance in the three-agent counterexample (the graph $K_{3,3}$ plus item 7 with the given six-level valuation) and test each for EF1; if any maximal EF1 allocation is found, the counterexample is false. The search is finite and checkable by a short program, since every allocation is a subpartition into independent sets.

Watch

Extended reading notes

Core claim

The central claim is that the obstruction to fair allocation under conflict constraints is not the graph but the number of agents. The proof builds a gapless chain of maximal allocations $A^{(0)},\ldots,A^{(k)}$ for two agents: each step moves exactly one good from agent 1 to agent 2, and the first allocation favours agent 1 while the last favours agent 2. By monotonicity, some consecutive pair has the sign of $v(A_1) - v(A_2)$ flip, and a lemma shows that at least one allocation in that pair must be EF1. The paper constructs such a chain for any graph by starting from a value-maximal maximal independent set $S$ and scanning the remaining goods to form two independent sets $X_1, X_2$. On the negative side, the paper exhibits a 7-good instance on $K_{3,3}$ plus one extra item with identical monotone valuations where a case analysis reduces to six maximal allocations, all of which fail EF1, and it sketches a reduction from Independent Set that turns any constant-size negative instance into NP-hardness for fixed $n \geq 3$.

Load-bearing premise

The load-bearing step is the finite enumeration in the three-agent counterexample: after fixing good 7 with agent 1 and applying symmetries, the proof asserts that every maximal allocation is one of six listed allocations, so a missed maximal allocation could hide an EF1 allocation and break the negative result.

Editorial extensions

If this is right

  • For two agents with arbitrary conflict graphs and monotone valuations, maximal EF1 is guaranteed, subsuming the earlier interval-graph existence result.
  • The two-agent algorithms give a practical route to fair scheduling or office allocation when only two parties are involved, with polynomial time in the additive case.
  • No analogous guarantee can hold for three agents even with identical monotone valuations, so any general algorithm for $n \geq 3$ must either restrict valuations further or settle for approximate existence.
  • Deciding whether a maximal EF1 allocation exists is NP-hard for every fixed $n \geq 3$ (with additivity for $n \geq 4$ and monotonicity for $n = 3$), so efficient universal decision procedures are out of reach unless $\mathrm{P} = \mathrm{NP}$.
  • Under uniform valuations, maximal EF1 allocations are maximal equitable partial colorings, so the paper's tree result provides a first step toward generalizing a classical equitable-coloring theorem.

Reading between the lines

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

  • The gapless-chain construction is not tied to interval graphs, so a natural test is whether a similar sign-flipping sequence can be built for other efficiency notions or for larger fixed numbers of agents.
  • The pseudo-polynomial bound for monotone valuations suggests that a strongly polynomial two-agent algorithm would need a different idea, since the current proof pushes the value of a maximal independent set upward by a factor of $m/(m-1)$ only in the additive case.
  • Because the paper's reduction converts any constant-size negative instance into NP-hardness, the open additive three-agent case is a single-instance question: finding one additive counterexample would simultaneously establish hardness for that setting.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 6 minor

Summary. The paper studies fair division of indivisible goods in which each agent's bundle must be an independent set in a conflict graph. For two agents, Theorem 6 establishes that a maximal EF1 allocation exists for every graph under identical monotone valuations, via a gapless chain of maximal allocations; Theorem 10 supplies a polynomial-time algorithm for additive valuations and a pseudo-polynomial-time algorithm for monotone valuations. For three agents, Theorem 11 gives a seven-good instance with identical monotone valuations that admits no maximal EF1 allocation; Proposition 12 gives additive counterexamples for n >= 4; and Lemma 15 reduces from Independent Set, yielding NP-hardness for every fixed n >= 3 (Theorem 14). Section 5 transfers the goods results to chores by a valuation-negation argument. The paper is self-contained and uses no fitted parameters or external numerical inputs beyond standard hardness results.

Significance. The two-agent result resolves the existence question for arbitrary conflict graphs, substantially generalizing the interval-graph result of Kumar et al., and the three-agent counterexample sharply locates the boundary of existence. The algorithms are concrete and checkable, and the reduction in Lemma 15 is stated generically, so any future constant-size counterexample automatically yields NP-hardness. The proofs of Lemma 3, Lemma 5, Theorem 6, the case analysis in Theorem 11, and the YES/NO directions of Lemma 15 are all transparent and I found them correct. The chore transfer is simple but cleanly argued. These are strong, publishable contributions.

minor comments (6)
  1. [Algorithm 2 (Section 3.5)] Line 6 of Algorithm 2 calls CHAIN EF1 (S0; G, v), but it should call CHAIN EF1 (Si; G, v); the same typo is also reflected in the surrounding text where the loop variable is i.
  2. [Section 5] The sentence 'the instances given in Theorem 12 and Proposition 11' has the theorem and proposition numbers reversed; it should refer to Proposition 12 and Theorem 11.
  3. [Proof of Theorem 10 (Section 3.5)] In the sentence 'we must have v(S) < v(X_i^l \ {g})', the left-hand side should be v(S_i), consistent with the subsequent inequality 'v(S_i) < (m-1)/m * v(X_i^l)'; as written, S is undefined at that point.
  4. [Proof of Theorem 11 (Section 4.1)] The assertion that the six allocations in Figure 3 exhaust all maximal allocations is load-bearing, and the case analysis is compressed: the text jumps from the WLOG reductions to 'there are only 6 maximal allocations to consider.' I verified the exhaustiveness, but adding a short table that justifies, for each case, why no other maximal allocation exists would make the proof much easier for readers to check independently.
  5. [Abstract and Introduction] The word 'NP-hardnesss' appears with a typo in both the Abstract and the Introduction; it should be 'NP-hardness'.
  6. [Proof of Theorem 1 (Section 3.1)] The first sentence of the proof should read 'Let (A1, A2) be a maximal EF1 allocation' rather than 'Let (A1, A2) a maximal EF1 allocation'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the two-agent existence proof, the three-agent counterexample, and the NP-hardness reduction are all self-contained and do not reduce to fitted inputs or load-bearing self-citations.

full rationale

The paper's central claims are derived from definitions and standard external results rather than from its own conclusions. The two-agent result (Theorem 6) is built on a gapless chain construction whose ordered-adjacency and maximality properties are proven directly in Lemmas 7 and 8; Lemma 5 then yields EF1 from the sign flip, and the choice of S as a maximum-value maximal independent set supplies the required inequalities without any fitted parameters. The algorithms in Theorem 10 are justified by the Moon-Moser bound and a strictly increasing potential argument, not by assuming the target allocation. The three-agent counterexample (Theorem 11) is an explicit instance whose maximal allocations are enumerated and checked individually; even if the enumeration is compressed, it does not invoke the theorem itself or any author-derived uniqueness result. The NP-hardness reduction (Lemma 15) reduces from Independent Set and uses a constant-size negative instance only as an oracle-like building block, which is a standard reduction pattern rather than a circular appeal, and Theorem 14 follows by instantiating that lemma with the explicitly constructed negative instances. The chore-allocation transfer is a direct equivalence between EF1-for-chores under v and EF1-for-goods under -v, derived from the definitions rather than from an unproven claim. Self-citations appear only as background or as sources for standard definitions and do not carry the argument; no fitted input is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work. The derivation chain is therefore self-contained, and no circular step can be exhibited from the paper's own equations or reductions.

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

The paper introduces no fitted parameters and no invented entities. Its results rest on standard definitions of EF1 and maximality, the existence of maximal independent sets, the Moon-Moser bound, and NP-hardness of Independent Set. The only subtle point is the chores section implicitly allowing negative valuations.

assumptions (4)
  • domain assumption Monotone valuations satisfy v(empty set) = 0 and are non-decreasing under set inclusion.
    Section 2; used throughout to compare bundle values and justify the gapless-chain lemmas, especially Lemma 3.
  • standard math Moon-Moser bound: at most 3^(m/3) maximal independent sets in an m-vertex graph.
    Citation [24]; bounds the number of SWAPEF1 iterations in Theorem 10 for general monotone valuations.
  • standard math Independent Set is NP-hard.
    Source problem for the reduction in Lemma 15; standard Karp result, citation [20].
  • domain assumption For chores, valuations can be negative so that -v is a well-defined non-negative monotone non-decreasing goods valuation.
    Section 5 implicitly extends the valuation codomain; otherwise R_+ with monotone non-increasing and v(empty set) = 0 forces all valuations to be identically zero.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dividing Conflicting Items Fairly." pith.science (2026). https://pith.science/paper/FJ66XTOF

@misc{pith2026250614149,
  author       = {Pith},
  title        = {Pith review of: Dividing Conflicting Items Fairly},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FJ66XTOF}},
  note         = {Machine review of arXiv:2506.14149}
}
abstract

We study the allocation of indivisible goods under conflicting constraints, represented by a graph. In this framework, vertices correspond to goods and edges correspond to conflicts between a pair of goods. Each agent is allocated an independent set in the graph. In a recent work of Kumar et al. (2024), it was shown that a maximal EF1 allocation exists for interval graphs and two agents with monotone valuations. We significantly extend this result by establishing that a maximal EF1 allocation exists for \emph{any graph} when the two agents have monotone valuations. To compute such an allocation, we present a polynomial-time algorithm for additive valuations, as well as a pseudo-polynomial time algorithm for monotone valuations. Moreover, we complement our findings by providing a counterexample demonstrating a maximal EF1 allocation may not exist for three agents with monotone valuations; further, we establish NP-hardness of determining the existence of such allocations for every fixed number $n \geq 3$ of agents. All of our results for goods also apply to the allocation of chores.

Figures

Figures reproduced from arXiv: 2506.14149 by the authors.

Figure 1
Figure 1. An example of chain of allocations for a path graph, A(0) , . . . , A(5) . The number written in each vertex is a valuation of the corresponding good. Red and blue vertices are those assigned to agent 1 and 2, respectively. 3.3 Useful Definitions and Lemmata Our construction will require several generalizations of definitions and lemmata from Kumar et al. [21]. We believe that these tools can be useful beyond the co… view at source ↗
Figure 2
Figure 2. An example of a gapless chain of allocations, constructed by Algorithm 1. The number written in each vertex is a valuation of the corresponding good. Red and blue vertices are those assigned to agent 1 and 2, respectively. We now prove a couple of crucial lemmata. Starting with the fact that each allocation is valid and maximal: 2Namely, we use a weaker adjacency notion and we only require the sign flip (first two c… view at source ↗
Figure 3
Figure 3. 6 maximal allocations to consider in the instance of Theorem 11. The vertices in red, blue, green, and gray are goods taken by agent 1, 2, 3, and no one, respectively. The instance constructed in the proof of Theorem 11 uses an identical monotone valuation. It remains an open question whether a counterexample exists for three agents with (even identical) additive valuations. For every number n ≥ 4 of agents, Hummel … view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Instance I created with n = 4 instance given by Proposition 12 for ˜I, and 5-vertex 7-edge graph for H, setting t = 3 (note that γ = 1, λ = 1 3 ). The bands in purple represents type-(iv) edges. . 5 Chore Allocation In this section, we consider the chore version of our…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    Amanatidis, H

    G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu. Fair division of indivisible goods: recent progress and open questions. Artificial Intelligence, page 103965, 2023

    work page 2023

  2. [2]

    H. Aziz, I. Caragiannis, A. Igarashi, and T. Walsh. Fair allocation of indivisible goods and chores. Autonomous Agents and Multi-Agent Systems, 36(1):1–21, 2022

    work page 2022

  3. [3]

    Bhaskar, A

    U. Bhaskar, A. R. Sricharan, and R. Vaish. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), pages 1:1–1:23, 2021

    work page 2021

  4. [4]

    V . Bilò, I. Caragiannis, M. Flammini, A. Igarashi, G. Monaco, D. Peters, C. Vinci, and W. S. Zwicker. Almost envy-free allocations with connected bundles. Games and Economic Behavior, 131:197–221, 2022

    work page 2022

  5. [5]

    Biswas, Y

    A. Biswas, Y. Ke, S. Khuller, and Q. C. Liu. An algorithmic approach to address course enrollment challenges. In Proceedings of 4th Symposium on Foundations of Responsible Computing (FORC 2023), pages 8:1–8:23, 2023

    work page 2023

  6. [6]

    Bouveret, K

    S. Bouveret, K. Cechlárová, E. Elkind, A. Igarashi, and D. Peters. Fair division of a graph. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI) , pages 135–141, 2017

    work page 2017

  7. [7]

    S. J. Brams and P . C. Fishburn. Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equity.Social Choice and Welfare, 17(2):247–267, 2000. 16

    work page 2000

  8. [8]

    S. J. Brams, M. Kilgour, and C. Klamler. Two-person fair division of indivisible items: An efficient, envy-free algorithm. Notices of the AMS, 61(2):130–141, 2014

    work page 2014

Show all 28 references
  1. [9]

    S. J. Brams and A. D. Taylor. Fair division: from cake-cutting to dispute resolution. Cambridge University Press, 1996

    1996

  2. [10]

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

    2011

  3. [11]

    Budish, G

    E. Budish, G. P . Cachon, J. B. Kessler, and A. Othman. Course Match: a large-scale implementa- tion of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research, 65(2):314–336, 2017

    2017

  4. [12]

    Chiarelli, M

    N. Chiarelli, M. Krnc, M. Milanic, U. Pferschy, N. Pivac, and J. Schauer. Fair packing of independent sets. Algorithmica, 85(5):1459–1489, 2023

    2023

  5. [13]

    D. Foley. Resource allocation and the public sector. Yale Economic Essays, pages 45–98, 1967

    1967

  6. [14]

    Gamow and M

    G. Gamow and M. Stern. Puzzle-Math. Viking Press, 1958

    1958

  7. [15]

    Goldman and A

    J. Goldman and A. D. Procaccia. Spliddit: Unleashing fair division algorithms. ACM SIGecom Exchanges, 13(2):41–46, 2014

    2014

  8. [16]

    Hajnal and E

    A. Hajnal and E. Szemerédi. Proof of a conjecture of P. Erd˝ os.Colloq Math Soc János Bolyai, 4:601–623, 01 1970

    1970

  9. [17]

    W.-L. Hsu. A simple test for interval graphs. In Graph-Theoretic Concepts in Computer Science: 18th International Workshop, WG’92 Wiesbaden-Naurod, Germany, June 18–20, 1992 Proceedings 18, pages 11–16, 1993

    1992

  10. [18]

    Hummel and M

    H. Hummel and M. L. Hetland. Fair allocation of conflicting items. Autonomous Agents and Multi-Agent Systems, 36(1):8, 2022

    2022

  11. [19]

    Igarashi and T

    A. Igarashi and T. Yokoyama. Kajibuntan: a house chore division app. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 16449–16451, 2023

    2023

  12. [20]

    R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The ...

    1972

  13. [21]

    Kumar, S

    Y. Kumar, S. Equbal, R. Gurjar, S. Nath, and R. Vaish. Fair scheduling of indivisible chores. In Proceedings of the 23rd International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 2345–2347, 2024. Extended version available at https://arxiv.org/abs/ 2...

    2024 arXiv

  14. [22]

    B. Li, M. Li, and R. Zhang. Fair scheduling for time-dependent resources. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), 2021

    2021

  15. [23]

    R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 125–131, 2004. 17

    2004

  16. [24]

    J. W. Moon and L. Moser. On cliques in graphs. Israel Journal of Mathematics, 3:23–28, 1965

    1965

  17. [25]

    Steinhaus

    H. Steinhaus. Sur la division pragmatique. Econometrica, 17:315–319, 1949

    1949

  18. [26]

    greedy solution

    W. Suksompong. Constraints in fair division. ACM SIGecom Exchanges, 19(2):46–61, 2021. 18 Appendix A Two agents and Special Graph Classes Bipartite Graphs. For two agents and special graph classes like bipartite graphs, we can find a maximal EF1 and allocation in polynomial ti...

    2021

  19. [27]

    ,∅) and x = 0

    Initialize S = (∅, . . . ,∅) and x = 0

  20. [28]

    ,k, do the following: (a) (S1,

    For i = 1, . . . ,k, do the following: (a) (S1, . . . ,Sn) ← (S1 ∪ S(i) n−x+1, . . . ,Sx ∪ S(i) n , Sx+1 ∪ S(i) 1 , . . . ,Sn ∪ S(i) n−x) where the indices of S (i) wrap around to 1 after n, and, (b) x ← (x + (number of higher colors in S (i))) mod n. It is not difficult to se...

Pith tools

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