# hedonic_games_with_fixedsize_coalitions__367de719.pdf

Hedonic Games with Fixed-Size Coalitions

Vittorio Bil o,1 Gianpiero Monaco,2 Luca Moscardelli3

1 Univ. of Salento, Italy 2 Univ. of L Aquila, Italy 3 Univ. of Chieti-Pescara, Italy vittorio.bilo@unisalento.it, gianpiero.monaco@univaq.it, luca.moscardelli@unich.it

In hedonic games, a set of n 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 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 this 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.

1 Introduction It is social dinner time at your preferred conference. The organizers reserved the best restaurant of the city. When you arrive at the place, you see that k tables, of various capacities, have been set to accommodate the n participants. As you are a bit late, some seats are already taken. You would like to share your table with some friends you have not seen for a long time, as well as with some colleagues working on common research topics. At the same time, you would gladly avoid a couple of annoying persons you do not like that much. Where are you going to sit? Indeed, this example can be recast in several other (perhaps more concrete) settings, such as assigning desks to faculty members in a department with multi-person offices, dividing a set of employees into project teams, assigning students to classrooms, and so on. All the above situations fall within the well-established framework of hedonic games (Dreze and Greenberg 1980), where a set of agents, having preferences over all possible

Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

coalition structures (i.e., partitions of agents into groups), needs to agree on (or be assigned to) a stable outcome. Stability is interpreted as a situation that is acceptable by everyone, either because they are all happy or because any subset of unhappy agents cannot give life to a better outcome. There are several notions of stability that may be defined in this setting (e.g., individual stability (Bogomolnaia and Jackson 2002), Nash stability (Nash 1950), core stability (Banerjee, Konishi, and S onmez 2001), etc.), by discriminating on what an agent or a group of agents is allowed to do when deviating from a given outcome. All of them usually pose no restrictions on the number of agents that can belong to a coalition. This freedom is not guaranteed in our social dinner example, where the set of allowed coalition structures is restricted to obey stringent constraints: there are k coalitions (the tables), each coalition has a fixed size (the table capacity), and the sum of the sizes of all coalitions equals n (exactly one seat has been reserved for each participant). Under these premises, classical stability notions become infeasible. Nash stability, for instance, which allows an unhappy agent to join a more preferred coalition, cannot be applied, as the capacity of a table is fixed and cannot be increased. Also core stability, which allows a group of unhappy agents to create a new coalition, cannot be realized, as new tables (of at least a certain capacity) cannot be added to the current arrangement. Indeed, a given outcome can be modified only if both the number of tables and their capacities stay the same, i.e., only if a group of agents agrees on permuting their seats. The simplest permutation, which involves two agents only, is called a swap. Swap stability has been considered in a variety of problems with superimposed structures, such as matching markets (Alcalde 1995; Aziz and Goldwaser 2017; Damamme et al. 2015; Gourv es, Lesca, and Wilczynski 2017; Massand and Simon 2019) and Schelling games (Agarwal et al. 2020; Bil o et al. 2020; Gross-Humbert et al. 2021). However, to the best of our knowledge, it has not been imported yet in the general setting of hedonic games. In this work, we introduce and formalize the model of hedonic games with fixed-size coalitions and embark in the study of swap stability in additively separable games, 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. We distinguish among three different types of

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

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, if no pair of swapping agents can improve the sum of their utilities; it is swap stable, if no pair of swapping agents can improve the utility of one agent without decreasing the utility of the other one; it is strictly swap stable, if no pair of swapping agents can improve both of their utilities simultaneously.

Our Contribution

We investigate, in additively separable hedonic games with symmetric preferences, the fundamental questions of existence, complexity and efficiency of the three types of swap stability defined above, and that of complexity of a social optimum. Specifically, in Section 3, we show the following results that hold for any of the three stability notions we are considering. First, we prove that, given any initial starting configuration, a swap stable assignment is always reached after a finite number of improving swaps. This clearly implies that a swap stable assignment is always guaranteed to exist. As a further consequence, we also obtain that there always exists a socially optimal stable assignment, i.e., the price of stability is 1. From an algorithmic point of view, we show that computing a swap stable assignment is PLScomplete, while it becomes polynomially solvable in the specific case of simple games, where agents preferences can get values 0 and 1. In Section 4, we analyse the price of anarchy and provide tight or asymptotically tight bounds for all of the three stability notions. It turns out that the price of anarchy is unbounded for general games, independently of the considered stability notion, and so is also for the case of simple games when considering strictly swap stability. For the remaining two notions, better and more interesting results are possible in simple games. Our main technical results, indeed, are a tight bound of 2k 1 for the price of anarchy of swap stable assignments and a tight bound up to an additive factor of at most 1 for the price of anarchy of swap stable assignments with transferable utilities (the upper bound is 2k 1, while the lower bound equals 2k 2 + 1 k 1). Finally, in Section 5, we investigate the problem of finding an assignment maximizing the utilitarian social welfare (which is defined as the sum of the agents utilities) and provide hardness results as well as polynomial time approximation algorithms.

