Welfare Loss in Connected Resource Allocation

被引：0

作者：

Bei, Xiaohui ^{[1
]}

Lame, Alexander ^{[2
]}

Lu, Xinhang ^{[3
]}

Suksompong, Warut ^{[4
]}

机构：

[1] Nanyang Technol Univ, Singapore, Singapore

[2] City Univ Hong Kong, Hong Kong, Peoples R China

[3] UNSW Sydney, Sydney, NSW, Australia

[4] Natl Univ Singapore, Singapore, Singapore

来源：

PROCEEDINGS OF THE THIRTY-THIRD INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2024 | 2024年

关键词：

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We study the allocation of indivisible goods that form an undirected graph and investigate the worstcase welfare loss when requiring that each agent must receive a connected subgraph. Our focus is on both egalitarian and utilitarian welfare. Specifically, we introduce the concept of egalitarian (resp., utilitarian) price of connectivity, which captures the worst-case ratio between the optimal egalitarian (resp., utilitarian) welfare among all allocations and that among the connected allocations. We provide tight or asymptotically tight bounds on the price of connectivity for various large classes of graphs when there are two agents as well as for paths, stars and cycles in the general case. Many of our results are supplemented with algorithms which find connected allocations with a welfare guarantee corresponding to the price of connectivity.

引用

页码：2660 / 2668

页数：9