A Little Charity Guarantees Fair Connected Graph Partitioning


  • Ioannis Caragiannis Aarhus University
  • Evi Micha University of Toronto
  • Nisarg Shah University of Toronto




Game Theory And Economic Paradigms (GTEP)


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.




How to Cite

Caragiannis, I., Micha, E., & Shah, N. (2022). A Little Charity Guarantees Fair Connected Graph Partitioning. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4908-4916. https://doi.org/10.1609/aaai.v36i5.20420



AAAI Technical Track on Game Theory and Economic Paradigms