Related Work

Hedonic games have been introduced in (Dreze and Greenberg 1980) and then further developed in (Banerjee, Konishi, and S onmez 2001; Bogomolnaia and Jackson 2002; Cechl arov a and Romero-Medina 2001). See also (Aziz and Savani 2016) for a nice survey on the topic. Additively separable hedonic games (ASHGs) constitute a natural and succinctly representable class of hedonic games. In these games, each agent has a value for every other agent, and the utility she ascribes to a given coalition is simply the sum of the values she assigns to its members. ASHGs satisfy a number of desirable properties (Aziz, Brandt, and

Seedig 2013) and are equivalent to the non-transferable utility generalization of graph games studied in (Deng and Papadimitriou 1994). ASHGs have been first considered in (Bogomolnaia and Jackson 2002), where the authors pose no restrictions on the number of agents that can belong to a coalition and on the number of coalitions that can be created (i.e., any partition of the agents is a feasible outcome). They show that Nash stable outcomes may not exist in games with asymmetric valuations. However, for symmetric valuations, the existence of a Nash stable outcome is guaranteed by a potential function argument. In (Ballester 2004) and (Sung and Dimitrov 2010), the authors show that the problem of checking whether an instance admits a Nash stable outcome is NP-complete and NP-complete in the strong sense, respectively. (Olsen 2009) proves that the problem of deciding whether a non-trivial Nash stable outcome exists in additively separable hedonic games with non-negative and symmetric preferences is NP-complete. (Aziz, Brandt, and Seedig 2013) show that checking the existence of a core stable outcome is NP-hard even for symmetric valuations. Concerning the performance of Nash stable outcomes in ASHGs with symmetric valuations, it is easy to check that the price of anarchy is unbounded (Bil o et al. 2019) and that the price of stability is 1 since an optimal outcome is always Nash stable (it can be easily proved by using the potential function). (Flammini et al. 2021b) address the problem of maximizing the social welfare in ASHGs in the online setting. (Elkind, Fanelli, and Flammini 2020) study Pareto optimality in ASHGs. Finally, (Flammini et al. 2021a) propose strategyproof mechanisms for ASHGs. Hedonic games with coalition-size constraints have also been addressed in the literature. (Wright and Vorobeychik 2015) investigate strategyproof mechanisms for ASHGs with positive values. If there is no constraint on the coalition size, a trivial optimal strategyproof mechanism simply puts all agents in the grand coalition. Therefore, they assume coalition-size constraints and (approximate) envy-freeness. Their main contribution is a mechanism that achieves a good experimental performance. (Peters 2016) studies the computational complexity of questions related to finding optimal and several stable partitions (swap stability is not considered) for the roommate problem with dichotomous preferences. Finally, (Cseh, Fleiner, and Harj an 2019) consider the problem of partitioning agents into groups of fixed size and study the complexity of deciding the existence of, and then finding, a Pareto optimal assignment, and the complexity of verifying Pareto optimality for a given assignment. Swap stability has been considered in matching markets, where agents have ordinal preferences over other agents with whom they want to be matched with, and the goal is to find a matching, i.e., a subset of disjoint pairs of agents, which is swap stable. (Alcalde 1995) introduces (coalitional) exchange stability in matching market, where there is no subset of agents {u0, . . . , ur 1} of size r 2 such that each agent ui prefers the partner of her successor ui+1 (index i + 1 taken modulo r) and discusses restricted preference domains, where exchange stability is guaranteed to exist. Further results about the existence of exchange stable matchings for specific domains are shown in (Abizada

2019). (Cechl arov a and Manlove 2005) show that deciding whether an exchange stable matching exists is NP-complete even for the marriage case with complete preferences without ties. (Aziz and Goldwaser 2017) propose several relaxed notions of (coalitional) exchange-stability and discuss their relations. Very recently, (Chen et al. 2021) investigate the computational and parametrized complexity of the coalitional exchange stable marriage (resp. coalitional exchange roommates) problem, which asks to decide whether a Stable Marriage (resp. Stable Roommates) instance admits a coalitional exchange-stable matching. Swap stability has been also considered in (variants of) Schelling games (Agarwal et al. 2020; Bil o et al. 2020; Gross-Humbert et al. 2021), which can essentially be viewed as hedonic games with fixed-size, but overlapping, coalitions.

2 Definitions

Given any integer k, we denote by [k] the set {1, 2, . . . , k}.

Graph Theory Notation. Fix an edge weighted undirected graph G = (V, E, w), with w : E 7 R+. We assume n = |V | and m = |E|. Given an edge {u, v} E, we write wuv as a shorthand for w({u, v}); moreover, for a node u V , denote by Wu(G) = P {u,v} E wuv the sum of the weights of all edges incident to u in G (we drop G from the notation when it is clear from the context). For any u, v V , we use Iu,v to denote the indicator function which equals 1 if and only if {u, v} E. If wuv = 1 for any {u, v} E, we say that G is unweighted.

