Approximating Proportional and Maximin Allocations on D-Claw-Free Graphs
Journal of Artificial Intelligence Research · 28.02.2026 · 85
DOI: 10.1613/jair.1.17263 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 28.02.2026. Verfasst von Zbigniew Lonc.
Abstract (Originalsprache)
We study the problem of fair allocation of indivisible goods that form a graph and the bundles that are distributed to agents are connected subgraphs of this graph. We focus on the proportional and the maximin share fairness criteria. It is well-known that allocations satisfying these criteria may not exist for many graphs including complete graphs and cycles. Therefore, it is natural to look for approximate allocations, i.e., allocations guaranteeing each agent a certain portion of the value that is satisfactory to her. In this paper we consider the class of graphs of goods which do not contain a star with d+1 edges (where d > 1) as an induced subgraph. This is a large class of graphs containing graphs with the maximum degree bounded by d. For this class of graphs we show a theorem which specifies what fraction of the proportional share can be guaranteed to each of n agents if the values of single goods for the agents are bounded by a given fraction of this share. Furthermore, an allocation ensuring such a guarantee can be computed in polynomial time. This theorem can be viewed as analogous to a result by Hill in1987, who solved a similar problem for proportional allocations without connectivity constraints. Moreover, for the same class of graphs of goods, we prove that there is an allocation assigning each of n agents a connected bundle of value at least n/(d(n-1)+1) > 1/d of her maximin share, and this allocation can be computed in polynomial time.
Zitieren
APA
Lonc, Z. (2026). Approximating Proportional and Maximin Allocations on D-Claw-Free Graphs. Journal of Artificial Intelligence Research, 85. https://doi.org/10.1613/jair.1.17263
Vancouver
Lonc Z. Approximating Proportional and Maximin Allocations on D-Claw-Free Graphs. Journal of Artificial Intelligence Research. 2026;85. doi:10.1613/jair.1.17263
BibTeX
@article{Lonc2026,
author = {Lonc, Zbigniew},
title = {Approximating Proportional and Maximin Allocations on D-Claw-Free Graphs},
journal = {Journal of Artificial Intelligence Research},
year = {2026},
volume = {85},
doi = {10.1613/jair.1.17263}
}
EUVIMED