arxiv: 2605.09930 · v1 · submitted 2026-05-11 · 💻 cs.GT

Recognition: 2 theorem links

· Lean Theorem

Fair Allocation under Conflict Constraints

Ayumi Igarashi, Hirotaka Yoneda, Pasin Manurangsi, Raghuvansh Saxena, Rohit Gurjar, Rohit Vaish, Sarfaraz Equbal, Swaprava Nath, Yatharth Kumar

Pith reviewed 2026-05-12 04:17 UTC · model grok-4.3

classification 💻 cs.GT

keywords fair allocationEF1conflict graphindependent setsmonotone valuationsenvy-free up to onemaximal allocationNP-hardness

0 comments

The pith

For any conflict graph, two agents with monotone valuations always admit a maximal EF1 allocation.

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

The paper studies allocation of indivisible items where conflicts prevent certain pairs from being assigned to the same agent, modeled as independent sets in a graph. It establishes that for two agents whose valuations are monotone, a maximal allocation satisfying envy-freeness up to one item always exists. The proof introduces a color-switching method that adjusts a given maximal allocation locally to eliminate envy while keeping assignments feasible. In contrast, dropping monotonicity or increasing to three agents makes such allocations nonexistent in some cases and hard to decide in general, with a positive result only for identical non-monotone additive valuations on path graphs.

Core claim

For two agents with monotone valuations, a maximal EF1 allocation always exists on any graph. The existence proof relies on a color-switching technique, which locally modifies a maximal allocation while preserving feasibility and restoring EF1. Such allocations can be computed in pseudopolynomial time in general, and in polynomial time for additive valuations on arbitrary graphs as well as monotone valuations on interval and bipartite graphs. For three or more agents, an EF1 and maximal allocation fails to exist even under identical monotone valuations, and deciding existence is NP-hard. Under identical non-monotone additive valuations on a path graph, an EF[1,1] and maximal allocation is gu

What carries the argument

color-switching technique that locally modifies a maximal allocation to restore EF1 while preserving feasibility

If this is right

For two agents with monotone valuations a maximal EF1 allocation can always be produced no matter what the underlying conflict graph is.
Such allocations are computable in polynomial time when valuations are additive or the graph is an interval graph or bipartite graph.
For three agents with identical monotone valuations no EF1 maximal allocation is guaranteed to exist.
Deciding whether an EF1 and maximal allocation exists is NP-hard in general.
On path graphs with identical non-monotone additive valuations an EF[1,1] and maximal allocation is always guaranteed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The color-switching repair might be adaptable to other fairness criteria such as proportionality or to graphs with additional structure.
Real-world scheduling problems with resource conflicts could directly use the two-agent existence result as a starting point for algorithmic implementations.
The hardness results for three or more agents indicate that practical systems may need to relax maximality or fairness when the number of participants grows.
The application of the cycle-plus-triangles theorem on paths suggests similar graph-theoretic tools could resolve existence questions on other restricted graph families.

Load-bearing premise

Valuations are monotone so that adding an item never decreases an agent's value.

What would settle it

A concrete graph together with two agents having monotone valuations where every maximal allocation leaves at least one agent envious even after removing one item.

Figures

Figures reproduced from arXiv: 2605.09930 by Ayumi Igarashi, Hirotaka Yoneda, Pasin Manurangsi, Raghuvansh Saxena, Rohit Gurjar, Rohit Vaish, Sarfaraz Equbal, Swaprava Nath, Yatharth Kumar.

**Figure 1.** Figure 1: Summary of our results. The arrows denote logical implications between fairness and efficiency notions. The positive and negative results are shown in green and red, respectively. Example 2 (Non-existence of EF1+Pareto optimality for goods). Consider an instance with two agents 1 and 2 and six goods o1, . . . , o6 that are identically valued by the agents at 1, 2, 1, 2, 1, 2, respectively. The conflict gra… view at source ↗

**Figure 2.** Figure 2: A depiction of Algorithm 1 on two input graphs. It can be verified that all allocations are maximal and every pair of consecutive allocation is order-adjacent. For some vertices, the values max-conf(·) and min-conf(·) computed in Algorithm 1 are depicted using curved arrows. Finally, the assignments (Ao = (Ao,1, Ao,2))o∈{0}∪[m] are shown in order under the graphs, with the elements of Ao,1 colored red and … view at source ↗

**Figure 3.** Figure 3: 6 maximal allocations to consider in the instance of Theorem 5.1. 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 5.1 uses an identical monotone valuation. It remains an open question whether a counterexample exists for three agents with (even identical) additive and monotone valuations on general graphs… view at source ↗