Additively Separable Hedonic Games with Fixed Size Coalitions (AS-HGFSCs). An AS-HGFSC G = (G, k, (ni)i [k]) is defined by an edge weighted undirected graph G = (V, E, w) and a tuple of k positive integers n1, . . . , nk such that n1 n2 nk and P i [k] ni = n. Each node in the graph corresponds to an agent involved in the game, so that V is the set of agents of cardinality |V | = n = Pk i=1 ni and, for any i [k], ni is the size of the i-th coalition. Each agent must be assigned to one of the k coalitions. Thus, an assignment is a vector z = (z1, z2, . . . , zn) such that, for any u V , zu [k] denotes the index of the coalition agent u is assigned to, and, denoted by Ci(z) = {zu|zu = i} the set of agents assigned by z to the i-th coalition, |Ci(z)| = ni for any i [k]. For an assignment z and an agent u V , denote by Uu(z) = P v V :zv=zu wuv the utility of agent u in assignment z. We say that G is simple if the underlying graph G = (V, E) is unweighted. In this case, given an assignment z and two indices i, j [k], we denote by Tij(z) = |{{u, v} E : u Ci(z), v Cj(z)}| the cardinality of the cut between Ci(z) and Cj(z); moreover, for an agent u Ci(z), we denote by Tij(z, u) = |{{u, v} E : v Cj(z)}| the restriction of Tij(z) to all edges incident to u.

Stable Assignments. Given an assignment z and two agents u and v, let zu v be the assignment obtained from z by letting u and v swap their coalitions.

Definition 1. An assignment z is strictly swap stable, if there is no pair of agents u, v such that Uu(zu v) > Uu(z) and Uv(zu v) > Uv(z). We denote by SSS(G) the set of strictly swap stable assignments of G. An assignment z is swap stable, if there is no pair of agents u, v such that Uu(zu v) > Uu(z) and Uv(zu v) Uv(z). We denote by SS(G) the set of swap stable assignments of G. An assignment z is swap stable under transferable utilities, if there is no pair of agents u, v such that Uu(zu v) + Uv(zu v) > Uu(z) + Uv(z). We denote by SSTU(G) the set of stable assignments under transferable utilities of G. Notice that, for any game G, it holds that

SSTU(G) SS(G) SSS(G). (1)

We observe that, no matter which of the three above stability notions we are considering, if z is not stable, then there exist two agents u and v such that Uu(zu v)+Uv(zu v) > Uu(z) + Uv(z). In this case, we say that u and v possess an improving swap.

Social Optimum, Price of Anarchy and Price of Stability. Let SW be the function SW(z) = P u V Uu(z) associating to each assignment z its utilitarian social welfare, that is, the sum of all agents utilities realized in z. For convenience, we define, for any i [k], SW(Ci(z)) = P u Ci(z) Uu(z) as the amount of social welfare contributed by coalition i, so that SW(z) = P i [k] SW(Ci(z)). A social optimum z for G is an assignment maximizing SW. Given a game G, we denote by

Po A-SSS(G) = max z SSS(G) SW(z )

SW(z) and by

Po S-SSS(G) = min z SSS(G) SW(z )

the price of anarchy and the price of stability of strictly swap stable assignments of G, respectively. Whenever the denominator equals zero in any of the two above fractions, the ratio is assumed to be equal to infinity. The price of anarchy is the worst-case ratio between the social welfare of a social optimum and that of a strictly swap stable assignment, while the price of stability considers the best-case ratio. These two definitions naturally extend to the other two considered notions of stability, i.e., swap stability and swap stability under transferable utilities, yielding Po A-SS(G), Po S-SS(G), Po A-SSTU(G) and Po S-SSTU(G). Being the price of anarchy a worst-case measure and the price of stability a best-case one, for any game G, by relation (1) it holds that

Po A-SSTU(G) Po A-SS(G) Po A-SSS(G) (2)

Po S-SSS(G) Po S-SS(G) Po S-SSTU(G). (3)

Computational Problems. Given a game G, we consider the following computational problems:1

1For the sake of brevity, from now on we shall implicitly assume that every game G under consideration is an AS-HGFSC.

1. SOCIAL OPTIMUM: compute a social optimum for G; 2. STABLE: Given a notion of stability X {SSS, SS, SSTU}, compute a stable assignment belonging to X(G)2.

3 Preliminary Results In this subsection, we warm-up with some preliminary results. We start by showing, via a potential function argument, that for any game G and stability notion in {SSS, SS, SSTU}, a stable assignment is always guaranteed to exist. This is achieved by proving that, once fixed a particular stability notion and an initial starting assignment, a stable outcome is always reached after a finite number of improving swaps.

