Hedonic Games with Fixed-Size Coalitions

5 juin 23

Speaker: Luca Moscardelli, University of Chieti-Pescara

Room: B310

Date: 05/06/2023 14:00


In hedonic games, a set of n agents, having preferences over all possible coalition structures, needs to agree on a stable outcome. We consider hedonic games with fixed-size coalitions, in which the set of possible coalition structures is restricted as follows: there are k coalitions, each coalition has a fixed size, and the sum of the sizes of all coalitions equals n.
We focus on the basic model of additively separable hedonic games with symmetric preferences, 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 such a setting, an outcome is stable if no pair of agents can exchange coalitions and improve their utilities.
Conditioned on the definition of improvement, three stability notions arise: swap stability under transferable utilities, which requires to improve the sum of the utilities of both agents, swap stability, which requires to improve the utility of one agent without decreasing the utility of the other one, and strict swap stability, requiring to improve the utilities of both agents simultaneously.
We analyse the fundamental questions of existence, complexity and efficiency of stable outcomes, and that of complexity of a social optimum.