**Figure 4.** Figure 4: Instance I created with n = 4 instance given by Proposition 2 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.2 Identical Additive Valuations on a Path We will now establish a positive result for identical additive valuations when the conflict graph is a path (Theorem 5.3). Theorem 5.3. Given any instance with n ≥ 3 age… view at source ↗

**Figure 5.** Figure 5: An illustration of the reduction in the proof of Theorem 5.3 for n = 3 agents. Subfigure (a) shows the path graph consisting of ten original items o7, o10, . . . , o3 and two dummy items o11 and o12 (denoted by shaded nodes). The dummy items can be considered to be an extension of the path graph as shown. Subfigure (b) shows the corresponding cycle-plus-n-cliques graph H. We divide the items into groups of… view at source ↗

**Figure 6.** Figure 6: A 3-coloring of the graph H shown in [PITH_FULL_IMAGE:figures/full_fig_p027_6.png] view at source ↗

read the original abstract

We study the fair allocation of indivisible items subject to conflict constraints. In this framework, the items are represented as the vertices of a graph, with edges corresponding to conflicts between pairs of items. Each agent is assigned an independent set of items from the graph. Our goal is to achieve a fair and efficient allocation of these items. Fairness pertains to satisfying envy-freeness up to one item (EF1), while efficiency is defined by maximality, meaning that no unallocated item can be feasibly assigned to any agent. First, we explore the case of two agents. For monotone valuations, we show that a maximal EF1 allocation always exists on any graph. Our existence proof relies on a color-switching technique, which locally modifies a maximal allocation while preserving feasibility and restoring EF1. We further show that such allocations can be computed in pseudopolynomial time in general, and in polynomial time for additive valuations on arbitrary graphs, as well as for monotone valuations on interval and bipartite graphs. By contrast, once monotonicity is dropped, maximal EF1 allocations need not exist even for identical additive valuations, and deciding existence becomes NP-hard. Next, we consider the case with a general number of agents. Again, we arrive at a negative result: An EF1 and maximal allocation fails to exist even for three agents under identical monotone valuations, and determining the existence of such an allocation is NP-hard. On the positive side, we show that under identical non-monotone additive valuations on a path graph, an EF[1,1] and maximal allocation always exists. This result involves a novel application of the "cycle plus triangles" theorem.

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.

Desk Editor's Note private letter to a colleague

Two-agent monotone EF1 existence via color-switching is the solid new result, but multi-agent cases are mostly negative.

read the letter

The main thing to know is that for two agents with monotone valuations, a maximal EF1 allocation exists on any conflict graph, shown by starting from a maximal allocation and using color-switching along paths or cycles to fix envy without violating independence or maximality. The paper also gives a positive result for identical additive valuations on paths by applying the cycle-plus-triangles theorem to get EF[1,1] plus maximality. Hardness and non-existence kick in quickly once you drop monotonicity or add a third agent, even with identical monotone valuations.

Referee Report

2 major / 2 minor

Summary. The paper studies fair allocation of indivisible items under conflict constraints, modeled as a graph where each agent receives an independent set. For two agents with monotone valuations, it proves existence of a maximal EF1 allocation on arbitrary graphs via a color-switching technique that locally modifies allocations while preserving feasibility and EF1. It gives pseudopolynomial-time algorithms in general and polynomial-time algorithms for additive valuations on arbitrary graphs and monotone valuations on interval and bipartite graphs. Without monotonicity, maximal EF1 allocations need not exist (even for identical additive valuations) and existence is NP-hard. For multiple agents, EF1 + maximal allocations fail to exist even for three agents with identical monotone valuations, and existence is NP-hard; however, EF[1,1] + maximal allocations exist for identical non-monotone additive valuations on path graphs, via a novel application of the cycle-triangle theorem.

Significance. If the proofs hold, the work meaningfully extends fair division to graph-constrained settings by characterizing when maximality and (approximate) envy-freeness can coexist. The color-switching argument, the explicit non-existence constructions, the complexity results, and the application of the cycle-triangle theorem are all strengths that could influence follow-up work on constrained fair allocation. The computational results for restricted graph classes are practically relevant.

major comments (2)

[§3] §3 (two-agent monotone case): the color-switching procedure is claimed to terminate by strictly decreasing total envy while preserving maximality and independent-set feasibility; the case analysis on the envy graph must explicitly verify that monotonicity prevents new envy violations or maximality breaches in every configuration, including when the switch affects multiple agents' bundles.
[§5] §5 (multi-agent negative result): the non-existence claim for three agents with identical monotone valuations is witnessed by an explicit construction; the construction must be checked to ensure the conflict graph forces the independent-set constraint to interact with the valuation in a way that blocks all maximal EF1 allocations.

