pith. sign in

arxiv: 2607.01059 · v1 · pith:XMWHBK6Unew · submitted 2026-07-01 · 💻 cs.GT · cs.DS· math.CO

Fair Allocation under Conflict Constraints via Strong Colorability

Ishay Haviv This is my paper

Pith reviewed 2026-07-02 04:01 UTC · model grok-4.3

classification 💻 cs.GT cs.DSmath.CO
keywords agentsfairallocationgraphnumbersd-ef1commonconflict
0
0 comments X

The pith

The paper introduces a hierarchy of strong chromatic number variants to characterize and algorithmically guarantee SD-EF1, EF1, and EF[1,1] allocations under graph conflict constraints, showing 3Δ-1 agents suffice for any graph of maximum degree Δ.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

In this setting, items are vertices in a graph and conflicts mean adjacent vertices cannot be given to the same agent. All agents share the same preferences over items. The task is to divide the items so the bundles are fair according to three envy-freeness standards that relax full envy-freeness by allowing one extra item. The authors define a ladder of stronger versions of an older graph measure called the strong chromatic number. They prove that the first two rungs of this ladder exactly capture the conditions needed for the strongest fairness notion (SD-EF1) and give sufficient conditions for the other two. A concrete payoff is that any graph whose busiest vertex has at most Δ neighbors can always be divided fairly among 3Δ−1 agents for all three standards. They also supply fast deterministic algorithms that succeed as soon as the number of agents exceeds 3Δ by any positive amount. The approach therefore supplies both existence guarantees and practical computation methods while improving earlier bounds that came from equitable coloring.

Core claim

every graph with maximum degree Δ admits SD-EF1, EF1, and EF[1,1] allocations for common preferences whenever the number of agents is at least 3Δ-1. We further provide, for any ε>0, deterministic polynomial-time algorithms that find such allocations whenever the number of agents is at least (3+ε)Δ

Load-bearing premise

The fairness criteria for agents with common preferences can be reduced to properties of the first two levels of the newly introduced hierarchy of strong chromatic number variants (as described in the abstract).

read the original abstract

In the fair allocation problem under conflict constraints, the goal is to partition the vertices of a graph among agents in a fair manner, such that no two adjacent vertices are assigned to the same agent. We study this problem for agents with common preferences through the lens of three fairness criteria: stochastic-dominance envy-freeness up to one item for preference orders (SD-EF1), envy-freeness up to one item for monotone additive valuations (EF1), and envy-freeness up to one item from each side for general additive valuations (EF[1,1]). To do so, we introduce a hierarchy of variants of the strong chromatic number, a graph quantity introduced independently by Alon and Fellows in the early nineties. Our results reveal a close connection between fair allocation under conflict constraints and the first two levels of this hierarchy, providing a unified route to both existential and algorithmic results. For SD-EF1, we fully characterize the number of agents needed to guarantee a fair allocation of a given graph for every common preference order. For EF1 and EF[1,1], we provide analogous sufficient conditions, extending a result on path graphs due to Equbal, Gurjar, Igarashi, Kumar, Manurangsi, Nath, Saxena, Vaish, and Yoneda. We also show that, unlike in the SD-EF1 setting, the sufficient conditions for EF1 and EF[1,1] are not necessary in general. Our framework yields existential and algorithmic consequences in terms of the maximum degree. We obtain that every graph with maximum degree $\Delta$ admits SD-EF1, EF1, and EF[1,1] allocations for common preferences whenever the number of agents is at least $3\Delta-1$. We further provide, for any $\varepsilon>0$, deterministic polynomial-time algorithms that find such allocations whenever the number of agents is at least $(3+\varepsilon)\Delta$. These guarantees strengthen earlier work by Barman and Viswanathan on equitable colorings.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Circularity Check

0 steps flagged

No circularity: results derived from new hierarchy definitions and external graph-theoretic facts

full rationale

The paper introduces a new hierarchy of strong chromatic number variants and reduces the fairness criteria (SD-EF1, EF1, EF[1,1]) to properties of the first two levels of this hierarchy. Existential and algorithmic guarantees for graphs of maximum degree Δ are then obtained from these definitions plus standard graph coloring arguments, extending external results (Alon-Fellows on strong coloring; Barman-Viswanathan on equitable colorings; Equbal et al. on paths). No self-citations are load-bearing, no parameters are fitted and relabeled as predictions, no ansatzes are imported via citation, and no uniqueness theorems from the same authors are invoked. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claims rest on the newly introduced hierarchy of strong chromatic number variants and standard domain assumptions about graphs and valuations; no data-fitted parameters are present.

