2025/03/07 by Vittorio Bilò, Bilò, Vittorio, Martin Loebl +3
Computer Science · Economics, Econometrics and Finance · Mathematics · #Advanced Banach Space Theory #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Economic theories and models #FOS: Computer and information sciences #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.2503.05695
openalex publication_date 2025/03/07 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
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's Lemma and its variants), we establish the existence of \em envy-free-up-to-one-good-and-one-chore (EF1cg) and \em equitable-up-to-one-good-and-one-chore (EQ1cg) allocations, for non-monotone valuations that are always either non-negative or non-positive. These notions represent slight relaxations of the well-studied \em envy-free-up-to-one-item (EF1) and \em equitable-up-to-one-item (EQ1) guarantees, respectively. Our existential results hold even when items are arranged in a path and bundles must form connected sub-paths. The case of non-positive valuations, in particular, has been solved by proving a novel multi-coloring variant of Sperner's Lemma that constitutes a combinatorial result of independent interest. In addition, we also design a polynomial-time dynamic programming algorithm that computes an EQ1cg allocation. For monotone non-increasing valuations and path-connected bundles, all the above results can be extended to EF1 and EQ1 guarantees as well. Finally, we provide existential and computational results for certain stronger \em up-to-any-item equity notions under objective valuations, where items are partitioned into goods and chores.