minor comments (2)

The precise definition of EF[1,1] (as opposed to EF1) should be stated formally in the introduction or preliminaries, with a brief comparison to standard EF1.
The pseudopolynomial-time algorithm for general monotone valuations (mentioned in the abstract) would benefit from a high-level pseudocode or complexity breakdown in the main text rather than only in the appendix.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their positive evaluation and insightful comments, which help clarify the presentation of our results. We address each major comment below and will incorporate the suggested clarifications in the revised manuscript.

read point-by-point responses

Referee: [§3] §3 (two-agent monotone case): the color-switching procedure is claimed to terminate by strictly decreasing total envy while preserving maximality and independent-set feasibility; the case analysis on the envy graph must explicitly verify that monotonicity prevents new envy violations or maximality breaches in every configuration, including when the switch affects multiple agents' bundles.

Authors: We agree that the termination argument benefits from a more exhaustive case analysis. In the revision, we will expand the proof of the color-switching procedure in §3 to enumerate all relevant envy-graph configurations for two agents. For each configuration, we will explicitly show that monotonicity ensures the switch strictly decreases total envy, preserves EF1 (no new violations are introduced), and maintains both maximality and independent-set feasibility. This includes the cases where the switch modifies bundles of both agents simultaneously, with direct verification that no new conflicts arise under the graph constraints. revision: yes
Referee: [§5] §5 (multi-agent negative result): the non-existence claim for three agents with identical monotone valuations is witnessed by an explicit construction; the construction must be checked to ensure the conflict graph forces the independent-set constraint to interact with the valuation in a way that blocks all maximal EF1 allocations.

Authors: The explicit construction in §5 is designed precisely so that the conflict graph restricts feasible independent sets in a way that interacts with the identical monotone valuations to eliminate all maximal EF1 allocations. In the revised manuscript, we will add a detailed walkthrough of the construction, enumerating the possible maximal allocations and showing in each case how the graph-induced constraints force an EF1 violation. This makes the interaction between the graph and valuations fully explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; proofs rely on independent graph-theoretic arguments

full rationale

The paper's core results are existence proofs for maximal EF1 allocations (via color-switching on the conflict graph and a decreasing potential function on total envy) and NP-hardness/non-existence via explicit counterexamples and reductions. These steps are self-contained algorithmic constructions and standard complexity arguments that do not reduce to fitted parameters, self-definitional equivalences, or load-bearing self-citations. Monotonicity is an explicit assumption used in case analysis, not smuggled in; the cycle-plus-triangles theorem is an external graph-theoretic fact. The derivation chain stands independently of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard definition of EF1 and maximality, the assumption that valuations are monotone for the two-agent positive result, and the cycle-plus-triangles theorem from graph theory. No free parameters or invented entities are introduced.

axioms (2)

domain assumption Valuations are monotone for the two-agent existence theorem
Invoked explicitly for the color-switching argument on arbitrary graphs
standard math Cycle-plus-triangles theorem holds for the path-graph positive result
Used to guarantee EF[1,1] and maximality for identical non-monotone additive valuations

pith-pipeline@v0.9.0 · 5635 in / 1490 out tokens · 38598 ms · 2026-05-12T04:17:18.340614+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
Our existence proof relies on a color-switching technique, which locally modifies a maximal allocation while preserving feasibility and restoring EF1.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
the valuations are monotone (adding an item never decreases value)

Reference graph

Works this paper leans on

110 extracted references · 110 canonical work pages

[1]

Karp , editor =

Richard M. Karp , editor =. Proceedings of a Symposium on the Complexity of Computer Computations , series =

work page
[2]

Li, Bo and Li, Minming and Zhang, Ruilong , journal=

work page
[3]

ACM Transactions on Economics and Computation , volume=

Caragiannis, Ioannis and Kurokawa, David and Moulin, Herv. ACM Transactions on Economics and Computation , volume=

work page
[4]

Varian, Hal R , journal=

work page
[5]

Budish, Eric , journal=

work page
[6]

Brams, Steven J and Taylor, Alan D , year=

work page
[7]

1967 , pages=

Foley, Duncan , journal=. 1967 , pages=

work page 1967
[8]

Barman, Siddharth and Krishnamurthy, Sanath Kumar and Vaish, Rohit , booktitle=

work page
[9]

Lipton, Richard J and Markakis, Evangelos and Mossel, Elchanan and Saberi, Amin , booktitle=

work page
[10]

