Abstract
This paper investigates the computational complexity of dividing a network of agents into equal-sized groups while satisfying various fairness criteria. By generalizing previous models to accommodate non-binary friendship strengths and non-additive utility functions, the authors provide a comprehensive taxonomy of fairness notions, including Envy-Freeness (EF), Proportionality (PROP), and Maximin Share (MMS). The research reveals a sharp complexity divide: while finding fair partitions is generally NP-hard even on simple structures like path graphs, specific relaxations on tree-like graphs admit efficient, linear-time algorithms. These findings provide a theoretical foundation for fair resource allocation and team formation in structured social environments.
Introduction
Imagine organizing a corporate banquet where employees must be assigned to tables of equal size. Naturally, individuals prefer to sit with their friends. The goal is to create a "fair" seating arrangement where no one feels they would be better off swapping places with someone at another table.
This scenario represents a classic partitioning problem with significant applications in clustering, team formation, and resource allocation. While earlier models formalized this as the "fair partitioning of friends" on a graph, they often relied on the simplifying assumption that all friendships are binary (0 or 1) and symmetric. In reality, relationships vary in intensity. This paper addresses this gap by exploring the existence and computational tractability of fair, balanced partitions when friendships have different weights and utilities are monotone.
Defining Fairness in Social Networks
The authors model the problem using an undirected friendship graph where vertices represent agents and edges represent the strength of their relationships. To evaluate the quality of a partition, they adapt several standard concepts from the fair division literature:
- Envy-Freeness (EF): No agent prefers the group of another agent over their own.
- EFX / EF1 (Envy-Free up to any/one friend): Relaxations where envy is tolerated unless it persists after removing the least (EFX) or most (EF1) valued friend from the envied group.
- Proportionality (PROP): Every agent receives at least their "fair share" (total utility divided by the number of groups).
- Maximin Share (MMS): Agents receive at least the value they could guarantee themselves if they were the last to choose a group in a "divide-and-choose" procedure.
The Complexity Landscape
A central contribution of this work is the mapping of the computational boundaries for these fairness notions. The authors demonstrate a strict hierarchy: while EF implies EFX and EF1, it does not necessarily imply PROP in a graph-based setting.
The Hardness of Strict Fairness
Finding strictly fair partitions (EF or PROP) is remarkably difficult. The authors prove that deciding if such a partition exists is NP-complete and W[1]-hard (parameterized by the number of groups $k$). Surprisingly, this hardness persists even on the simplest possible graph structures, such as path graphs or bipartite graphs with a vertex cover of only two, and even when friendship values are restricted to binary utilities.
The Tree Dichotomy
The research uncovers a significant algorithmic boundary regarding tree-like graphs. While strict notions like EF and PROP remain NP-hard on trees, the authors prove that relaxed notions—specifically MMS, EFX, and EF1—always exist on forests and trees. Furthermore, they provide a highly efficient $O(n)$ linear-time algorithm to compute these partitions when utilities are additive.
Structural Tractability and Generalizations
Beyond tree structures, the paper explores how specific graph parameters influence tractability. Using parameterized complexity analysis, the authors show:
- Vertex Cover ($vc$): If a graph has a small number of highly connected "hubs" (a small vertex cover), the problem becomes Fixed-Parameter Tractable (FPT) for binary utilities.
- Treewidth ($tw$): The problem is solvable in XP time when parameterized by treewidth and the number of groups.
These positive results are robust; the algorithms extend naturally to Additively Separable Hedonic Games with fixed-size coalitions (ASHG-FSC). This means the logic holds even if the target groups are not perfectly balanced but have pre-defined, varying sizes.
Conclusion and Future Directions
This paper provides a rigorous taxonomy of fairness in network partitioning, highlighting a stark contrast between strict fairness (which is largely intractable) and relaxed fairness (which is efficiently computable on tree-like structures).
However, limitations remain. The current FPT and XP algorithms rely on binary utilities. Future research is needed to determine if these problems remain tractable for arbitrary or unary valuations. Additionally, extending this framework to directed graphs (representing asymmetric friendships) or graphs with negative edges (representing "enemies") would bring the model closer to the complexities of real-world social networks.