Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations

Vittorio Bilò; Martin Loebl; Cosimo Vinci

AAAI 2026technical0 citations

Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations

Vittorio Bilò, Martin Loebl, Cosimo Vinci

Abstract

We revisit the setting of fair allocation of indivisible items among agents with heterogeneous, non-monotone valuations. We explore the existence and efficient computation of allocations that approximately satisfy either envy-freeness or equity constraints. Approximate envy-freeness ensures that each agent values her bundle at least as much as those given to the others, after some (or any) item removal, while approximate equity guarantees roughly equal valuations among agents, under similar adjustments. As a key technical contribution of this work, by leveraging fixed-point theorems (such as Sperner

BibTeX

@inproceedings{aaai2026_approximatelyenv,
  title = {Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations},
  author = {Vittorio Bilò and Martin Loebl and Cosimo Vinci},
  booktitle = {AAAI 2026},
  year = {2026}
}