2017 , author=

Information Processing Letters , volume=. 2017 , author=

work page 2017
[11]

and Johnson, David S

Garey, Michael R. and Johnson, David S. , year =

work page
[12]

Aziz, Haris and Caragiannis, Ioannis and Igarashi, Ayumi and Walsh, Toby , booktitle=

work page
[13]

Traxler, Martino , journal=

work page
[14]

Theoretical Computer Science , volume=

Bil. Theoretical Computer Science , volume=. 2016 , pages=

work page 2016
[15]

Gardner, Martin , publisher=

work page
[16]

Freeman, Rupert and Sikdar, Sujoy and Vaish, Rohit and Xia, Lirong , booktitle=

work page
[17]

Freeman, Rupert and Shah, Nisarg and Vaish, Rohit , booktitle=

work page
[18]

Operations Research , volume=

Budish, Eric and Cachon, G. Operations Research , volume=. 2017 , publisher=

work page 2017
[19]

Bhaskar, Umang and Sricharan, AR and Vaish, Rohit , booktitle=

work page
[20]

Gamow, George and Stern, Marvin , journal=

work page
[21]

2020 , publisher=

Plaut, Benjamin and Roughgarden, Tim , journal=. 2020 , publisher=

work page 2020
[22]

Steinhaus, Hugo , journal=

work page
[23]

Conitzer, Vincent and Freeman, Rupert and Shah, Nisarg , booktitle=

work page
[24]

Annual Review of Economics , volume=

Moulin, Herv. Annual Review of Economics , volume=. 2019 , publisher=

work page 2019
[25]

Dubins, Lester E and Spanier, Edwin H , journal=

work page
[26]

Proceedings of the 21st European Conference on Artificial Intelligence , pages=

Gourv. Proceedings of the 21st European Conference on Artificial Intelligence , pages=

work page
[27]

Garg, Jugal and Murhekar, Aniket and Qin, John , booktitle=

work page
[28]

arXiv preprint arXiv:2003.11313 , year=

Chiarelli, Nina and Krnc, Matja. arXiv preprint arXiv:2003.11313 , year=

work page arXiv 2003
[29]

Hummel, Halvard and Hetland, Magnus Lie , journal=

work page
[30]

The Division Problem with Single-Peaked Preferences: A Characterization of the Uniform Allocation Rule , year =

Sprumont, Yves , journal =. The Division Problem with Single-Peaked Preferences: A Characterization of the Uniform Allocation Rule , year =

work page
[31]

Swaprava Nath , title =

work page
[32]

2013 , number =

Morimoto, Shuhei and Serizawa, Shigehiro and Ching, Stephen , journal =. 2013 , number =

work page 2013
[33]

Ebadian, Soroush and Peters, Dominik and Shah, Nisarg , booktitle=

work page
[34]

Hosseini, Hadi and Igarashi, Ayumi and Searns, Andrew , booktitle=

work page
[35]

1992 , publisher=

Hsiao, Ju Yuan and Tang, Chuan Yi and Chang, Ruay Shiung , journal=. 1992 , publisher=

work page 1992
[36]

Zhou, Shengwei and Wu, Xiaowei , booktitle=

work page
[37]

Li, Bo and Li, Yingkai and Wu, Xiaowei , journal=

work page
[38]

Chen, Xingyu and Liu, Zijie , journal=

work page
[39]

Sun, Ankang and Chen, Bo and Doan, Xuan Vinh , journal=

work page
[40]

de Keijzer, Bart and Bouveret, Sylvain and Klos, Tomas and Zhang, Yingqian , booktitle=

work page
[41]

2008 , publisher=

Kierstead, Hal A and Kostochka, Alexandr V , journal=. 2008 , publisher=

work page 2008
[42]

Biswas, Arpita and Ke, Yiduo and Khuller, Samir and Liu, Quanquan C , booktitle=

work page
[43]

Artificial Intelligence , pages=

Amanatidis, Georgios and Aziz, Haris and Birmpas, Georgios and Filos-Ratsikas, Aris and Li, Bo and Moulin, Herv. Artificial Intelligence , pages=. 2023 , publisher=

work page 2023
[44]

Chaudhury, Bhaskar Ray and Garg, Jugal and Mehlhorn, Kurt , booktitle=

work page
[45]

2021 , publisher=

Suksompong, Warut , journal=. 2021 , publisher=

work page 2021
[46]

Algorithmica , volume=

Chiarelli, Nina and Krnc, Matja. Algorithmica , volume=. 2023 , publisher=

work page 2023
[47]

Proceedings of the 26th International Joint Conference on Artificial Intelligence , pages=

