Proceedings:
No. 5: AAAI-22 Technical Tracks 5
Volume
Issue:
Proceedings of the AAAI Conference on Artificial Intelligence, 36
Track:
AAAI Technical Track on Game Theory and Economic Paradigms
Downloads:
Abstract:
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.
DOI:
10.1609/aaai.v36i5.20420
AAAI
Proceedings of the AAAI Conference on Artificial Intelligence, 36