Lemma 1. Fix a game G, an assignment z and two agents u, v V . It holds that 1 2SW(zu v) 1 2SW(z) = Uu(zu v) + Uv(zu v) Uu(z) Uv(z).

Proof. Assume, without loss of generality, that zu = i and zv = j. We have that:

1 2SW(zu v) 1

= 1 2SW(Ci(zu v)) + 1

2SW(Cj(zu v)) (4)

2SW(Ci(z)) 1

v Ci(zu v) wvv + 2 X

v Cj(zu v) wuv (5)

v Ci(z) wuv 2 X

v Cj(z) wvv

= Uu(zu v) + Uv(zu v) Uu(z) Uv(z),

where equality (4) holds because coalitions i = zu and j = zv are the only ones that change after the swap, and equality (5) holds because the difference in the social welfare is given by twice the overall weight of all edges incident to u and v before and after the swap.

Theorem 1. Fix a game G, an assignment z and a stability notion in {SSS, SS, SSTU}. A stable assignment is always reached after a finite number of improving swaps starting from z. If G is simple, the number of swaps is at most n(n 1)

Proof. Fix a game G and an assignment z. By Lemma 1, any improving swap increases the value of function 1

2SW(z). Since SW(z) is upper bounded by P u V Wu and there is a finite number of possible assignments, it follows that, after a finite number of improving swaps, a stable assignment must be reached. To prove the second part of the claim, observe that, if G is simple, Wu n 1 for each u V and each improving

2This problem is well posed, as we prove in Theorem 1 that stable assignments always exist for any X {SSS, SS, SSTU}.

swap increases the value of function 1

2SW(z) by at least one.

Once established the existence of stable assignments, we provide a first characterization of the complexity of STABLE which can be derived by reinterpreting a reduction from the local search problem MAX CUT designed in (Schaffer and Yannakakis 1991).

Theorem 2. STABLE is PLS-complete for any stability notion in {SSS, SS, SSTU}.

Another direct consequence of Lemma 1 is that, with respect to the price of stability, all stability notions share the same best-possible performance. Indeed, the fact that 1 2SW(z) is a potential function implies that the social optimum is a stable assignment under all stability notions. Hence, the following theorem holds.

Theorem 3. For any game G, Po S-SSTU(G) = Po S-SS(G) = Po S-SSS(G) = 1.

We end this section by discussing the meaningfulness of AS-HGFSCs defined on directed graphs (i.e., asymmetric games) and the relations occurring between these games and the symmetric version we consider in this paper. First, it is not difficult to define an asymmetric AS-HGFSC admitting no strictly swap stable assignments by adapting a construction given in (Gale and Shapley 1962) for the roommate problem. For completeness, we illustrate it in the following. There are 4 agents and two coalitions of size 2. The edge weights are: w12 = 2, w13 = 3, w14 = 1, w21 = 3, w23 = 1, w24 = 2, w31 = 2, w32 = 1, w34 = 3, w41 = 1, w42 = 3, w43 = 2. In assignment {{1, 2}, {3, 4}}, agents 1 and 4 both have utility 2 and can get utility 3 by swapping. In assignment {{1, 3}, {2, 4}}, agents 2 and 3 both have utility 2 and can get utility 3 by swapping. In assignment {{1, 4}, {2, 3}}, all agents get the minimum possible utility of 1 and so any two unmatched agents improve by swapping. As no other assignments are possible, it follows that no strictly swap stable assignments exist. Secondly, we can show that SOCIAL OPTIMUM in asymmetric games is computationally equivalent to its version on symmetric games. In fact, given an asymmetric game G = (G, k, (ni)i [k]) defined over a weighted directed graph G, consider the undirected weighted graph G with the same set of nodes of G and whose edges are defined as follows: for every pair of nodes u, v, create an undirected edge {u, v} whose weight is equal to w((u,v))+w((v,u))

2 , where w((u, v)) (resp. w((v, u))) is the weight of the directed arc (u, v) (resp. (v, u)) in G (we assume that an arc has weight equal to 0 if it does not exist). It can be easily checked that any assignment realizes the same social welfare in both G and G = (G , k, (ni)i [k]). Therefore, any approximation result provided for the symmetric weighted case (as our O(k2)- approximation algorithm of Theorem 13) directly extends to the asymmetric one.

4 The Price of Anarchy In this section, we complete the study of the efficiency of stable assignments by giving tight or almost tight bounds

Figure 1: The game considered in the proof of Theorem 4. (a) The strictly swap stable assignment z. (b) Assignment z .

on the price of anarchy of the three stability notions in {SSS, SS, SSTU}. We start by showing that the performance of strictly swap stable assignments is the worst-possible one, even in simple games played on basic topologies, such as trees.

Theorem 4. There exists a simple game G defined by an unweighted tree such that Po A-SSS(G) is unbounded.

