New paper finds fairness in coalition games is NP-hard to maximize

Researchers Marta Pagano and Alexander Schlenga from an undisclosed institution have published a significant theoretical computer science paper on arXiv (2605.19030) that brings Nash welfare—a fairness metric combining efficiency with scale invariance—into the study of additively separable hedonic games (ASHGs). In ASHGs, agents each have a numeric valuation for every other agent, and coalitions form when agents want to group with those they value positively. Until now, social welfare research focused almost exclusively on utilitarian (sum-of-utilities) measures, ignoring Nash welfare's desirable property of balancing fairness across all agents. The authors show that partitions maximizing Nash welfare naturally guarantee contractual Nash stability in symmetric games, even for approximate solutions—a strong stability property that doesn't require explicit enforcement.

However, the computational picture is challenging. The team proves that maximizing Nash welfare is NP-hard even for the restricted subclass of Aversion-to-Enemies games (AEGs), where valuations are only negative or zero. For positive-only Appreciation-of-Friends games (AFGs), they develop packing-based approximation algorithms achieving ratios of 2n (where n is the number of agents) for AFGs and n-1 for AEGs, along with a strict inapproximability result showing no algorithm can guarantee a factor better than 1.0000759 for general ASHGs unless P=NP. They also map the boundary of tractability: limiting coalition size or number to 2 yields polynomial-time algorithms, but bounds of 3 or more lead to NP-hardness or unbounded inapproximability. This work has implications for automated team formation, social network clustering, and fair resource allocation where group preferences are based on pairwise compatibility.