=Paper= {{Paper |id=Vol-3345/paper13_Spirit2 |storemode=property |title=None |pdfUrl=https://ceur-ws.org/Vol-3345/paper13_Spirit2.pdf |volume=Vol-3345 }} ==None== https://ceur-ws.org/Vol-3345/paper13_Spirit2.pdf 
Hedonic Games with Fixed-Size Coalitions
Vittorio BilΓ²1,*,† , Gianpiero Monaco2,† and Luca Moscardelli2,†
1
    University of Salento, Provinciale Lecce-Arnesano P.O. Box 193, 73100, Lecce, Italy
2
    University of Chieti-Pescara, Viale Pindaro 42, 65127, Pescara, Italy


                                         Abstract
                                         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.

                                         Keywords
                                         Coalition formation, Swap equilibria, Price of Anarchy and Stability




1. Introduction
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

Spirit’22: Workshop on Strategies, Prediction, Interaction, and Reasoning in Italy, November 29, 2022, Udine, Italy
*
  Corresponding author.
†
  These authors contributed equally.
$ vittorio.bilo@unisalento.it (V. BilΓ²); gianpiero.monaco@unich.it (G. Monaco); luca.moscardelli@unich.it
(L. Moscardelli)
                                       Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073
                                       CEUR Workshop Proceedings (CEUR-WS.org)
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
                                                     1
the analysis with a lower bound of 2π‘˜ βˆ’ 2 + π‘˜βˆ’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.
              (︁ coalitions have)︁ size at least 3, we design an algorithm whose approximation
However, if all
                      𝑠
guarantee is 1 + π‘ βˆ’1     (π‘˜ βˆ’ 1) , where 𝑠 is the size of the smallest coalition. In particular, as 𝑠
increases, the performance guarantee tends to π‘˜.
References
[1] A. Bogomolnaia, M. O. Jackson, The stability of hedonic coalition structures, Games and
    Economic Behavior 38 (2002) 201–230. doi:10.1006/game.2001.0877.
[2] S. Banerjee, H. Konishi, T. SΓΆnmez, Core in a simple coalition formation game, Social
    Choice and Welfare 18 (2001) 135–153. doi:10.1007/s003550000067.
[3] K. CechlΓ‘rovΓ‘, A. Romero-Medina, Stability in coalition formation games, Int. J. Game
    Theory 29 (2001) 487–494. doi:10.1007/s001820000053.
[4] J. H. Dreze, J. Greenberg, Hedonic coalitions: Optimality and stability, Econometrica 48
    (1980) 987–1003.
[5] A. Schaffer, M. Yannakakis, Simple local search problems that are hard to solve., SIAM J.
    Comput. 20 (1991) 56–87. doi:10.1137/0220004.
[6] Y. Asahiro, K. Iwama, H. Tamaki, T. Tokuyama, Greedily finding a dense subgraph, Journal
    of Algorithms 34 (2000) 203–221. doi:https://doi.org/10.1006/jagm.1999.1062.