Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2602.20929 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
Sommario:
- We study the fair division of indivisible goods with conflicts between pairs of goods, represented by a graph $G = (V, E)$. We consider ``soft'' conflicts: assigning two adjacent goods to the same agent is allowed, but we seek allocations that are envy-free up to one good (EF1) while keeping the number of such conflict violations small. We propose a linear-time algorithm for general additive valuations that finds an EF1 allocation with at most $|E|/n + O(|E|^{1-1/(2n-2)})$ violations, for any constant number of agents $n$. The leading term $|E|/n$ matches the worst-case bound on the number of violations. We use a novel approach that combines an algorithm for fair division with cardinality constraints from Biswas \& Barman (2018) and a geometric ``closest points'' argument. For identical additive valuations, we also propose a simple round-robin-based algorithm that finds an EF1 allocation with at most $|E|/n$ violations.