Additively separable hedonic games and fractional hedonic games have received consid-erable attention in the literature. They are coalition formation games among selfish agentsbased on their mutual preferences. Most of the work in the literature characterizes theexistence and structure of stable outcomes (i.e., partitions into coalitions) assuming thatpreferences are given. However, there is little discussion of this assumption. In fact, agentsreceive different utilities if they belong to different coalitions, and thus it is natural forthem to declare their preferences strategically in order to maximize their benefit. In thispaper we consider strategyproof mechanisms for additively separable hedonic games andfractional hedonic games, that is, partitioning methods without payments such that utilitymaximizing agents have no incentive to lie about their true preferences. We focus on so-cial welfare maximization and provide several lower and upper bounds on the performanceachievable by strategyproof mechanisms for general and specific additive functions. In mostof the cases we provide tight or asymptotically tight results. All our mechanisms are simpleand can be run in polynomial time. Moreover, all the lower bounds are unconditional, thatis, they do not rely on any computational complexity assumptions
Strategyproof Mechanisms for Additively Separable and Fractional Hedonic Games
Flammini, Michele
;Kodric, Bojana
;
2021-01-01
Abstract
Additively separable hedonic games and fractional hedonic games have received consid-erable attention in the literature. They are coalition formation games among selfish agentsbased on their mutual preferences. Most of the work in the literature characterizes theexistence and structure of stable outcomes (i.e., partitions into coalitions) assuming thatpreferences are given. However, there is little discussion of this assumption. In fact, agentsreceive different utilities if they belong to different coalitions, and thus it is natural forthem to declare their preferences strategically in order to maximize their benefit. In thispaper we consider strategyproof mechanisms for additively separable hedonic games andfractional hedonic games, that is, partitioning methods without payments such that utilitymaximizing agents have no incentive to lie about their true preferences. We focus on so-cial welfare maximization and provide several lower and upper bounds on the performanceachievable by strategyproof mechanisms for general and specific additive functions. In mostof the cases we provide tight or asymptotically tight results. All our mechanisms are simpleand can be run in polynomial time. Moreover, all the lower bounds are unconditional, thatis, they do not rely on any computational complexity assumptionsI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.