TY - JOUR
AU - Caragiannis, Ioannis
AU - Micha, Evi
AU - Shah, Nisarg
PY - 2022/06/28
Y2 - 2023/04/01
TI - A Little Charity Guarantees Fair Connected Graph Partitioning
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 36
IS - 5
SE - AAAI Technical Track on Game Theory and Economic Paradigms
DO - 10.1609/aaai.v36i5.20420
UR - https://ojs.aaai.org/index.php/AAAI/article/view/20420
SP - 4908-4916
AB - Motivated by fair division applications, we study a fair connected graph partitioning problem, in which an undirected graph with m nodes must be divided between n agents such that each agent receives a connected subgraph and the partition is fair. We study approximate versions of two fairness criteria: \alpha-proportionality requires that each agent receive a subgraph with at least (1/\alpha)*m/n nodes, and \alpha-balancedness requires that the ratio between the sizes of the largest and smallest subgraphs be at most \alpha. Unfortunately, there exist simple examples in which no partition is reasonably proportional or balanced. To circumvent this, we introduce the idea of charity. We show that by "donating" just n-1 nodes, we can guarantee the existence of 2-proportional and almost 2-balanced partitions (and find them in polynomial time), and that this result is almost tight. More generally, we chart the tradeoff between the size of charity and the approximation of proportionality or balancedness we can guarantee.
ER -