Partitioning Friends Fairly


  • Lily Li University of Toronto
  • Evi Micha University of Toronto
  • Aleksandar Nikolov University of Toronto
  • Nisarg Shah University of Toronto



GTEP: Social Choice / Voting, GTEP: Cooperative Game Theory, GTEP: Fair Division


We consider the problem of partitioning n agents in an undirected social network into k almost equal in size (differing by at most one) groups, where the utility of an agent for a group is the number of her neighbors in the group. The core and envy-freeness are two compelling axiomatic fairness guarantees in such settings. The former demands that there be no coalition of agents such that each agent in the coalition has more utility for that coalition than for her own group, while the latter demands that no agent envy another agent for the group they are in. We provide (often tight) approximations to both fairness guarantees, and many of our positive results are obtained via efficient algorithms.




How to Cite

Li, L., Micha, E., Nikolov, A., & Shah, N. (2023). Partitioning Friends Fairly. Proceedings of the AAAI Conference on Artificial Intelligence, 37(5), 5747-5754.



AAAI Technical Track on Game Theory and Economic Paradigms