Proof. Consider a simple game G defined as follows: G is an unweighted 3-node tree with two leaf nodes, and there are k = 2 coalitions, with n1 = 2 and n2 = 1. Since no agent swapping with the one in the singleton coalition C2 can increase her utility, assignment z in which both leaves belong to the first coalition is strictly swap stable and has SW(z) = 0 (see Figure 1.a). As assignment z in which the root belongs to the first coalition yields SW(z ) = 2 (see Figure 1.b), we obtain the claim.

A similar negative result also holds for swap stability under transferable utilities (and thus, by relation (2), for swap stability too) in games played on weighted graphs and in simple games played on (unweighted) graphs with isolated vertices.

Theorem 5. There exists a game G such that both Po A-SSTU(G) and Po A-SS(G) are unbounded. Also, there exists a simple game G, whose underlying graph has isolated vertices, such that both Po A-SSTU(G) and Po A-SS(G) are unbounded.

The previous theorem does not rule out the possibility of having better performance, for assignments being swap stable or swap stable under transferable utilities, in simple games whose underlying graph does not contain isolated vertices. This is indeed the case, as shown by the following theorem that provides an upper bound on the price of anarchy of swap stable assignments as a function of the number of coalitions.

Theorem 6. For any simple game G whose underlying graph has no isolated vertex, Po A-SS(G) 2k 1.

To show Theorem 6, we need a couple of technical lemmas. The first lemma lower bounds the social welfare of a swap stable assignment as a function of the cardinality of the largest coalition.

Lemma 2. Let z be a swap stable assignment for a simple game whose underlying graph has no isolated vertex. It holds that SW(z) n1 1. The second lemma upper bounds the size of the cut between two coalitions as a function of their contributed social welfare. Lemma 3. Let z be a swap stable assignment for a simple game whose underlying graph has no isolated vertex. For any pair of indices i, j [k] such that ni 2 and nj 1, it holds that Tij(z) SW(Ci(z)) + SW(Cj(z)).

Proof of Theorem 6. Fix a worst-case swap stable assignment z and a social optimum z for G. Assume, for the moment, that nk 2. We have

2|E| P i [k] SW(Ci(z))

P i [k] SW(Ci(z)) + 2 P i,j [k] Tij(z) P i [k] SW(Ci(z))

1 + 2 P i,j [k](SW(Ci(z)) + SW(Cj(z)))

P i [k] SW(Ci(z))

= 1 + 2(k 1) P i [k] SW(Ci(z)) P i [k] SW(Ci(z))

where the first inequality holds as, in any assignment, an edge of G can contribute to the utility of its incident agents only; the second equality holds as any edge of G can exclusively connect either two agents in a same coalition in z or two agents belonging to different coalitions in z and, moreover, twice the number of edges connecting agents in a same coalition Ci(z) equals the contribution SW(Ci(z)) of Ci(z) to the social welfare SW(z) of z; the last inequality comes from Lemma 3 as, by hypothesis, there is no pair of singleton coalitions. To show the claim also in presence of singleton coalitions, i.e., for nk = 1, we use an inductive approach based on the number s of singleton coalitions in G. We have just proved that the claim holds for the base case of s = 0. Consider a game G with s 1 singleton coalitions and fix a swap stable assignment z for G. Let u be the agent such that zu = k and let G be the game defined by graph G \ {u} and in which there are k 1 coalitions mirroring the first k 1 coalitions of G. By construction, G has s 1 singleton coalitions and thus, for any swap stable assignment z for G, by the inductive hypothesis, we have SW(z )

SW(z) 2(k 1) 1 = 2k 3,

where z denotes the social optimum for G. Now, we make two simple observations. The first is that assignment z, obtained from z by removing the last coalition, is a swap stable assignment for G, and this implies that

SW(z) = SW(z )

SW(z) 2k 3. (6)

The second is that, by adding a singleton coalition (and so also a new vertex to the underlying graph) to a given game, the social optimum can increase of at most 2(n1 1), that is, SW(z ) SW(z ) + 2(n1 1). (7)

To show why (7) holds, assume, by way of contradiction, that SW(z ) > SW(z ) + 2(n1 1). Let z the assignment obtained from z by removing vertex u from G: at most n1 1 edges contributing to SW(z ) can be removed from z , thus implying that SW(z ) SW(z ) 2(n1 1) > SW(z ): a contradiction to the fact that z is the social optimum for G. Putting everything together, we conclude that

SW(z) SW(z ) + 2(n1 1)

SW(z) 2k 3 + 2 = 2k 1,

where the first inequality comes from (7) and the second inequality comes from (6) and Lemma 2.

By showing that the upper bound provided by Theorem 6 is tight, we obtain an exact characterization of the price of anarchy of swap stable assignments for simple games.

Theorem 7. There exists a simple game G whose underlying graph has no isolated vertex and such that Po A-SS(G) = 2k 1.