axioms (2)
  • domain assumption The input is an undirected simple graph representing conflict constraints
    Standard modeling choice for allocation problems with conflicts, invoked throughout the abstract.
  • domain assumption All agents share identical preferences over the items
    Explicitly stated as the setting for the fairness criteria.
invented entities (1)
  • Hierarchy of variants of the strong chromatic number no independent evidence
    purpose: To provide a unified framework linking graph coloring quantities to the three fairness criteria
    Newly defined in the paper to obtain both existential and algorithmic results.

pith-pipeline@v0.9.1-grok · 5903 in / 1392 out tokens · 86473 ms · 2026-07-02T04:01:45.400080+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 3 canonical work pages · 3 internal anchors

  1. [1]

    Aharoni, E

    R. Aharoni, E. Berger, and R. Ziv. Independent systems of representatives in weighted graphs. Combinatorica, 27(3):253–267, 2007

    2007

  2. [2]

    N. Alon. The strong chromatic number of a graph.Random Struct. Algorithms, 3(1):1–7, 1992

    1992

  3. [3]

    N. Alon. Discrete mathematics: Methods and challenges. InProc. of the International Congress of Mathematicians (ICM’02), pages 119–135. Higher Education Press, 2002

    2002

  4. [4]

    Axenovich and R

    M. Axenovich and R. R. Martin. On the strong chromatic number of graphs.SIAM J. Discret. Math., 20(3):741–747, 2006

    2006

  5. [5]

    H. Aziz, S. Gaspers, S. Mackenzie, and T. Walsh. Fair assignment of indivisible objects under ordinal preferences.Artif. Intell., 227:71–92, 2015. Preliminary version in AAMAS’14

    2015

  6. [6]

    Barman, S

    S. Barman, S. Ebadian, M. Latifian, and N. Shah. Fair division with market values. InProc. of the 39th AAAI Conference on Artificial Intelligence (AAAI’25), pages 13589–13596, 2025

    2025

  7. [7]

    Equitable Colorings of Vertex-Weighted Graphs

    S. Barman and V . Viswanathan. Equitable colorings of vertex-weighted graphs.arXiv preprint, abs/2605.09320, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  8. [8]

    Biswas and S

    A. Biswas and S. Barman. Fair division under cardinality constraints. InProc. of the 27th International Joint Conference on Artificial Intelligence (IJCAI’18), pages 91–97, 2018

    2018

  9. [9]

    Biswas and S

    A. Biswas and S. Barman. Matroid constrained fair allocation problem. InProc. of the 33rd AAAI Conference on Artificial Intelligence (AAAI’19), pages 9921–9922, 2019. 30

    2019

  10. [10]

    Bogomolnaia and H

    A. Bogomolnaia and H. Moulin. A new solution to the random assignment problem.J. Econ. Theory, 100(2):295–328, 2001

    2001

  11. [11]

    E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.J. Polit. Econ., 119(6):1061–1103, 2011. Preliminary version in BQGT’10

    2011

  12. [12]

    Caragiannis, D

    I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The unrea- sonable fairness of maximum Nash welfare.ACM Trans. Econ. Comput., 7(3):12:1–32, 2019. Preliminary version in EC’16

    2019

  13. [13]

    Chiarelli, M

    N. Chiarelli, M. Krnc, M. Milani ˇc, U. Pferschy, N. Pivaˇc, and J. Schauer. Fair allocation of in- divisible items with conflict graphs.Algorithmica, 85(5):1459–1489, 2023. Preliminary version in IWOCA’20

    2023

  14. [14]

    Cookson, S

    B. Cookson, S. Ebadian, and N. Shah. Constrained fair and efficient allocations. InProc. of the 39th AAAI Conference on Artificial Intelligence (AAAI’25), pages 13718–13726, 2025

    2025

  15. [15]

    Fair Allocation under Conflict Constraints

    S. Equbal, R. Gurjar, A. Igarashi, Y. Kumar, P . Manurangsi, S. Nath, R. Saxena, R. Vaish, and H. Yoneda. Fair allocation under conflict constraints.arXiv preprint, abs/2605.09930, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  16. [16]

    P . Erd˝os. On some of my favourite problems in graph theory and block designs.Le Matem- atiche, 45(1):61–74, 1990

    1990

  17. [17]

    M. R. Fellows. Transversals of vertex partitions in graphs.SIAM J. Discret. Math., 3(2):206– 215, 1990

    1990

  18. [18]

    Fleischner and M

    H. Fleischner and M. Stiebitz. A solution to a colouring problem of P . Erd ˝os.Discret. Math., 101(1–3):39–48, 1992

    1992

  19. [19]

    Fleischner and M

    H. Fleischner and M. Stiebitz. Some remarks on the cycle plus triangles problem. InThe Math- ematics of Paul Erd˝ os II, volume 14 ofAlgorithms and Combinatorics, pages 136–142. Springer, 1997

    1997

  20. [20]

    A. Graf, D. G. Harris, and P . Haxell. Algorithms for weighted independent transversals and strong colouring.ACM Trans. Algorithms, 18(1):1:1–16, 2022. Preliminary version in SODA’21

    2022

  21. [21]

    Graf and P

    A. Graf and P . Haxell. Finding independent transversals efficiently.Comb. Probab. Comput., 29(5):780–806, 2020

    2020

  22. [22]

    S. Gutner. Choice numbers of graphs. M.Sc. thesis, Tel Aviv University, 1992

    1992

  23. [23]

    Gutner and M

    S. Gutner and M. Tarsi. Some results on(a:b)-choosability.Discret. Math., 309(8):2260–2270, 2009

    2009

  24. [24]

    D. G. Harris. Deterministic algorithms for the Lov ´asz local lemma: Simpler, more general, and more parallel.Random Struct. Algorithms, 63(3):716–752, 2023. Preliminary version in SODA’22. 31

    2023

  25. [25]

    D. G. Harris and A. Srinivasan. A constructive Lov ´asz local lemma for permutations.Theory Comput., 13(1):1–41, 2017. Preliminary version in SODA’14

    2017

  26. [26]

    I. Haviv. The complexity of finding fair independent sets in cycles.Comput. Complex., 31(2):14:1–32, 2022. Preliminary version in ITCS’21

    2022

  27. [27]

    P . E. Haxell. On the strong chromatic number.Comb. Probab. Comput., 13(6):857–865, 2004

    2004

  28. [28]

    Hummel and M

    H. Hummel and M. L. Hetland. Fair allocation of conflicting items.Auton. Agents Multi Agent Syst., 36(1):8:1–33, 2022

    2022

  29. [29]

    Igarashi

    A. Igarashi. How to cut a discrete cake fairly. InProc. of the 37th AAAI Conference on Artificial Intelligence (AAAI’23), pages 5681–5688, 2023

    2023

  30. [30]

    Igarashi, P

    A. Igarashi, P . Manurangsi, and H. Yoneda. Dividing conflicting items fairly. InProc. of the 34th International Joint Conference on Artificial Intelligence (IJCAI’25), pages 3908–3915, 2025

    2025

  31. [31]

    Kumar, S

    Y. Kumar, S. Equbal, R. Gurjar, S. Nath, and R. Vaish. Fair scheduling of indivisible chores. InProc. of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AA- MAS’24), pages 2345–2347, 2024

    2024

  32. [32]

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

    2004

  33. [33]

    Leveraging Matchings in Constrained Fair Division with a Conflict Graph

    E. Markakis and M. Samaris. Leveraging matchings in constrained fair division with a con- flict graph.arXiv preprint, abs/2606.13083, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  34. [34]

    L.-D. ¨Ohman. Strong chromatic numbers of graphs with maximum degree 2. Manuscript, available at author’s website

  35. [35]

    H. Sachs. Elementary proof of the cycle-plus-triangles theorem. InCombinatorics, Paul Erd˝ os is eighty, volume 1 ofBolyai Soc. Math. Stud., pages 347–359. J ´anos Bolyai Math. Soc., 1993

    1993

  36. [36]

    Shoshan, N

    H. Shoshan, N. Hazon, and E. Segal-Halevi. Efficient nearly-fair division with capacity con- straints. InProc. of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS’23), pages 206–214, 2023

    2023

  37. [37]

    Suksompong

    W. Suksompong. Constraints in fair division.SIGecom Exch., 19(2):46–61, 2021. 32

    2021