Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average
SIAM Journal on Discrete Mathematics · 31.03.2025 · 39 (1) · 533-549
DOI: 10.1137/24m1631407 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 01.03.2025. Verfasst von Yusuke Kobayashi und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 30 Literaturangaben. Gefördert von: Japan Science and Technology Agency, Japan Society for the Promotion of Science.
Abstract (Originalsprache)
We study the problem of fairly allocating a set of indivisible goods to multiple agents and focus on the proportionality, which is one of the classical fairness notions. Since proportional allocations do not always exist when goods are indivisible, approximate concepts of proportionality have been considered in previous work. Among them, proportionality up to the maximin good ( PROPm ) has been the best approximate notion of proportionality that can be achieved for all instances [A. Baklanov et al., PROPm allocations of indivisible goods to multiple agents, in Proceedings of the 30th International Joint Conference on Artificial Intelligence, 2021, pp. 24–30]. In this paper, we introduce the notion of proportionality up to the least valued good on average ( PROPavg ), which is a stronger notion than PROPm , and show that a PROPavg allocation always exists for all instances and can be computed in polynomial time. Our results establish PROPavg as a notable nontrivial fairness notion that can be achieved for all instances. Our proof is constructive and is based on a new technique that generalizes the cut-and-choose protocol and uses a recursive technique.
Förderung
- Japan Science and Technology Agency
- Japan Society for the Promotion of Science
Zitieren
APA
Kobayashi, Y., & Mahara, R. (2025). Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average. SIAM Journal on Discrete Mathematics, 39(1), 533-549. https://doi.org/10.1137/24m1631407
Vancouver
Kobayashi Y, Mahara R. Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average. SIAM Journal on Discrete Mathematics. 2025;39(1):533-549. doi:10.1137/24m1631407
BibTeX
@article{Kobayashi2025,
author = {Kobayashi, Yusuke and Mahara, Ryoga},
title = {Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average},
journal = {SIAM Journal on Discrete Mathematics},
year = {2025},
volume = {39},
number = {1},
pages = {533--549},
doi = {10.1137/24m1631407}
}
EUVIMED