Proof. For any fixed k, let n be such that n k + 1 > k 1 and n k+1 is even. Define r := (n k+1)/2. Consider a graph G defined as follows. The set of nodes V is such that V = U U b U, with U = {u1, . . . , ur}, U = {u1, . . . , ur} and |b U| = k 1. The set of edges E is the minimal one such that there exists an edge between ui and ui for each i [r] and every node in b U is adjacent to any other node in V . We shall say that nodes ui and ui are twins. Finally, define n1 = 2r = n k + 1 and n2 = . . . = nk = 1. First, let us observe that assignment z in which all nodes in U U belong to the first coalition is swap stable. In fact, each node in this coalition is getting utility 1 (being adjacent to its twin node only) and, by deviating to a singleton coalition, gets zero utility. Thus, SW(z) = n k + 1. Now, let z be an assignment constructed as follows: node u1 is assigned to the second coalition, node u1 is assigned to the third coalition, node u2 is assigned to the fourth coalition and so on until all singleton coalitions are occupied. All the remaining nodes are then assigned to the first coalition. Observe that, by so doing, the first coalition will contain all nodes in b U, as n k + 1 > k 1. To bound SW(z ), observe that, within the first coalition, any node in b U is adjacent to n k nodes, while any other node, except for at most one, is adjacent to at least k nodes (the k 1 ones belonging to b U and its twin node). Thus, we get SW(z ) (k 1)(n k) + (n 2k + 2)k 1. By letting n going to infinity, we get Po A-SS(G) 2nk n

By Theorem 6 and relation (2), we have that Po A-SSTU(G) 2k 1 for each simple game G. In the following, we show a nearly matching lower bound that is tight for the basic case of k = 2.

Theorem 8. For every ε > 0, there exists a simple game G whose underlying graph has no isolated vertex and such that Po A-SSTU(G) 2(k 1) + 1 k 1 ε.

Our bounds on the price of anarchy are given in terms of the number of coalitions k. If we are interested in bounds depending on the number of agents, we can prove the following asymptotically tight results.

Theorem 9. For any simple game G whose underlying graph has no isolated vertex, Po A-SS(G) n.

Theorem 10. There exist a simple game G and a simple game G (whose underlying graphs have no isolated vertex) such that Po A-SS(G) (4 2

3)n > 0.53589n and Po A-SSTU(G ) n/2.

5 Problem SOCIAL OPTIMUM: Complexity and Approximation In this section, we investigate the problem of finding an assignment that maximizes social welfare. In order to provide hardness results, we exploit reductions from some well-known optimization problems (i.e., DENSEST t SUBGRAPH and BISECTION). We emphasize that the following hardness results hold even for unweighted graphs. We first show a hardness result for the case of k being not constant.

Theorem 11. When k is not constant, SOCIAL OPTIMUM is not approximable within n1/(log log n)c, where c > 0 is a universal constant independent of n, assuming the exponential time hypothesis (ETH). Moreover, by assuming that there is some constant ε > 0 such that no subexponential-time algorithm can distinguish between a satisfiable 3SAT formula and one which is only (1 ε)-satisfiable (also known as Gap ETH), SOCIAL OPTIMUM is not approximable within nf(n) for any function f whose limit is zero as n goes to infinity (i.e. f o(1)). Both results hold even for simple games.

We are also able to provide a weaker hardness result for the special case of simple games with two coalitions only.

Theorem 12. SOCIAL OPTIMUM is NP-hard even for simple games with k = 2.

On the positive side, by exploiting known results for the DENSEST t-SUBGRAPH problem, it is possible to prove the following theorem.

Theorem 13. For any game G, there exists an O(k2)- approximation algorithm for SOCIAL OPTIMUM.

Proof. DENSEST t-SUBGRAPH is defined as follows: Given an undirected graph G = (V, E, w) on n vertices and a positive integer t < n, the goal is to find a subset S V of t vertices of G such that the sum of the weights of the edges contained in the subgraph induced by S is maximum. When defined on graphs with non-negative edge weights, it admits a polynomial time approximation algorithm A with

approximation ratio O(n/t) (Asahiro et al. 2000) (the exact approximation ratio R is 1

2t 2 + O (1/n) for t in the range n/3 t n and 2 n

t2 for t < n

3 ). We can get an O(k2)-approximation algorithm for SOCIAL OPTIMUM as follows. Given a game G = (G, k, (ni)i [k]), consider the n n1 -approximated outcome S obtained by applying algorithm A to the instance of DENSEST n1-SUBGRAPH defined on the same graph G. Let S be an optimal solution to the instance of DENSEST n1SUBGRAPH. Since n1 ni, for any i = 2, . . . , k, we get that SW(z ) k SW(S ). Consider the assignment z that assigns all the agents belonging to S to coalition 1, i.e., zu = 1 for any u S, and assigns the other agents to the remaining coalitions 2, . . . , n, in any feasible way (i.e. by respecting their sizes). Notice that n n1 k since

