Dividing Conflicting Items Fairly
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915348232536064 |
|---|---|
| author | Igarashi, Ayumi Manurangsi, Pasin Yoneda, Hirotaka |
| author_facet | Igarashi, Ayumi Manurangsi, Pasin Yoneda, Hirotaka |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_14149 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dividing Conflicting Items Fairly Igarashi, Ayumi Manurangsi, Pasin Yoneda, Hirotaka Computer Science and Game Theory 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. |
| title | Dividing Conflicting Items Fairly |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2506.14149 |