---
title: "Dividing Conflicting Items Fairly"
authors:
  - "Ayumi Igarashi"
  - "Pasin Manurangsi"
  - "Hirotaka Yoneda"
doi: "10.24963/ijcai.2025/435"
url: "https://ijcai.org/proceedings/2025/435"
pdf: "https://ijcai.org/proceedings/2025/0435.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "3908-3915"
track: "Main Track"
keywords:
  - "Game Theory and Economic Paradigms: GTEP: Computational social choice"
  - "Game Theory and Economic Paradigms: GTEP: Fair division"
---

# Dividing Conflicting Items Fairly

Ayumi Igarashi, Pasin Manurangsi, Hirotaka Yoneda

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 3908-3915. DOI: [10.24963/ijcai.2025/435](https://doi.org/10.24963/ijcai.2025/435)

## 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. (AAMAS, 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 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 >= 3 of agents. All of our results for goods also apply to the allocation of chores.