otherwise Pk i=1 ni < n. We have that SW(C1(z)) is an n n1 -approximation on the maximum social welfare that we can get from coalition 1. We conclude that assignment z is O(k2) approximating.

If we focus on simple games, better approximation ratios can be guaranteed. In fact, Theorem 6 combined with Theorem 1 implies that any sequence of improving swaps starting from an arbitrary assignment leads, in polynomial time, to a 2k 1 approximation of the social optimum. If nk > 2, i.e., the size of the smallest coalition is sufficiently big, the following theorem provides a better approximation for SOCIAL OPTIMUM.

Theorem 14. Given a simple game G such that nk 2, there exists an 1 + nk nk 1(k 1) -approximation algorithm for SOCIAL OPTIMUM.

Proof. Consider the local search algorithm in which, for any assignment z, the neighbourhood of z is N(z) = {zu v|u, v V, u = v} and the algorithm aims at maximizing function Ψ(z) = Pk i=1 ni SW(Ci(z)). First of all, since G is simple, the maximum value that Ψ can assume is polynomially bounded in the size of G. Given that, at each move of the local search algorithm, it increases by at least 1, it follows that the algorithm is polynomial-time. It remains to show that the social welfare of any local optimum approximates the social welfare of the social optimum by a factor 1 + nk nk 1(k 1) . Given a local optimum z, consider a couple of vertices u Ci(z) and v Cj(z) with i = j. Since Ψ(zu v) Ψ(z), it holds that

ni Uu(z) + nj Uv(z) nj(Tij(z, u) Iu,v) + ni(Tij(z, v) Iu,v). (8)

In fact, if agents u and v swap their coalitions, Ψ(zu v) = Ψ(z) 2(ni Uu(z) + nj Uv(z)) + 2(nj(Tij(z, u) Iu,v) + ni(Tij(z, v) Iu,v)). Given any i, j [k] with i = j, by summing inequality (8) over all couples of agents u Ci(z) and v Cj(z), we obtain ninj SW(Ci(z)) +

njni SW(Cj(z)) n2 j Tij(z) + n2 i Tij(z) (ni + nj)Tij(z) that is equivalent to

Tij(z) ninj(SW(Ci(z)) + SW(Cj(z)))

n2 i + n2 j ni nj . (9)

Assume without loss of generality that i j. Since ni nj nk 2, by simple algebra, it is possible to verify that

ninj n2 i + n2 j ni nj ni 2(ni 1) nk 2(nk 1)

and it follows that inequality (9) implies

Tij(z) nk 2(nk 1)(SW(Ci(z)) + SW(Cj(z))). (10)

An easy upper bound to the optimal solution is given by each agent having utility equal to her degree in G, i.e. all edges of G contribute to the social welfare of the optimal solution. It follows that

SW(z) + 2 X

i,j [k],i =j Tij(z)

SW(z) + (11)

i,j [k],i =j

nk 2(nk 1)(SW(Ci(z)) + SW(Cj(z)))

SW(z) + (k 1) nk (nk 1)SW(z), (12)

where inequality (11) holds by (10) and inequality (12) holds because each coalition is considered k 1 times in the summation. Hence, the claim follows.

It is worth noticing that the approximation ratio guaranteed by Theorem 14 approaches k as nk tends to infinity. This result is particularly significant when considering a scenario in which a population of n agents has to be divided into a given number of groups, each of which sized as a quota of the total: as n grows and tends to infinity, also nk does.

6 Conclusions

Besides closing the gaps between all non-tight upper and lower bounds derived in this paper, we believe that hedonic games with fixed-size coalitions may spur future research along several directions. Some of these are: deriving price of anarchy bounds as a function of vector (n1, . . . , nk), considering the efficiency of stable outcomes with respect to the egalitarian social welfare (which measures the quality of an outcome by means of the lowest agent s utility), strengthening the stability notion by allowing permutations involving more than two agents, considering other well-established classes of hedonic games as, for instance, fractional hedonic games (Aziz et al. 2019). With respect to the latter question, we observe that Theorem 1 keeps holding in this setting as well, up to an O(n2) slowdown on the convergence time for simple games.

