In hedonic games, a set of π agents, having preferences over all possible coalition structures, needs to agree on a stable outcome. In this work, we initiate the study of hedonic games with fixed-size coalitions, where the set of possible coalition structures is restricted as follows: there are π coalitions, each coalition has a fixed size, and the sum of the sizes of all coalitions equals π. We focus on the basic model of additively separable hedonic games with symmetric valuations, where an agent's preference is captured by a utility function which sums up a contribution due to any other agent in the same coalition. In this setting, an outcome is stable if no pair of agents can exchange coalitions and improve their utilities. We analyse the fundamental questions of existence, complexity and efficiency of stable outcomes, and that of complexity of a social optimum.
We introduce the model of hedonic games with fixed-size coalitions, where π agents want to be assigned to coalitions in order to maximize their utilities. Differently from classical models of hedonic games [1,2,3,4], both the number and sizes of coalitions are fixed: there are π coalitions, whose sizes sum up to π. The utility that agent π receives when being in the same coalition of agent π is given by a non-negative value π£ ππ . We assume that valuations are symmetric, i.e., π£ ππ = π£ ππ for every distinct agents π and π. Valuations are dichotomous when they belong to {0, 1}.
We are interested in the existence and efficiency of outcomes which may be resistant to agents swaps. In particular, we distinguish among three different types of swap stability, depending on how we define the happiness of a pair of swapping agents. We say that an outcome is swap stable under transferable utilities (SSTU), if no pair of swapping agents can improve the sum of their utilities; it is strictly swap stable (SSS), if no swap can improve the utility of one agent without decreasing the utility of the other one; it is swap stable (SS), if no pair of swapping agents can improve both of their utilities simultaneously. It is immediate to see that, by definition, any outcome which is SSTU is also SSS and that any SSS outcome is also SS. So, positive results holding for SSTU outcomes (such as existence and efficient computation) extend to both SSS and SS ones, while negative results for SS outcomes (such as hardness of computation) apply to SSS and SSTU outcomes as well.
We prove that the utilitarian social welfare (USW), defined as the sum of the utilities of all agents, is a potential function which shows that, starting from any outcome, every sequence of swaps in which the sum of the utilities of the swapping agents increases converges to a SSTU outcome after a finite number of swaps. For dichotomous valuations, this number is at most π(π β 1)/2, which yields a polynomial time algorithm for computing a SSTU outcome. For general valuations, however, we prove that computing a SS outcome is PLS-complete by reworking a reduction from the Max Cut problem originally designed in [5].
To measure the efficiency of stable outcomes, we resort to two state-of-the-art metrics: the price of anarchy (PoA) and the price of stability (PoS). They compare the USW of a socially optimal outcome against the USW of, respectively, the worst and the best possible stable outcome. As a corollary of the fact that the USW is a potential function, the PoS of all three stability notions is equal to 1. The characterization of the PoA, instead, is much more challenging and constitutes one of the main results of our work. We first show that the PoA of SS outcomes can be unbounded even for games with dichotomous valuations. A similar negative result is also obtained for SSTU outcomes (and so also for SSS ones) for games with generic valuations and even for games with dichotomous valuations, as long as there exist agents who dislike all the other ones (i.e., misanthropes). In light of these negative results, our investigation will be limited to the characterization of the PoA of both SSS and SSTU outcomes in games with dichotomous valuations and no misanthropes. For SSS outcomes, we show that the PoA is exactly 2π β 1. To obtain the upper bound, we first derive a couple of technical lemmas. The first lemma lower bounds the USW of a SSS outcome as a function of the size of the largest coalition. The second one, instead, upper bounds the sum of the utilities of the agents belonging to any two coalitions π and π β² in a SSS outcome which half of the total utility that the agents would get if they were all together in a coalition. By summing over all possible pairs of coalitions, the desired bound can be obtained. However, the technical lemma does not hold when both π and π β² are singleton sets. Thus, one needs to deal with the presence of singletons in the coalition structure. We resolve this issue by means of an ingenious inductive argument on the number of singleton coalitions. For SSTU outcomes, for which the 2π β 1 upper bound carries over, we complement the analysis with a lower bound of 2π β 2 + 1 πβ1 . This lower bound is tight for π = 2 and almost tight up to an additive factor of 1 for any other value of π.
We also investigate the problem of computing a social optimum (SO). On the negative side, we show that a SO cannot be approximated within π π (1) , even for games with dichotomous valuations. Even for constant π, computing a SO remains NP-hard. On the positive side, by leveraging known approximability results for the Densest π‘-Subgraph [6], we obtain an π(π 2 )approximation algorithm. For dichotomous valuations, we know that a SSTU outcome can be computed in polynomial time and that this outcomes is a (2π β 1)-approximation of the SO. However, if all coalitions have size at least 3, we design an algorithm whose approximation guarantee is
)οΈ , where π is the size of the smallest coalition. In particular, as π increases, the performance guarantee tends to π.