Bouveret, Sylvain and Cechl. Proceedings of the 26th International Joint Conference on Artificial Intelligence , pages=

work page
[48]

Games and Economic Behavior , volume=

Bil. Games and Economic Behavior , volume=. 2022 , publisher=

work page 2022
[49]

Autonomous Agents and Multi-Agent Systems , volume=

Beynier, Aur. Autonomous Agents and Multi-Agent Systems , volume=. 2019 , publisher=

work page 2019
[50]

2022 , publisher=

Bredereck, Robert and Kaczmarczyk, Andrzej and Niedermeier, Rolf , journal=. 2022 , publisher=

work page 2022
[51]

Hosseini, Hadi and Payan, Justin and Sengupta, Rik and Vaish, Rohit and Viswanathan, Vignesh , booktitle=

work page
[52]

Abebe, Rediet and Kleinberg, Jon and Parkes, David C , booktitle=

work page
[53]

Autonomous Agents and Multi-Agent Systems , volume=

Bouveret, Sylvain and Cechl. Autonomous Agents and Multi-Agent Systems , volume=. 2019 , publisher=

work page 2019
[54]

and Szemer\'

Hajnal, A. and Szemer\'. Combinatorial Theory and Its Applications,. 1970 , MRCLASS =

work page 1970
[55]

2001 , publisher=

West, Douglas Brent , volume=. 2001 , publisher=

work page 2001
[56]

1998 , publisher=

Ajtai, Miklos and Aspnes, James and Naor, Moni and Rabani, Yuval and Schulman, Leonard J and Waarts, Orli , journal=. 1998 , publisher=

work page 1998
[57]

2020 , publisher=

Im, Sungjin and Moseley, Benjamin , journal=. 2020 , publisher=

work page 2020
[58]

Leung, Joseph YT , year=

work page
[59]

Igarashi, Ayumi and Yokoyama, Tomohiko , booktitle=

work page
[60]

2022 , publisher=

Oxley, James , booktitle=. 2022 , publisher=

work page 2022
[61]

Benabbou, Nawal and Chakraborty, Mithun and Ho, Xuan-Vinh and Sliwinski, Jakub and Zick, Yair , journal=

work page
[62]

2015 , publisher=

Goldman, Jonathan and Procaccia, Ariel D , journal=. 2015 , publisher=

work page 2015
[63]

2016 , publisher=

Brandt, Felix and Conitzer, Vincent and Endriss, Ulle and Lang, J. 2016 , publisher=

work page 2016
[64]

Biswas, Arpita and Barman, Siddharth , booktitle=

work page
[65]

Dror, Amitay and Feldman, Michal and Segal-Halevi, Erel , journal=

work page
[66]

Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS) , pages =

Hila Shoshan and Noam Hazon and Erel Segal-Halevi , title =. Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS) , pages =

work page
[67]

1997 , publisher=

Fleischner, Herbert and Stiebitz, Michael , journal=. 1997 , publisher=

work page 1997
[68]

1990 , publisher=

Fellows, Michael R , journal=. 1990 , publisher=

work page 1990
[69]

1992 , publisher=

Fleischner, Herbert and Stiebitz, Michael , journal=. 1992 , publisher=

work page 1992
[70]

1992 , publisher=

Alon, Noga and Tarsi, Michael , journal=. 1992 , publisher=

work page 1992
[71]

Alon, Noga , journal=

work page
[72]

1988 , publisher=

Alon, Noga , journal=. 1988 , publisher=

work page 1988
[73]

1992 , publisher=

Alon, Noga , journal=. 1992 , publisher=

work page 1992
[74]

Le Matematiche , volume=

Erd. Le Matematiche , volume=

work page
[75]

1999 , publisher=

Alon, Noga , journal=. 1999 , publisher=

work page 1999
[76]

2022 , publisher=

Haviv, Ishay , journal=. 2022 , publisher=

work page 2022
[77]

2017 , publisher=

Aharoni, Ron and Alon, Noga and Berger, Eli and Chudnovsky, Maria and Kotlar, Dani and Loebl, Martin and Ziv, Ran , booktitle=. 2017 , publisher=

work page 2017
[78]

Igarashi, Ayumi and Manurangsi, Pasin and Yoneda, Hirotaka , booktitle=

work page
[79]

2023 , publisher=

Jana, Satyabrata and Maheshwari, Anil and Mehrabi, Saeed and Roy, Sasanka , journal=. 2023 , publisher=

work page 2023
[80]

Kleinberg, Jon and Tardos, Eva , year=

work page

Showing first 80 references.