Group-Fair Allocations of Contiguous Blocks of Indivisible Items

Hau Chan, Minming Li, Yingchao Zhao, Shangkun Zheng
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:981-1002, 2026.

Abstract

We study the problem of allocating contiguous blocks of indivisible items positioned on a line to a set of agents where agents are partitioned into different groups. In the problem, agents must be located on a line, and items allocated to each agent must be contiguous and form a connected block. We study the settings, considered by Suksompong [2019] and Wang et al. [2021], without and with the requirement that items are assigned to their closest agents, respectively. For both settings, we focus on allocations that satisfy intra-group envy fairness (IEF) and inter-group fair share (GFS). In both settings, we show that determining the existence of IEF or GFS allocations is NP-complete. When the number of agents or items is constant, we provide polynomial algorithms to determine the existence of IEF or GFS allocations for both settings. For both settings, we provide upper and lower bounds on the existence of IEF or GFS allocations as well as allocations that satisfy both IEF and GFS simultaneously.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-chan26a, title = {Group-Fair Allocations of Contiguous Blocks of Indivisible Items}, author = {Chan, Hau and Li, Minming and Zhao, Yingchao and Zheng, Shangkun}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {981--1002}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/chan26a/chan26a.pdf}, url = {https://proceedings.mlr.press/v337/chan26a.html}, abstract = {We study the problem of allocating contiguous blocks of indivisible items positioned on a line to a set of agents where agents are partitioned into different groups. In the problem, agents must be located on a line, and items allocated to each agent must be contiguous and form a connected block. We study the settings, considered by Suksompong [2019] and Wang et al. [2021], without and with the requirement that items are assigned to their closest agents, respectively. For both settings, we focus on allocations that satisfy intra-group envy fairness (IEF) and inter-group fair share (GFS). In both settings, we show that determining the existence of IEF or GFS allocations is NP-complete. When the number of agents or items is constant, we provide polynomial algorithms to determine the existence of IEF or GFS allocations for both settings. For both settings, we provide upper and lower bounds on the existence of IEF or GFS allocations as well as allocations that satisfy both IEF and GFS simultaneously.} }
Endnote
%0 Conference Paper %T Group-Fair Allocations of Contiguous Blocks of Indivisible Items %A Hau Chan %A Minming Li %A Yingchao Zhao %A Shangkun Zheng %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-chan26a %I PMLR %P 981--1002 %U https://proceedings.mlr.press/v337/chan26a.html %V 337 %X We study the problem of allocating contiguous blocks of indivisible items positioned on a line to a set of agents where agents are partitioned into different groups. In the problem, agents must be located on a line, and items allocated to each agent must be contiguous and form a connected block. We study the settings, considered by Suksompong [2019] and Wang et al. [2021], without and with the requirement that items are assigned to their closest agents, respectively. For both settings, we focus on allocations that satisfy intra-group envy fairness (IEF) and inter-group fair share (GFS). In both settings, we show that determining the existence of IEF or GFS allocations is NP-complete. When the number of agents or items is constant, we provide polynomial algorithms to determine the existence of IEF or GFS allocations for both settings. For both settings, we provide upper and lower bounds on the existence of IEF or GFS allocations as well as allocations that satisfy both IEF and GFS simultaneously.
APA
Chan, H., Li, M., Zhao, Y. & Zheng, S.. (2026). Group-Fair Allocations of Contiguous Blocks of Indivisible Items. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:981-1002 Available from https://proceedings.mlr.press/v337/chan26a.html.

Related Material