Abizada, A. 2019. Exchange-stability in roommate problems. Review of Economic Design, 23: 3 12. Agarwal, A.; Elkind, E.; Gan, J.; and Voudouris, A. A. 2020. Swap Stability in Schelling Games on Graphs. In Proceedings of the The Thirty-Fourth Conference on Artificial Intelligence (AAAI), 1758 1765. Alcalde, J. 1995. Exchange-proofness or divorce-proofness? Stability in one-sided matching markets. Economic Design, 1: 275 287. Asahiro, Y.; Iwama, K.; Tamaki, H.; and Tokuyama, T. 2000. Greedily Finding a Dense Subgraph. Journal of Algorithms, 34(2): 203 221. Aziz, H.; Brandl, F.; Brandt, F.; Harrenstein, P.; Olsen, M.; and Peters, D. 2019. Fractional Hedonic Games. ACM Trans. Economics and Comput., 7(2): 6:1 6:29. Aziz, H.; Brandt, F.; and Seedig, H. G. 2013. Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195: 316 334. Aziz, H.; and Goldwaser, A. 2017. Coalitional Exchange Stable Matchings in Marriage and Roommate Markets. In Proceedings of the 16th Conference on Autonomous Agents and Multi Agent Systems, (AAMAS), 1475 1477. Aziz, H.; and Savani, R. 2016. Hedonic Games. In Handbook of Computational Social Choice, 356 376. Ballester, C. 2004. NP-completeness in hedonic games. Games Econ. Behav., 49(1): 1 30. Banerjee, S.; Konishi, H.; and S onmez, T. 2001. Core in a simple coalition formation game. Social Choice and Welfare, 18(1): 135 153. Bil o, D.; Bil o, V.; Lenzner, P.; and Molitor, L. 2020. Topological Influence and Locality in Swap Schelling Games. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), 15:1 15:15. Bil o, V.; Fanelli, A.; Flammini, M.; Monaco, G.; and Moscardelli, L. 2019. Optimality and Nash Stability in Additive Separable Generalized Group Activity Selection Problems. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, (IJCAI), 102 108. Bogomolnaia, A.; and Jackson, M. O. 2002. The Stability of Hedonic Coalition Structures. Games and Economic Behavior, 38(2): 201 230. Cechl arov a, K.; and Manlove, D. F. 2005. The exchangestable marriage problem. Discret. Appl. Math., 152(1-3): 109 122. Cechl arov a, K.; and Romero-Medina, A. 2001. Stability in coalition formation games. Int. J. Game Theory, 29(4): 487 494. Chen, J.; Chmurovic, A.; Jogl, F.; and Sorge, M. 2021. On (Coalitional) Exchange-Stable Matching. In Proceedings of the 14th International Symposium on Algorithmic Game Theory SAGT, 205 220.

Cseh, A.; Fleiner, T.; and Harj an, P. 2019. Pareto optimal coalitions of fixed size. Journal of Mechanism and Institution Design, 4(1): 87 108. Damamme, A.; Beynier, A.; Chevaleyre, Y.; and Maudet, N. 2015. The Power of Swap Deals in Distributed Resource Allocation. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 625 633. Deng, X.; and Papadimitriou, C. H. 1994. On the Complexity of Cooperative Solution Concepts. Mathematics of Operations Research, 19(2): 257 266. Dreze, J. H.; and Greenberg, J. 1980. Hedonic Coalitions: Optimality and Stability. Econometrica, 48(4): 987 1003. Elkind, E.; Fanelli, A.; and Flammini, M. 2020. Price of Pareto Optimality in hedonic games. Artif. Intell., 288: 103357. Flammini, M.; Kodric, B.; Monaco, G.; and Zhang, Q. 2021a. Strategyproof Mechanisms for Additively Separable and Fractional Hedonic Games. Journal of Artificial Intelligence Research, 70: 1253 1279. Flammini, M.; Monaco, G.; Moscardelli, L.; Shalom, M.; and Zaks, S. 2021b. On the Online Coalition Structure Generation Problem. Journal of Artificial Intelligence Research, 72: 1215 1250. Gale, D.; and Shapley, L. S. 1962. College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1): 9 15. Gourv es, L.; Lesca, J.; and Wilczynski, A. 2017. Object Allocation via Swaps along a Social Network. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI), 213 219. Gross-Humbert, N.; Benabbou, N.; Beynier, A.; and Maudet, N. 2021. Sequential and Swap Mechanisms for Public Housing Allocation with Quotas and Neighbourhood-Based Utilities. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1521 1523. Massand, S.; and Simon, S. 2019. Graphical One-Sided Markets. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI), 492 498. Nash, J. F. 1950. Equilibrium points in n-person games. Proceedings of the National Academy of Science, 36(1): 48 49. Olsen, M. 2009. Nash Stability in Additively Separable Hedonic Games and Community Structures. Theory Comput. Syst., 45(4): 917 925. Peters, D. 2016. Complexity of Hedonic Games with Dichotomous Preferences. In Proceedings of the Thirtieth Conference on Artificial Intelligence AAAI, 579 585. Schaffer, A.; and Yannakakis, M. 1991. Simple Local Search Problems That are Hard to Solve. SIAM J. Comput., 20: 56 87. Sung, S. C.; and Dimitrov, D. 2010. Computational complexity in additive hedonic games. Eur. J. Oper. Res., 203(3): 635 639.

Wright, M.; and Vorobeychik, Y. 2015. Mechanism Design for Team Formation. In Proceedings of the Twenty-Ninth Conference on Artificial Intelligence AAAI, 1050 1056.