# altruistic_hedonic_games__fb796a94.pdf

Journal of Artiﬁcial Intelligence Research 75 (2022) 129 169 Submitted 02/2022; published 09/2022

Altruistic Hedonic Games

Anna Maria Kerkmann anna.kerkmann@hhu.de Nhan-Tam Nguyen nhan-tam.nguyen@hhu.de Anja Rey anja.rey@hhu.de Lisa Rey lisa.rey@hhu.de Jörg Rothe rothe@hhu.de Lena Schend lena.schend@googlemail.com Alessandra Wiechers alessandra.wiechers@hhu.de Heinrich-Heine-Universität Düsseldorf, Universitätsstraße 1, 40225 Düsseldorf, Germany

Hedonic games are coalition formation games in which players have preferences over the coalitions they can join. For a long time, all models of representing hedonic games were based upon selﬁsh players only. Among the known ways of representing hedonic games compactly, we focus on friend-oriented hedonic games and propose a novel model for them that takes into account not only the players own preferences but also their friends preferences. Depending on the order in which players look at their own or their friends preferences, we distinguish three degrees of altruism: selﬁsh-ﬁrst, equal-treatment, and altruistic-treatment preferences. We study both the axiomatic properties of these games and the computational complexity of problems related to various common stability concepts.

1. Introduction

The breathtakingly rapid development of artiﬁcial intelligence (AI) is largely based on mimicking by means of tools, methods, and insights from computer science, mathematics, and other ﬁelds of science human intelligence and human properties, attributes, and behavior as individuals and in society. Interaction among agents in a multiagent system a key topic in AI is typically modeled via game-theoretic means. From the early beginnings of (noncooperative) game theory due to von Neumann and Morgenstern (1944), a player (or agent we will use the terms player and agent synonymously) in a game has been viewed as a homo economicus: Such players are perfectly rational, narrowly selﬁsh, and interested only in maximizing their own gains, no matter what the costs to the other players are. In spirit, this assumption is somewhat related to Darwin s thesis of survival of the ﬁttest, where survival essentially is measured by the ability of reproduction. However, even in terms of biology and evolution, there are reasonable doubts if selﬁshness alone (in the sense that more aggressive behavior yields more oﬀspring) is really the key to success. Recently, Hare and Woods (2020) countered Darwin s thesis with their survival of the friendliest. Speciﬁcally, one of their many arguments is that of the two species making up the genus Pan among the great apes, bonobos and chimpanzees, the bonobos beneﬁt from their much friendlier behavior: The most successful male bonobo has more progenies than the most successful male chimpanzee, i.e., has a higher reproduction rate. Hare and Woods (2020) also argue that the evolutionary supremacy of the human species is mainly due to their

c 2022 AI Access Foundation. All rights reserved.

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

Figure 1: Example of a network of friends

friendly behavior, which made it possible for them to form larger social groups and even societies.

Now, if we agree that AI is best oﬀwhen mimicking natural life and simulating realworld human behavior, the homo economicus from the early days of game theory is obsolete and better models are needed. Indeed, relentlessly aiming at one s own advantage and maximizing one s own utility regardless of the consequences for others may in fact not only diminish an agent s individual gains, but it may also harm the society of agents in a multiagent system as a whole. With this in mind, there have been some approaches of taking ethics, psychology, emotions, and behavioral dynamics into consideration in collective decision-making (Regenwetter, Grofman, Marley, & Tsetlin, 2006; Popova, Regenwetter, & Mattei, 2013; Rothe, 2019). This paper integrates altruism into the model of hedonic games.

Hedonic games, originally proposed by Drèze and Greenberg (1980) and later formally modeled by Bogomolnaia and Jackson (2002) and Banerjee, Konishi, and Sönmez (2001), are coalition formation games in which players have preferences over coalitions (subsets of players) they can be part of. In the context of decentralized coalition formation, several stability concepts and representations have been studied from an axiomatic and a computational complexity point of view; see the survey by Woeginger (2013a) on this topic and the book chapters by Aziz and Savani (2016) and Elkind and Rothe (2015) for an overview.

Dimitrov, Borm, Hendrickx, and Sung (2006) proposed a model that allows for compact representation of hedonic games, namely, the friend-and-enemy encoding of the players preferences, where each player divides the other players into friends and enemies. Based on this encoding, they suggest two models of preference extensions: appreciation of friends and aversion to enemies. In friend-oriented hedonic games, a coalition A is preferred to another coalition B if A contains either more friends than B or the same number of friends as B but fewer enemies than B. This setting corresponds to a network of friends represented as a graph. We focus on the natural restriction of symmetric friendship relations and assume that the graph is undirected. For example, suppose there are four players, 1, 2, 3, and 4, and let 1 be friends with 2 but neither with 3 nor with 4, while 2 and 3 are friends with each other but not with 4. The corresponding network is displayed in Figure 1. Now, in the friend-oriented extension, player 2 prefers teaming up with 1 and 3 to forming a coalition with 1 and 4. Player 1, on the other hand, is indiﬀerent between coalitions {1, 2, 3} and {1, 2, 4} because they both contain the one friend of 1 s (namely, 2) and one of 1 s enemies (either 3 or 4). However, following the paradigm of the survival of the friendliest, 1 can be expected to care about her friend 2 s interests and thus might prefer a coalition in which 2 is satisﬁed ({1, 2, 3}) to one in which 2 is less satisﬁed ({1, 2, 4}). Indeed, player 1 would have a direct advantage of respecting 2 s interests, since 2 and 3 being friends can be expected to cooperate better than 2 and 4. In order to model such preferences, starting from friend-oriented hedonic games, we will introduce three degrees of altruism.

Altruistic Hedonic Games

1.1 Our Contribution

Focusing on the friend-oriented extension of preferences due to Dimitrov et al. (2006) and considering the idea of players caring about their friends preferences, we propose hedonic games with three degrees of altruistic inﬂuences: from being selﬁsh ﬁrst and considering one s friends preferences to be of lower priority, over aggregating one s own opinions and those of one s friends equally, to truly altruistically letting one s friends decide ﬁrst. The latter is the most altruistic case we consider, as we assume that from a player s perspective only friends can be consulted, while players further away (such as a friend s friend that is one s own enemy) cannot be communicated with or cannot be trusted or do not provoke the need to help. In a social network, for example, the whole set of players other than one s own friends might not even be known. It may be debatable whether altruism is really the best term to capture our model. After all, even though the players utilities for a coalition don t depend on their own preferences alone, they do not depend on all the players preferences either but merely on their own and their friends preferences so one might be tempted to call this empathy among friends rather than altruism. However, we have argued in the previous paragraph why it does make sense to consider only one s friends in the network. And even if our agents may not be completely selﬂess, they do behave altruistically toward their friends. Another important reason to not change the term altruistic hedonic game is that, meanwhile, quite a number of papers (listed in Sections 1.2 and 2.2.2) have adopted this term, so renaming it now would only cause confusion in the literature. Since we consider friends to be equally important, we ﬁrst focus on their average valuation when comparing two coalitions. To distinguish the above-mentioned three degrees of altruism, we assign a suﬃciently large weight either to a player s own valuation (the selﬁshﬁrst case), or to the average valuation of this player s friends (the truly altruistic case), or to none of them (the equal-treatment case). As an alternative, we also propose a minimum-based variant where we replace the average by the minimum in our previous deﬁnitions. As innocent as this small change appears to be, it is in fact as fundamental as considering egalitarian social welfare instead of utilitarian social welfare in multiagent resource allocation.1 Minimum-based altruism may be more suitable than average-based altruism when the well-being of the entire group of agents crucially suﬀers from their unhappiest member. All of the proposed games are compactly representable but not fully expressive. However, as we will see, our representations of altruistic hedonic games can express other hedonic games than those expressible by diﬀerent compact representations common in the literature. We provide a two-part study of these newly introduced games: First, we analyze the deﬁned preferences with respect to axiomatic properties such as anonymity, monotonicity, and friend

1. As noted by Nguyen, Nguyen, Roos, and Rothe (2014, p. 257), utilitarian social welfare sums up the agents individual utilities in a given allocation, thus providing a useful measure of the overall and also of the average beneﬁt for society. For instance, in a combinatorial auction the auctioneer s aim is to maximize the auction s revenue (i.e., the sum of the prizes paid for the items auctioned), no matter which agent can realize which utility. In contrast, egalitarian social welfare gives the utility of the agent who is worst oﬀin a given allocation, which provides a useful measure of fairness in cases where the minimum needs of all agents are to be satisﬁed.

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

dependence; second, we consider various common stability concepts and show that our games always permit (contractually) individually stable and Nash stable solutions, and that testing whether a given solution is stable with respect to these concepts is tractable. We furthermore characterize when perfect solutions exist, and we analyze the computational complexity of the veriﬁcation and the existence problem of core stable solutions.

1.2 Preliminary Conference and Workshop Versions

This paper merges and extends preliminary versions that appeared in the proceedings of several conferences: At the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 16), Nguyen, Rey, Rey, Rothe, and Schend (2016) introduced altruistic hedonic games and established the ﬁrst related results, which they also presented at the 7th International Workshop on Cooperative Games in Multiagent Systems (Coop MAS 16) in Singapore and at the 6th International Workshop on Computational Social Choice (COMSOC 16) in Toulouse, France (the latter two without archival proceedings). At the 9th European Starting AI Researcher Symposium (STAIRS 20), Wiechers and Rothe (2020) introduced minimum-based altruistic hedonic games, and Rothe (2021) surveyed altruism in game theory for the senior-member track of the 35th AAAI Conference on Artiﬁcial Intelligence (AAAI 21). Kerkmann and Rothe (2021) presented their study of the axiomatic properties of (minimum-based) altruistic hedonic games at the 8th International Workshop on Computational Social Choice (COMSOC 21, without archival proceedings) in Haifa, Israel. We have extended these preliminary versions by merging them and adding many more examples, discussion, omitted proofs, and further results (including Example 6.7, Lemma 6.2, Theorems 5.6, 5.7, 5.8, and 6.9, and Corollaries 6.10 and 6.15).

1.3 Organization

In Section 2, we present related work, focusing on notions of altruism in noncooperative and cooperative games and on related literature on hedonic games. In Section 3, we give the basic deﬁnitions of hedonic games and some of the most common stability concepts. We formally introduce altruistic hedonic games in Section 4, discuss them in comparison with related but diﬀerent notions from the literature, and study their axiomatic properties in Section 5. In Section 6, we deal with stability concepts and study the related existence and veriﬁcation problems in terms of their complexity. Section 7 concludes the paper and raises some interesting open questions.

2. Related Work

In this section, we present related work, in particular regarding various ways of introducing notions of altruism into existing game-theoretic models, both in noncooperative and cooperative game theory (Sections 2.1 and 2.2). Since the literature about altruism in noncooperative games is older and richer than in cooperative games, we start with the former.

2.1 Altruism in Noncooperative Games

Game theory more or less started with the early papers by Borel (1921) and von Neumann (1928) and the book by von Neumann and Morgenstern (1944) who explored noncooperative

Altruistic Hedonic Games

games in which all players are on their own, competing with each other to win the game and to maximize their own proﬁt. For more background on noncooperative game theory and its algorithmic aspects, the reader is referred, e.g., to the book edited by Nisan, Roughgarden, Tardos, and Vazirani (2007) and the book chapter by Faliszewski, Rothe, and Rothe (2015). Altruism in games has been considered mainly for noncooperative games to date. We give a short overview, starting with models of social components through a network of players.

2.1.1 Games with Social Networks

Ashlagi, Krysta, and Tennenholtz (2008) introduced social context games by embedding a strategic game into a social context that consists of a graph of neighborhood among the players and an aggregation function. The resulting social context game has the same players and strategies as the underlying strategic game. However, the players payoﬀs in the resulting game do not only depend on their original payoﬀs but also on the neighborhood graph and the aggregation functions that express the social context. Ashlagi et al. (2008) focus on resource selection games (a famous subclass of congestion games2) as the underlying strategic games and on the following four social contexts: They obtain the payoﬀs of the social context game by either taking the minimum, maximum, or average of the players and their neighbors original payoﬀs (so-called best-member, min-max, or surplus collaborations) or they aggregate by so-called competitive rankings. Bilò, Celi, Flammini, and Gallotti (2013) apply the model of social context games by Ashlagi et al. (2008) to linear congestion games and Shapley cost-sharing games with the aggregation functions min, max, and sum (or average). They characterize the graph topologies modeling these social contexts such that the existence of pure Nash equilibria (as deﬁned in Footnote 2) is guaranteed.

Hoefer, Penn, Polukarov, Skopalik, and Vöcking (2011) also consider players being embedded in a social network and assume that certain constraints specify which sets of coalitions may jointly deviate from their actual strategies in the game. When doing so, however, they assume that the players are considerate not to hurt others: Players ignore (i.e., choose to not carry out) potentially proﬁtable group deviations whenever those would cause their neighbors utilities to decrease. Exploring the properties of so-called considerate equilibria in resource selection games, Hoefer et al. (2011) show that there exists a state that is stable with respect to selﬁsh and considerate behavior at the same time.

Anagnostopoulos, Becchetti, de Keijzer, and Schäfer (2013) study altruism and spite in strategic games. They consider directed weighted social networks where player i assigning a positive (negative) weight to player j means that i is altruistic (spiteful) towards j. They consider three classes of strategic games, namely, congestion games, minsum scheduling games, and generalized second price auctions, and study the price of anarchy (relating the worst-case cost of an equilibrium to the cost of an optimal outcome; see Koutsoupias and Papadimitriou (1999)) for these games.

2. A fundamental property of congestion games is that they always have a Nash equilibrium in pure strategies (Rosenthal, 1973, see also, e.g., Ashlagi et al., 2008), i.e., there always exists a proﬁle of pure strategies such that no player has an incentive to deviate from her strategy in the proﬁle, provided the other players also stay with their strategies in the proﬁle.

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

2.1.2 Games with an Altruistic Factor

We now turn to work that models altruism in strategic games by means of an altruistic factor that is integrated into the agents cost or payoﬀfunctions.

Hoefer and Skopalik (2013) consider altruism in atomic congestion games. There are myopic selﬁsh players and a set of resources, each with a nondecreasing delay function. Every player chooses a strategy by selecting (or allocating) a subset of resources, and experiences a delay corresponding to the total delay on all selected resources, which depends on the number of players that have allocated any of these resources. The goal of each player is to minimize the experienced delay. Now, altruism is introduced by Hoefer and Skopalik (2013) into such games as follows. They assume that the players are partly selﬁsh and partly altruistic, which is formalized by an altruism level βi [0, 1] for each player i, where βi = 0 means i is purely selﬁsh and βi = 1 means i is purely altruistic. These players incentive is to optimize a linear combination of personal cost (their individually experienced delay) and social cost (the total delay of all players). Hoefer and Skopalik (2013) study under which conditions there exist pure Nash equilibria in various types of such games. They also show that optimal stability thresholds (the minimum number of altruists such that there exists an optimal Nash equilibrium) and optimal anarchy thresholds (the minimum number of altruists such that every Nash equilibrium is optimal) can be computed in polynomial time. Chen, de Keijzer, Kempe, and Schäfer (2014) study a similar model for nonatomic congestion games.

Apt and Schäfer (2014) introduce so-called selﬁshness levels for strategic games, which are based on the so-called altruistic games due to Ledyard (1995) (and, more recently, De Marco & Morgan, 2007). Selﬁshness levels measure the discrepancy between the social welfare in a Nash equilibrium and in a social optimum. After showing that their model is equivalent to some previous models of altruism due to Chen et al. (2014), Elias, Martignon, Avrachenkov, and Neglia (2010), and Caragiannis, Kaklamanis, Kanellopoulos, Kyropoulou, and Papaioannou (2010), Apt and Schäfer (2014) determine the selﬁshness levels of several well-studied strategic games, such as fair cost-sharing games, linear congestion games, the n-player prisoner s dilemma, the n-player public goods game, and the traveler s dilemma game. While these games have ﬁnite selﬁshness levels, Apt and Schäfer (2014) also show that other speciﬁc games like Cournot competition, tragedy of the commons, and Bertrand competition have an inﬁnite selﬁshness level.

Rahn and Schäfer (2013) introduce yet another class of games, which they call social contribution games. They are motivated by the fact that altruistic behavior may actually render equilibria more ineﬃcient (e.g., in congestion games) and may thus harm society as a whole (Anagnostopoulos et al., 2013). This is not the case for so-called valid utility games, though (Chen et al., 2014). Therefore, a question naturally arises: What is it that causes or inﬂuences the ineﬃciency of equilibria in games with altruistic players? In social contribution games, players individual costs are set to the cost they cause for society just because of their presence, thus providing a useful abstraction of games with altruistic players when the robust price of anarchy is to be analyzed. Rahn and Schäfer (2013) in particular show that social contribution games are what they call altruism-independently smooth, which means that the robust price of anarchy in these games remains unaltered under arbitrary altruistic extensions.

Altruistic Hedonic Games

2.2 Altruism in Cooperative Games

In a cooperative game, players may work together by forming groups, so-called coalitions, and may take joint actions so as to realize their goals better than if they were on their own. If a coalition structure (i.e., a partition of the players into coalitions) has formed, the question arises how stable it is, i.e., whether some players may have an incentive to leave their coalition and to join another one. There are plenty of special types of cooperative games and of stability notions some of which we will encounter below. For more background on cooperative game theory, the reader is referred, e.g., to the books by Peleg and Sudhölter (2003) and Chalkiadakis, Elkind, and Wooldridge (2011) and to the book chapter by Elkind and Rothe (2015).

2.2.1 Hedonic Games

Hedonic games are cooperative games with nontransferable utility. After Drèze and Greenberg (1980) introduced the concept, Banerjee et al. (2001) and Bogomolnaia and Jackson (2002) formally modeled them. In such coalition formation games, players have preferences over the coalitions they can be a member of. Since every player in a hedonic game needs to rank (by a weak order) exponentially many (in the number of players) coalitions, it is crucial to ﬁnd compact representations for these games. One such representation is the friends-and-enemies encoding by Dimitrov et al. (2006) where players partition the other players into two groups: friends and enemies. Based on this representation, they suggest two preference extensions. In the friend-oriented preference extension, which will be formally deﬁned in Section 3, players prefer coalitions with more friends, and only if two coalitions have the same number of friends, players prefer to be with fewer enemies. In the enemy-oriented preference extension, on the other hand, players prefer coalitions with fewer enemies, and only if two coalitions have the same number of enemies, players prefer to be with more friends. In addition to representation issues, much work has been done regarding the properties of hedonic games such as various notions of stability (see, e.g., Cechlárová & Hajduková, 2003, 2004; Aziz, Brandt, & Harrenstein, 2013a; Dimitrov et al., 2006) and studying the related problems in terms of their computational complexity (see, e.g., Ballester, 2004; Sung & Dimitrov, 2007, 2010; Woeginger, 2013b; Peters & Elkind, 2015; Peters, 2016). Needless to say that most of the papers just listed contribute to more than one of these goals; for example, Dimitrov et al. (2006) both introduce new ways of representing hedonic games and study their stability. The friends-and-enemies encoding of Dimitrov et al. (2006) has inspired a lot of follow-up work. For example, Ota, Barrot, Ismaili, Sakurai, and Yokoo (2017) allow for neutral agents in addition to friends and enemies and study their impact on (strict) core stability. Also considering friends, enemies, and neutral agents, Kerkmann, Lang, Rey, Rothe, Schadrack, and Schend (2020) propose a bipolar extension of the responsive extension principle and use it to derive partial preferences over coalitions, characterize coalition structures that necessarily or possibly satisfy certain stability concepts, and study the related problems in terms of their complexity. Barrot, Ota, Sakurai, and Yokoo (2019) study the impact of additional unknown agents, and Rey, Rothe, Schadrack, and Schend (2016) study wonderful stability (a.k.a. perfectness) and strict core stability in enemy-oriented hedonic games. Peters and

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

Elkind (2015) establish metatheorems that help proving NP-hardness results for the problem of checking whether given hedonic games admit stable coalition structures. For more background on hedonic games, the reader is referred to the book chapters by Aziz and Savani (2016) and Elkind and Rothe (2015) and to the excellent survey by Woeginger (2013a).

2.2.2 Altruism in Hedonic Games

Since we ﬁrst introduced altruistic hedonic games in 2016 (Nguyen et al., 2016),3 there has been some follow-up literature on this topic. Schlueter and Goldsmith (2020) introduced super altruistic hedonic games and studied them with respect to various stability notions. In their model, players in the same coalition have a diﬀerent impact on a player based on their distances in the underlying network of friends. Their model is also related to the social distance games by Brânzei and Larson (2011) where the utility of a player is deﬁned by measuring her distance to the other members of her coalition. Kerkmann and Rothe (2020) extend the altruistic hedonic games to coalition formation games in general. While our model is hedonic in the sense that players preferences only depend on the coalitions that they are part of, in their model players behave altruistically also towards their friends in other coalitions, which makes their games nonhedonic. Recently, Bullinger and Kober (2021) introduced loyalty in cardinal hedonic games. In their model, each player has a loyalty set that contains all players for which she has positive utility when being together with this player in a coalition of size two. The loyal variant of a cardinal hedonic game is then deﬁned to have the same players as the original game but with redeﬁned utilities. More speciﬁcally, the utility of a player for a coalition structure is derived by taking the minimum of her own original utility and the original utilities of all players in her loyalty set who are also in her coalition. Bullinger and Kober (2021) also deﬁne a k-fold loyal variant where the loyal variant is applied k times. Note that our minbased altruistic hedonic games with equal-treatment preferences (min-based EQ AHGs) are equivalent to their loyal variant of symmetric friend-oriented hedonic games. Their results for this model imply that, given some min-based EQ AHG, a designated agent, and some threshold, deciding whether there exists a coalition for which this agent s utility reaches the threshold is NP-complete (Bullinger & Kober, 2021, Theorem 2). Furthermore, given some min-based EQ AHG where the underlying network of friends is connected and regular, the coalition structure consisting of the grand coalition is strictly core stable (Bullinger & Kober, 2021, Proposition 10). Yet, they leave the following problems open: the complexity of computing core stable coalition structures for min-based EQ AHGs, and the question of whether there might exist min-based EQ AHGs without core stable coalition structures. Based on the social context games (Ashlagi et al., 2008) described in Section 2.1.1, Monaco, Moscardelli, and Velaj (2018) introduced social context hedonic games (which, in fact, are nonhedonic games). Such games are based on additively separable utilities, an altruism factor, and a social network among the players. A player s utility for a coalition

3. (Nguyen et al., 2016) is one of the preliminary conference versions of the present paper (recall Section 1.2) and has thus been incorporated into it.

Altruistic Hedonic Games

structure is then deﬁned to be the sum of her own additively separable utility for her coalition and the utilities of her neighbors in the network, the latter weighted by the altruism factor. Remotely related to our min-based altruistic hedonic games is the work of Monaco, Moscardelli, and Velaj (2019) who study the modiﬁed fractional hedonic games introduced by Olsen (2012). These games behave qualitatively diﬀerent than the fractional hedonic games due to Aziz, Brandl, Brandt, Harrenstein, Olsen, and Peters (2019). In particular, Monaco et al. (2019) study the performance of Nash (and, to some extent, core) stable outcomes in modiﬁed fractional hedonic games with egalitarian social welfare.

3. Preliminaries

A hedonic game is given by a pair (N, ), where N = {1, . . . , n} is a set of players and = ( 1, . . . , n) is a list of the players preferences. For i N, let N i = {C N | i C} denote the set of coalitions containing i. Player i s preference relation i N i N i

induces a complete, weak preference order over N i. For A, B N i, we say that player i weakly prefers A to B if A i B, that i prefers A to B (A i B) if A i B but not B i A, and that i is indiﬀerent between A and B (A i B) if A i B and B i A. We call C N i

acceptable for player i if C i {i}. A coalition structure is a partition Γ = {C1, . . . , Ck} of the players into k coalitions C1, . . . , Ck N (i.e., Sk r=1 Cr = N and Cr Cs = for all distinct r, s {1, . . . , k}). The unique coalition in Γ containing player i N is denoted by Γ(i). The set of all coalition structures for a set of agents N is denoted by CN. For two coalition structures Γ, CN, we say that agent i prefers Γ to if i prefers Γ(i) to (i) (and analogously so for weak preference and indiﬀerence).

3.1 Friend-Oriented Preference Extension

In order to avoid preference orders that are exponentially long in the number of players, a common way to represent players preferences is to consider a network of friends (Dimitrov et al., 2006): Every player i N has a set of friends Fi N \ {i} and a set of enemies Ei = N \ (Fi {i}). Visually, we represent the players in N by the vertices in a graph G = (N, H), and let a directed edge (i, j) H denote that j is i s friend, that is, the open neighborhood of i represents the set of i s friends Fi = {j | (i, j) H}. Since in the context of stability it is reasonable to consider symmetric friendship relations only (as noted, e.g., by Woeginger, 2013a), we will focus on undirected graphs representing networks of friends. In the friend-oriented preference extension (Dimitrov et al., 2006), players prefer coalitions with more friends, and only if two coalitions have the same number of friends, players prefer to be with fewer enemies. Formally, deﬁne

A F i B |A Fi| > |B Fi| or (|A Fi| = |B Fi| and |A Ei| |B Ei|). (1)

Note that friend-oriented preferences can be represented additively, by assigning a value of n = |N| to each friend and a value of 1 to each enemy (Dimitrov et al., 2006): For any player i N and any coalition A N i, deﬁne the value of a coalition by

vi(A) = n|A Fi| |A Ei|. (2)

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

Figure 2: Relations between the stability notions deﬁned in Section 3.2. In this ﬁgure, there is a directed path from notion A to notion B if and only if A implies B.

It then holds that (n 1) vi(A) n(n 1), and vi(A) > 0 if and only if |A Fi| > 0. For A, B N i, we have

A F i B vi(A) vi(B). (3)

3.2 Stability Concepts

The following stability concepts are commonly studied in hedonic games (Aziz & Savani, 2016). The relations between these concepts are illustrated in Figure 2.

Deﬁnition 3.1. Let (N, ) be a hedonic game and Γ a coalition structure. A coalition C N blocks Γ if for each i C it holds that C i Γ(i). If there is at least one i C with C i Γ(i) while C j Γ(j) holds for the other players j = i in C, we call C weakly blocking. A coalition structure Γ is said to be

1. individually rational (IR) if for all i N, Γ(i) is acceptable;

2. Nash stable (NS) if for all i N and for each C Γ { } with Γ(i) = C, it holds that Γ(i) i C {i};

3. individually stable (IS) if for all i N and for each C Γ { }, it either holds that Γ(i) i C {i} or there is a player j C with C j C {i};

4. contractually individually stable (CIS) if for all i N and for each C Γ { }, it either holds that Γ(i) i C {i}, or there is a player j C with C j C {i}, or there is a player k Γ(i) with i = k and Γ(i) k Γ(i) \ {i};

5. core stable (CS) if there is no nonempty coalition that blocks Γ;

6. strictly core stable (SCS) if there is no coalition that weakly blocks Γ; and

7. perfect if for all i N and for all C N i, it holds that Γ(i) i C.

4. Altruistic Hedonic Games

In this section, we introduce our new model that reﬁnes friend-oriented hedonic games by taking altruistic inﬂuences into account. In this model, players still want to be with as many friends (and, secondarily, with as few enemies) as possible, but in addition they want their friends to be as satisﬁed as possible.

Altruistic Hedonic Games

Figure 3: Network of friends representing the hedonic game in Example 4.1

4.1 Failure of a Naïve Approach

A ﬁrst attempt to formalize this idea (that will turn out to fail) is the following. Consider the scenario where i N has a friend-oriented preference extension (according to Equivalence (1)) except that, whenever the number of friends in A and B is the same and so is the number of enemies in A and B (i.e., A F i B), i now prefers A to B if more of i s friends that are contained in A and B prefer A to B than B to A (again according to Equivalence (1)). Formally:

A NA i B |A Fi| > |B Fi| or (4)

(|A Fi| = |B Fi| and |A Ei| < |B Ei|) or

(|A Fi| = |B Fi| and |A Ei| = |B Ei| and

|{j A B Fi | A F j B}| |{j A B Fi | B F j A}|).

Intuitively, according to (4), a player is selﬁsh ﬁrst, but as soon as she is indiﬀerent between two coalitions in the sense of (1), she cares about her friends preferences. A major disadvantage of this deﬁnition, however, is that irrational preference orders can arise, i.e., preference orders that are not transitive in general, as the following example shows.

Example 4.1. Consider the hedonic game (N, NA) with N = {1, 2, 3, 4, 5, 6, 7} and the network of friends from Figure 3. For coalitions A = {1, 2, 3, 5}, B = {1, 2, 4, 7}, and C = {1, 3, 4, 6}, it holds that A NA 1 B and B NA 1 C, yet C NA 1 A, violating transitivity.

In order to ensure transitivity, we have to add an extra condition to Equivalence (4). One idea would be to demand indiﬀerence between all coalitions that are involved in a NA i - cycle by (4). This, however, can lead to a comparison of all coalitions containing a player, so determining a relation between two coalitions might comprise an exponential number of steps in the number of players. Then it would have been easier to give an arbitrary preference order as an input in the ﬁrst place. Another idea would be to include the preferences of all friends, not only of those contained in the considered coalitions, but this would still lead to preference orders that are not transitive and would also contradict the concept of hedonic games. In the following, we take a diﬀerent approach that does not violate transitivity.

4.2 Modeling Altruism Based on the Friend-Oriented Preference Extension

Given the failure of extending friend-oriented preferences by breaking ties with majority voting, we consider the following model instead: When comparing two coalitions A and B, player i considers two aspects. First, i takes her own friend-oriented value for the coalitions into account and, second, she also incorporates the opinions of her friends in A and B. As i incorporates her friends opinions, she aggregates their friend-oriented values by either taking

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

the average or the minimum. While the ﬁrst variant gives equal weights to all her friends, the second variant is better motivated in situations when i wishes to improve the satisfaction of the friend that is worst oﬀbecause she would always suﬀer with her unhappiest friend. Recall that player i s value for coalition A N i in the friend-oriented encoding is given by vi(A) = n|A Fi| |A Ei|. We denote the average value of i s friends in A and the average value of i and her friends in A by

avg F i (A) = X

va(A) |A Fi| and avg F+ i (A) = X

a (A Fi) {i}

va(A) |(A Fi) {i}|. (5)

Note that normalization by the number of i s friends in a coalition prevents a tyranny of the many (otherwise, large coalitions might be preferred merely because they contain more friends). Similarly, we denote the corresponding minimum values by

min F i (A) = min a A Fi{va(A)} and min F+ i (A) = min a (A Fi) {i}{va(A)} (6)

where the minimum of the empty set is deﬁned as zero. Assigning a weight to player i s own contribution in comparison to her friends inﬂuence on her preferences, we will distinguish between three degrees of altruism:

(a) Selﬁsh First (SF): A player is selﬁsh ﬁrst and asks her friends only in case of indifference, i.e., initially she decides which of two coalitions she prefers friend-orientedly, and if and only if she is indiﬀerent between them, she asks her friends for a vote. For a constant M n2, we use the utility functions

uavg SF i (A) = M vi(A) + avg F i (A) and (7)

umin SF i (A) = M vi(A) + min F i (A) (8)

to deﬁne agent i s

avg-based SF altruistic preferences by A avg SF i B uavg SF i (A) uavg SF i (B);

min-based SF altruistic preferences by A min SF i B umin SF i (A) umin SF i (B).

(b) Equal Treatment (EQ): A player s and her friends friend-oriented opinions are treated equally for the decision. For the utility functions

uavg EQ i (A) = avg F+ i (A) and (9)

umin EQ i (A) = min F+ i (A), (10)

deﬁne agent i s

avg-based EQ altruistic preferences by A avg EQ i B uavg EQ i (A) uavg EQ i (B);

min-based EQ altruistic preferences by A min EQ i B umin EQ i (A) umin EQ i (B).

(c) Altruistic Treatment (AL): A player ﬁrst asks her friends for their opinions on a coalition they are contained in and adopts their average or minimum value; if and

Altruistic Hedonic Games

only if the consensus is indiﬀerence, the player decides for herself. For M n4, we use the utility functions

uavg AL i (A) = vi(A) + M avg F i (A) and (11)

umin AL i (A) = vi(A) + M min F i (A) (12)

to deﬁne agent i s

avg-based AL altruistic preferences by A avg AL i B uavg AL i (A) uavg AL i (B);

min-based AL altruistic preferences by A min AL i B umin AL i (A) umin AL i (B).

The next proposition shows that the deﬁnitions of the SF and AL preferences indeed capture the intuitive ideas behind them: In the case of SF preferences, the own value is the ﬁrst decisive factor, and in the case of AL preferences, the friends values are the ﬁrst decisive factor.

Proposition 4.2. For M n4, the following statements hold for each i N and for any two coalitions A, B N i:

1. vi(A) > vi(B) implies A avg SF i B,

2. vi(A) > vi(B) implies A min SF i B,

3. avg F i (A) > avg F i (B) implies A avg AL i B, and

4. min F i (A) > min F i (B) implies A min AL i B.

Proof. We just state the proofs for statements (1) and (3). The proofs for (2) and (4) are quite similar. We start with statement (1). The claim clearly holds for avg F i (A) avg F i (B). For

avg F i (A) < avg F i (B), it holds if and only if M > avg F i (B) avg F i (A) vi(A) vi(B) . The numerator is upper-

bounded by |B Fi| n(n 1)

|B Fi| |A Fi| (n 1)

|A Fi| = n2 1. For the denominator, we have vi(A) vi(B) > 0. Since vi(A) and vi(B) are integral, vi(A) vi(B) 1. Thus M > n2 1 suﬃces. We now turn to statement (3). The claim clearly holds for vi(A) vi(B). For vi(A) < vi(B), the claim holds if and only if M > vi(B) vi(A) avg F i (A) avg F i (B). The numerator is upper-bounded

by n(n 1) + (n 1) = n2 1 < n2. We further show that the denominator is lower-bounded by 1 n2 : First, for the sake of readability, let α = P a A Fi va(A) and β = P b B Fi vb(B). Then α and β are integral by the integrality of va and vb. Note that the premise avg F i (A) > avg F i (B) is equivalent to α |A Fi| > β |B Fi|. This implies α|B Fi| β|A Fi| 1, since α, β, |A Fi|, and |B Fi| are each integral. Thus

avg F i (A) avg F i (B) = α |A Fi| β |B Fi| = α|B Fi| β|A Fi|

|A Fi||B Fi| 1 |A Fi||B Fi| 1

Overall, M n4 suﬃces for statement (3). K

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

(a) Network of friends

{1, 2, 3, 4}

{1, 2, 3, 5}

v1(C) 10 9 9 8 5 5 4 4 4 v2(C) 4 3 9 8 5 4 10 v3(C) 4 9 3 8 5 10

avg F 1 (C) 4 6 6 8 5 5 4 10 10

avg F+ 1 (C) 6 7 7 8 5 5 4 7 7

(b) Player 1 s average values for certain coalitions

Figure 4: Diﬀerent approaches to altruism in the avg-based AHG from Example 4.3

Now, an altruistic hedonic game (AHG) is a hedonic game where the preference proﬁle consists of any mixture of avg-based and min-based SF, EQ, and AL altruistic preferences. The subclasses of AHGs where all agents have the same type of altruistic preferences are, e.g, called avg-based SF AHGs (with avg-based SF preferences), min-based AHGs (with minbased SF, EQ, or AL preferences), or EQ AHGs (with avgor min-based EQ preferences), etc. We will sometimes abuse notation and just write ui for player i s utility (or i for i s preference) when the considered altruistic model is clear from the context or when we talk about multiple models. The following examples illustrate the diﬀerent approaches to altruism in hedonic games. We start with explaining the three avg-based preferences in Example 4.3.

Example 4.3. Consider a game with ﬁve agents where the network of friends forms a path as shown in Figure 4a. The table in Figure 4b gives an overview of the relevant values and average values needed to determine player 1 s utilities for a number of acceptable coalitions depending on the degree of altruism. A dash indicates that a value does not exist. It can be seen that the friend-oriented preference and all three avg-based altruistic preferences are diﬀerent. Under the friend-oriented preference extension (1), player 1 s weak preference order F 1 is given in the ﬁrst line according to the values of v1. For avg-based SF preferences, the order remains the same; however, indiﬀerences are resolved based on the average of the friends values avg F 1 (C), as is the case here with {1, 2, 5} avg SF 1 {1, 2, 4}. Under avg-based EQ preferences, avg F+ 1 (C) is considered and the grand coalition is the most preferred one; intuitively, because all friends have a large number of friends at the same time. Finally, under avg-based AL preferences, the average of player 1 s friends avg F 1 (C) is considered ﬁrst. Player 1 s friends consider {1, 2, 5} and {1, 3, 4} to be the best coalitions. As player 1 values these two coalitions the same, she adopts this opinion and is indiﬀerent between them. Player 1 s friends are also indiﬀerent between {1, 2, 3} and {1, 2, 4}. Since player 1 assigns a higher value to {1, 2, 3}, she resolves this tie with {1, 2, 3} avg AL 1 {1, 2, 4}.

The next example shows that the min-based preferences are diﬀerent from the avg-based preferences.

Altruistic Hedonic Games

Figure 5: Network of friends with coalitions A and B in Example 4.4

uavg SF 1 uavg EQ 1 uavg AL 1 umin SF 1 umin EQ 1 umin AL 1 A 22M + 16 17.5 22 + 16M 22M + 13 13 22 + 13M B 22M + 19 19.75 22 + 19M 22M + 4 4 22 + 4M

Table 1: Player 1 s utilities for coalitions A and B in Example 4.4

Example 4.4. Let N = {1, . . . , 8} be the set of players with the network of friends displayed in Figure 5. Calculating the values of players 1, 2, 3, and 4 for the coalitions A = {1, 2, 3, 4, 5, 8} and B = {1, 2, 3, 4, 6, 7} reveals that v1(A) = v1(B) = v2(B) = v4(A) = 3 8 2 = 22, v2(A) = v3(A) = 2 8 3 = 13, v3(B) = 4 8 1 = 31, and v4(B) = 1 8 4 = 4. The resulting avg-based and min-based utilities of player 1 for these two coalitions are shown in Table 1. They reveal that, for all three degrees of altruism, player 1 prefers A to B when taking the minimum, yet prefers B to A when taking the average.

5. Properties of Altruistic Hedonic Games

In this section, we study which desirable properties are satisﬁed by altruistic preferences. First, however, we start with a short discussion of expressiveness and explain how our models diﬀer from other representations known from the literature.

5.1 Expressiveness and a Short Discussion of Our and Other Models

Our altruistic models are not fully expressive because players are indiﬀerent between friends and enemies, respectively. Also, for coalitions that only consist of enemies, all our altruistic preference extensions correlate with the original deﬁnition of friend-oriented preferences. Yet, AHGs can express games that cannot be expressed by friend-oriented hedonic games and vice versa. To wit, consider the friend-oriented hedonic game that is induced by the network of friends in Figure 4a. If we consider the friend-oriented preferences over size-two coalitions in this game, we see that, for example, agent 1 prefers {1, 2} to {1, 4}. Similar observations can be made for the other agents and all size-two coalitions. Now, assuming that the same preferences can be represented by an AHG (i.e., assuming that this friend-oriented hedonic game is an AHG), 1 s preference of {1, 2} over {1, 4} implies that 2 is a friend of 1 s in the network that underlies this AHG, whereas 4 is an enemy of 1 s. By consulting all preferences over size-two coalitions, we can then deduce that the AHG with these preferences needs to have the exactly same network of friends as the friend-oriented hedonic game (namely the network in Figure 4a). Yet, we have seen in Example 4.3 that this network of friends leads to diﬀerent preferences under the friend-oriented and under the altruistic extensions. This is a contradiction to the assumption that the friend-oriented hedonic game that is induced

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

by the network of friends in Figure 4a is also an AHG. Analogously, any AHG induced by the network of friends in Figure 4a is not friend-oriented. Hence, we have seen that friend-oriented hedonic games are neither a subclass of AHGs nor vice versa. Next, we show that AHGs are incomparable to additively separable hedonic games, fractional hedonic games, hedonic games with Bor W-preferences, and FEN-hedonic games (for the deﬁnitions of these representations, see Aziz, Brandt, & Seedig, 2013b; Aziz et al., 2019; Cechlárová & Hajduková, 2003, 2004; Kerkmann et al., 2020). Note that in all of the above models two players preference orders are independent from each other, but in our models they might depend on each other. Players are free in making friends; however, the induced preferences crucially depend on their friends relations to other players indeed, this is the key point of introducing our models of altruism. We will now show that there are AHGs that cannot be expressed by any of the above mentioned classes. While similar examples exist for all altruistic models, we now focus on the avg-based EQ extension:

Example 5.1. Consider a game with three players (N = {1, 2, 3}, so n = 3) where the network of friends is a path: 1 2 3. Recall that for any i N and A N i, we have

uavg EQ i (A) = avg F+ i (A) = X

a A (Fi {i})

n|A Fa| |A Ea|

|A (Fi {i})| .

Then uavg EQ 1 ({1, 2}) = 3+3

2 = 3 and uavg EQ 1 ({1, 2, 3}) = (3 1)+3 2

2 = 4. Consequently, {1, 2, 3} avg EQ 1 {1, 2}, but {1} avg EQ 1 {1, 3} because agent 3 is an enemy of 1 s, and {1, 2} avg EQ 1 {1} because agent 2 is a friend of 1 s.

In particular, the preferences considered in Example 5.1 cannot be expressed in additively separable hedonic games, fractional hedonic games, hedonic games with Bor Wpreferences, or FEN-hedonic games. However, all these classes can express strict preferences over coalitions of size two that only contain the considered agent and a single additional agent. This is not possible for altruistic hedonic preferences because of indiﬀerence between friends and enemies, respectively. (Comparing three coalitions of size two under altruistic hedonic preferences, there will always be an indiﬀerence.) Overall, neither are altruistic hedonic preferences more expressive than any of the other considered models nor the other way around.

5.2 Properties of Preference Extensions

Aiming at determining the axiomatic properties of our altruistic preference extensions, we now give a selection of properties of preference extensions that deduce preferences over coalitions from the friends-and-enemies encoding. These properties are inspired by properties from various related ﬁelds such as social choice theory and resource allocation, which also are concerned with preferences. Let N = {1, . . . , n} be a set of players and Fi and Ei the sets of player i s friends and enemies, respectively. Let G = (N, H) be the corresponding network of friends. Let G = (N , H ) be some network of friends that is isomorphic to G by the isomorphism ϕ : N N . Consider player i s preference relation i on N i and ϕ(i) s preference relation ϕ(i) on N ϕ(i) that were deduced from G and G by the same preference extension.

Altruistic Hedonic Games

We say i is reﬂexive if A i A for each coalition A N i; i is transitive if for any three coalitions A, B, C N i, A i B and B i C implies A i C; i is polynomial-time computable if for two given coalitions A, B N i, it can be decided in polynomial time whether or not A i B; and i is anonymous if renaming the players in N does not change the structure of i s preference, i.e., if for any two coalitions A, B N i, it holds that A i B if and only if {ϕ(a) | a A} ϕ(i) {ϕ(b) | b B}. Clearly, the ﬁrst three properties are necessary to have eﬃciently computable and rational preferences, and anonymity means that only the structure of the friendship network is important. We further deﬁne the following properties.

Weak Friend-Orientedness: Given any coalition A N i and a friend f Fi \ A, the coalition A {f} is acceptable for i.

Favoring Friends: If x Fi and y Ei then {x, i} i {y, i}.

Indiﬀerence between Friends: If x, y Fi then {x, i} i {y, i}.

Indiﬀerence between Enemies: If x, y Ei then {x, i} i {y, i}.

Note that these four properties hold for friend-oriented preferences, see the work of Alcantud and Arlegi (2012).4 The next property is inspired by the property citizens sovereignty from social choice theory, which says that only the voters shall decide on who has won an election, so for a voting rule to satisfy this property it is required that every candidate can be made a winner for suitably chosen voter preferences (see, e.g., Baumeister & Rothe, 2015).5

Similarly, we require that only the players shall decide on which coalitions turn out to be their most preferred ones, under a suitably chosen network of friends.

Sovereignty of Players: For a ﬁxed player i and each C N i, there exists a network of friends such that C ends up as i s most preferred coalition.

We now introduce two types of monotonicity. Type-I-monotonicity ensures that if i (weakly) prefers A over B, this should still be true after an enemy j of i s, who is contained in both coalitions and weakly prefers A to B friend-orientedly, turns into i s friend. Type II-monotonicity is similarly deﬁned but requires that j is only in A (hence has no opinion on B or its relation to A), but still i s preference of A over B should not be altered by j turning from an enemy of i s into i s friend.

Monotonicity: Let j = i be a player with j Ei and let A, B N i. Let further i be the preference relation resulting from i when j turns from being i s enemy into being i s friend (all else remaining equal). We call i

type-I-monotonic if it holds that (1) if A i B, j A B, and A F j B, then A i B, and (2) if A i B, j A B, and A F j B, then A i B.

4. Alcantud and Arlegi (2012) deﬁne so-called weighted GNB rankings (where objects are classiﬁed into three categories: good, neutral, and bad), which are a generalization of friend-oriented preferences in hedonic games. 5. This property is also known as non-imposition.

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

type-II-monotonic if it holds that (1) if A i B and j A \ B, then A i B, and (2) if A i B and j A \ B, then A i B.

The next property is local friend dependence. It says that an agent s preferences over some coalitions can change if the sets of this agent s friends friends change. These friends also have to be members of the coalition that is under consideration. Thus local friend dependence is a crucial property that characterizes the essence of the proposed altruistic preferences and distinguishes them from previous models, e.g., from additively separable (Aziz et al., 2013b) or friend-oriented preferences (Dimitrov et al., 2006).

Local Friend Dependence: The preference order i can depend on the sets of friends F1, . . . , Fn of some agents. Let A, B N i. We say that comparison (A, B) is

friend-dependent in i if A i B is true (or false) and can be made false (or true) by changing the set of friends of some players in N \ {i} (while not changing any relation to i);

locally friend-dependent in i if A i B is true (or false), can be made false (or true) by changing the set of friends of some players in (A B) Fi (while not changing any relation to i), and changing the set of friends of any of the other players in N \({i} (Fi (A B))) (while not changing any relation to any player in {i} (Fi (A B))) does not aﬀect the status of the comparison.

We say i is friend-dependent if there are A, B N i such that (A, B) is frienddependent in i.

We say i is locally friend-dependent if i is friend-dependent and every (A, B) that is friend-dependent in i is locally friend-dependent in i.

Finally, we turn to local unanimity: If two coalitions A and B contain the same friends of a player i, and if i and all these friends value A higher than B, then we want i to prefer A over B. This is a desirable property as it means that an unanimous opinion of agent i and her friends will always be reﬂected in i s preference.

Local Unanimity: Let A, B N i and A Fi = B Fi. We say that i is locally unanimous if va(A) > va(B) for each a (Fi {i}) A implies that A i B.

The above deﬁnition covers all cases where the same subset of friends is consulted who all have an unanimous opinion in terms of friend-oriented preferences; in particular, it covers the case where all friends are consulted: Fi A B.

5.3 Study of Desirable Properties

We now consider the desirable properties from Section 5.2. Table 2 summarizes our results for all three degrees of avg-based and min-based altruistic preferences. We start by showing some basic properties.

Proposition 5.2. Under all three degrees of avg-based and min-based altruistic preferences, the following properties are satisﬁed: reﬂexivity, transitivity, polynomial-time computability, as well as anonymity.

Altruistic Hedonic Games

Avg-based preferences Min-based preferences avg SF avg EQ avg AL min SF min EQ min AL

Reﬂexivity Transitivity Polynomial-time computability Anonymity Weak friend-orientedness Favoring friends Indiﬀerence between friends Indiﬀerence between enemies Sovereignty of players Type-I-monotonicity Type-II-monotonicity Local friend dependence 1 1 1 1 2 1

Local unanimity

1 If there are at least four agents and the considered agent has at least one friend. 2 If the considered agent has at least two friends.

Table 2: Properties satisﬁed ( ) or not ( ) by the altruistic preferences from Section 4.2

Proof. Reﬂexivity follows immediately from the deﬁnition. Transitivity follows from the fact that the relation is transitive for rational numbers. Furthermore, each value (as deﬁned in (2)) that an agent assigns to a coalition can obviously be computed in polynomial time. Hence, each summand in the friends average value (deﬁned in (5)) and each element in the friends minimum value (deﬁned in (6)) can be computed in polynomial time. The number of summands (and elements in the minimum) is bounded by the number n of players, which implies that both sums and minima can be computed in polynomial time, which in turn allows to determine the utilities for any two coalitions in polynomial time. Finally, by renaming the players, the numbers of friends and enemies of the players do not change. Therefore, the calculations of the utilities do not change either, leading to no change in the relation between two coalitions. K

We continue with the following lemma that will be very useful for the subsequent analysis.

Lemma 5.3. Under all three degrees of avg-based and min-based altruistic preferences, the following two statements hold:

1. A player i has a positive utility for a coalition C N i if and only if i has at least one friend in C.

2. If a player i has at least one friend, i s most preferred coalition contains at least one friend of i s.

Proof. For the ﬁrst statement, if i has no friends in C then i s utility for C is at most zero under all altruistic preferences because vi(C) 0, avg F i (C) = 0, and min F i (C) = 0. If i

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

has at least one friend in C then these friends also have at least one friend in C (namely, i). Hence, i and all friends of i s in C assign a positive value to C, i.e., vi(C) > 0, avg F i (C) > 0, and min F i (C) > 0, which implies a positive utility. The second statement follows directly from the ﬁrst one. K

Theorem 5.4. Under all three degrees of avg-based and min-based altruistic preferences, weak friend-orientedness, favoring friends, indiﬀerence between friends, indiﬀerence between enemies, sovereignty of players, and local unanimity are satisﬁed.

Proof. We show these properties for avg-based EQ preferences only. The proofs for the other ﬁve models of altruism work analogously and are therefore omitted.

Weak Friend-Orientedness: Let i N, A N i, and f Fi \ A. Since i has at least one friend in A {f}, it follows by Lemma 5.3.1 that i has a positive utility for A {f}. Hence, A {f} is acceptable for i.

Favoring Friends: Let i N, x Fi, and y Ei. This property holds because

uavg EQ i ({x, i}) = X

a {x,i} (Fi {i})

va({x, i}) |{x, i} (Fi {i})|

= vx({x, i}) + vi({x, i})

|{x, i} (Fi {i})| = n + n

= vi({y, i}) = X

b {y,i} (Fi {i})

vb({y, i}) |{y, i} (Fi {i})| = uavg EQ i ({y, i}).

Indiﬀerence between Friends: Let x, y Fi. As i s utility for both coalitions, {x, i} and {y, i}, is n, we have {x, i} avg EQ i {y, i}.

Indiﬀerence between Enemies: For x, y Ei, i s utility for {x, i} and {y, i} is 1, which also implies indiﬀerence.

Sovereignty of Players: Let i N and C N i. We construct the network of friends G such that for all pairs of players x, y C, x = y, there is an edge {x, y} in G, while there are no other edges in G. Then C is i s most preferred coalition.

Local Unanimity: Let A, B N i with A Fi = B Fi and let vj(A) > vj(B) for each j A (Fi {i}). Then A (Fi {i}) = B (Fi {i}). Hence, it is obvious that

uavg EQ i (A) = X

j A (Fi {i})

vj(A) |A (Fi {i})| > X

j B (Fi {i})

vj(B) |B (Fi {i})| = uavg EQ i (B).

Thus A avg EQ i B, showing local unanimity.

This completes the proof for avg-based EQ altruistic preferences; the proofs for the other altruistic preferences, as mentioned above, are very similar. K

Altruistic Hedonic Games

Turning to local friend dependence, we can show that this property holds for all three degrees of avg-based and min-based altruistic preferences except for some edge cases where there are not enough agents or no friends at all. In particular, if i has no friends, her altruistic preferences coincide with her friend-oriented preferences (3). Additionally, min EQ i coincides with the friend-oriented preference extension if i has only one friend. In these cases, the preferences are not friend-dependent.6 Before turning to Theorem 5.6, we state the following interesting lemma.

Lemma 5.5. Any avg-based or min-based altruistic preference is locally friend-dependent if and only if it is friend-dependent.

Proof. We consider some player i N and her altruistic preference i that was obtained under any of the three degrees of avg-based or min-based altruism. By deﬁnition, local friend-dependence implies friend-dependence. So, it remains to show that every pair (A, B) of coalitions that is friend-dependent under i is also locally friend-dependent under i. This holds because i s utilities for A and B only depend on the set of i s friends and the sets of friends of i s friends in A and B, respectively. In other words, i s utilities for A and B can only be changed by changing some Fa with a {i} (Fi (A B)). Hence, i is locally friend-dependent if and only if i is friend-dependent. K

By means of Lemma 5.5, we now show the following results.

Theorem 5.6. The preference i of agent i N is (locally) friend-dependent exactly if

1. in case = avg SF or = min SF, i has at least one friend and n 4;

2. in case = avg EQ, i has at least one friend and n 4 or i has exactly one friend and n = 3;

3. in case = min EQ, i has at least two friends (and thus n 3);

4. in case = avg AL or = min AL, i has at least one friend and n 3.

Proof. We show that i is friend-dependent, i.e., there exists a pair (A, B) of coalitions that is friend-dependent under i if and only if i has at least one (or two) friends and N is suﬃciently large. Due to Lemma 5.5, this also implies that i is locally friend-dependent in exactly these cases. We omit the cases of one, two, and three players as these few small examples can easily be veriﬁed and the results are as stated in the theorem. Only if: If i has no friends, then there are no friends whose sets of friends could be changed. So, there is obviously no pair of coalitions that is friend-dependent under any degree of altruism and, thus, i is not friend-dependent. Moreover, we consider min EQ i for the case that i has exactly one friend. Then vi(C) is the minimum valuation in umin EQ i (C) for any coalition C because i has at most one friend in C while this friend might have more friends in C. Hence, min EQ i coincides with F i and is not friend-dependent.

6. Note that friend dependence is a crucial property that distinguishes our altruistic preferences from previous models, e.g., from additively separable (Aziz et al., 2013b) or friend-oriented preferences (Dimitrov et al., 2006).

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

If: First, for {avg SF, avg EQ, avg AL}, we show that there is a pair (A, B) N i N i

that is friend-dependent under i if n 4 and |Fi| > 0.

Case 1: There are at least two agents e1, e2 N \{i} that are i s enemies (and at least one friend f Fi due to |Fi| > 0). It holds that vi({i, f, e1}) = vi({i, f, e2}). Hence, i s utility depends on avg F i ({i, f, e1}) and avg F i ({i, f, e2}). If avg F i ({i, f, e1}) = avg F i ({i, f, e2}), we change Ff such that avg F i ({i, f, e1}) = avg F i ({i, f, e2}), and vice versa. (This is possible by adding e1 to Ff or deleting e1 from Ff.) This changes i s preference over {i, f, e1} and {i, f, e2} under all three degrees of altruism. Hence, ({i, f, e1}, {i, f, e2}) is friend-dependent.

Case 2: i is friends with all but one agent e1 N \ {i} and thus has at least two friends f1, f2 Fi (due to n 4). Then ({i, f1, e}, {i, f2, e}) is friend-dependent (by adding e to Ff1 or deleting e from Ff1).

Case 3: If i is friends with all (at least n 1 3) agents f1, . . . , fn 1 N \ {i}, then ({i, f1, f2}, {i, f1, f3}) is friend-dependent (by adding f2 to Ff1 or deleting f2 from Ff1).

For {min SF, min AL}, the proof that i is friend-dependent if n 4 and |Fi| > 0 is very similar to the above argumentation and is therefore omitted.

Finally, we show that min EQ i is friend-dependent if |Fi| 2. Assuming |Fi| 2, there are f1, f2 Fi. If f1 and f2 are friends of each other, then {i, f1, f2} min EQ i {i, f1}. Otherwise, {i, f1} min EQ i {i, f1, f2}. Hence, we can change min EQ i by changing the friendship relation between f1 and f2, which means that min EQ i is friend-dependent. K

We now turn to our two types of monotonicity. Interestingly, both types of monotonicity hold for avg-based SF preferences and type-II-monotonicity also holds for min-based SF preferences, but both types of monotonicity are violated for all other altruistic preferences.

Theorem 5.7. Avg-based SF preferences are type-I-monotonic and type-II-monotonic. Minbased SF preferences are type-II-monotonic.

Proof. We start with avg-based SF preferences. Let G = (N, H) be a network of friends and let i N, A, B N i, and j Ei. We denote with G = (N, H {{i, j}}) the network of friends resulting from G when j turns from being i s enemy into being i s friend (all else being equal). Then, for any player a N and coalition C N a, we denote a s value for C in G with v a(C), her SF preference in G with avg SF a and her new friend and enemy sets with F a and E a. Hence, we have F i = Fi {j}, E i = Ei \ {j}, F j = Fj {i}, and E j = Ej \ {i}. Further, v i, v j, and avg SF i diﬀer from vi, vj, and avg SF i . The friends, enemies, and values of all other players stay the same, i.e., F a = Fa, E a = Ea, and v a = va for all a N \ {i, j}.

Type-I-Monotonicity: Let j A B and A F j B, i.e., vj(A) vj(B). It then holds that v i(A) = n|A F i| |A E i| = n|A Fi|+n |A Ei|+1 = vi(A)+n+1. Equivalently, v i(B) = vi(B) + n + 1, v j(A) = vj(A) + n + 1, and v j(B) = vj(B) + n + 1.

Altruistic Hedonic Games

Furthermore,

avg F i (A) = X

v a(A) |A F i| = X

a (A Fi) {j}

v a(A) |(A Fi) {j}|

va(A) |A Fi| + 1 + v j(A) |A Fi| + 1

= |A Fi| |A Fi| + 1 avg F i (A) + vj(A) + n + 1

|A Fi| + 1 and (13)

avg F i (B) = |B Fi| |B Fi| + 1 avg F i (B) + vj(B) + n + 1

|B Fi| + 1 . (14)

If A avg SF i B then either (i) vi(A) = vi(B) and avg F i (A) > avg F i (B), or (ii) vi(A) > vi(B). In case (i), vi(A) = vi(B) implies v i(A) = v i(B) and |A Fi| = |B Fi|. Applying |A Fi| = |B Fi|, avg F i (A) > avg F i (B), and vj(A) vj(B) to (13) and (14), we get avg F i (A) > avg F i (B). Then, v i(A) = v i(B) and avg F i (A) > avg F i (B) implies A avg SF i B. In case (ii), vi(A) > vi(B) implies v i(A) > v i(B). Hence, A avg SF i B. If A avg SF i B then vi(A) = vi(B) and avg F i (A) = avg F i (B). vi(A) = vi(B) implies v i(A) = v i(B) and |A Fi| = |B Fi|. Applying |A Fi| = |B Fi|, avg F i (A) = avg F i (B), and vj(A) vj(B) to (13) and (14), we get avg F i (A) avg F i (B). Hence, v i(A) = v i(B) and avg F i (A) avg F i (B) implies A avg SF i B.

Type-II-Monotonicity: Let j A \ B. It follows that v i(A) = vi(A) + n + 1 and v i(B) = vi(B). If A avg SF i B then vi(A) vi(B). Hence, v i(A) = vi(A) + n + 1 vi(B) + n + 1 > vi(B) = v i(B). This implies A avg SF i B. If A avg SF i B then vi(A) = vi(B). Again, v i(A) = vi(A) + n + 1 = vi(B) + n + 1 > vi(B) = v i(B). Hence, A avg SF i B. This completes the proof for avg-based SF preferences. The proof that min-based SF preferences are type-II-monotonic is identical to the proof that avg-based SF preferences are type-II-monotonic. K

Theorem 5.8. Min-based SF preferences are not type-I-monotonic. Avg-based and minbased EQ and AL preferences are neither type-I-monotonic nor type-II-monotonic.

Proof. As a counterexample for all min-based altruistic preferences, consider the game G1 with the network of friends in Figure 6a. To see that none of the three degrees of minbased altruistic preferences is type-I-monotonic, consider players i = 1 and j = 2 / F1 and coalitions A = {1, 2, 3, 4} and B = {1, 2, 5, 6}. Then v1(A) = v1(B) = 11, v2(A) = v2(B) = 3, v3(A) = v4(A) = 11, and v5(B) = v6(B) = 4. Hence, min F 1 (A) = 11 and min F 1 (B) = 4. It follows that A min SF 1 B, A min EQ 1 B, and A min AL 1 B. Making j = 2 a friend of i = 1, we get the game G 1 with the network of friends shown in Figure 6f. For this network, we have v1(A) = v1(B) = 18, v2(A) = v2(B) = 4, v3(A) = v4(A) = 11, and v5(B) = v6(B) = 4. Then min F 1 (A) = 4 = min F 1 (B). Hence,

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

(a) Network of G1

(b) Network of G2

(c) Network of G3

(d) Network of G4

(e) Network of G5

(f) Network of G 1

(g) Network of G 2

(h) Network of G 3

(i) Network of G 4

(j) Network of G 5

Figure 6: Networks of friends in the proof of Theorem 5.8

Type Games i j Violation

avg AL I G3 (Fig. 6c), 1 2 For A = {1, 2, 7, 8, 9, 10} and B = {1, . . . , 6}: G 3 (Fig. 6h) A avg AL 1 B, 2 A B, v2(A) v2(B) in G3

but B avg AL 1 A in G 3 avg EQ II G4 (Fig. 6d), 1 6 For A = {1, 2, 3, 4, 5, 6} and B = {1, 5, 7, 8, 9, 10}: G 4 (Fig. 6i) A avg EQ 1 B, 6 A \ B in G4 but B avg EQ 1 A in G 4 avg AL II G5 (Fig. 6e), 1 4 For A = {1, 2, 3, 4} and B = {1, 5, 6, 7}: G 5 (Fig. 6j) A avg AL 1 B, 4 A \ B in G5 but B avg AL 1 A in G 5

Table 3: Violation of type-Iand type-II-monotonicity in the proof of Theorem 5.8

A min SF 1 B, A min EQ 1 B, and A min AL 1 B, which contradicts type-I-monotonicity for the three degrees of min-based altruistic preferences. To see that min EQ and min AL violate type-II-monotonicity, consider the same game G1 from Figure 6a and again players i = 1 and j = 2 / F1, but now coalitions A = {1, 2, 3, 4} and B = {1, 5, 6}. Then A min EQ 1 B and A min AL 1 B. However, considering G 1, we get B min EQ 1 A and B min AL 1 A, violating type-II-monotonicity for min-based EQ and AL preferences. We now turn to avg-based EQ preferences and type-I-monotonicity. Let G2 be a game with the network of friends shown in Figure 6b. We consider players i = 1, j = 2 / F1, and coalitions A = {1, 2, 3, 4, 5} and B = {1, 2, 6, 7, 8}. Then A avg EQ 1 B, 2 A B, and v2(A) v2(B). Making 2 a friend of 1 leads to the new game G 2 with the network of friends shown in Figure 6g. However, in G 2 we have B avg EQ 1 A, violating type-I-monotonicity for avg-based EQ preferences. With analogous arguments, avg-based EQ preferences are not type-II-monotonic and avg-based AL preferences are neither type-Inor type-II-monotonic, as shown in Table 3 that lists all counterexamples showing the violations of the respective properties. K

Altruistic Hedonic Games

Note that the above results of Theorems 5.7 and 5.8 are a desirable outcome since this behavior exactly captures the intuition behind the deﬁnitions of the diﬀerent altruistic preferences. In particular, if a player i gets an additional friend who is really unsatisﬁed in i s coalition then this should diminish player i s utility under EQ and AL preferences. Also, under min-based SF preferences, type-I-monotonicity does not have to be satisﬁed as an additional friend that is added to two coalitions might impose the same upper bound on the friends minimum valuation for both coalitions. In the case of adding an additional friend to only one of the two coalitions (as in the case of type-II-monotonicity), however, both models of SF preferences ensure that the additional friend will increase i s utility. In addition to the axiomatic properties from Section 5.2, one could consider notions of independence (for a characterization of friend-oriented preferences using an independence axiom, see, e.g., Alcantud & Arlegi, 2012). Classic independence axioms say that a relation between two coalitions, A and B, continues to hold even if a new (and the same) player is introduced to both coalitions. However, independence axioms of this type are not desirable in our model because the new player can be valued very diﬀerently in both coalitions. This would be the case, for example, if the new player were an enemy to most of i s friends in coalition A but were a friend to most of i s friends in coalition B. Similarly, Band W-preferences (Cechlárová & Romero-Medina, 2001) are natural extensions from singleton encodings that are not independent.

6. Stability in Altruistic Hedonic Games

In this section, we study stability in AHGs. We mostly concentrate on the cases of general AHGs and SF AHGs but also provide some results for EQ and AL AHGs. We study the common stability concepts that were deﬁned in Section 3.2. Questions of interest are how hard it is to verify whether a given coalition structure satisﬁes a certain concept in a given AHG and whether stable coalition structures for certain concepts always exist. If, for some concept, such coalition structures are not guaranteed to exist, we are also interested in the computational complexity of deciding whether or not such coalition structures exist in a given hedonic game. Formally, in the veriﬁcation problem for a stability notion σ, we are given an AHG (N, ) and a coalition structure Γ CN, and we ask whether Γ satisﬁes σ. In the existence problem for σ, we are given an AHG (N, ), and we ask whether there exists a coalition structure Γ CN that satisﬁes σ. Note that whenever the veriﬁcation problem is in P, the existence problem is in NP, as we can then guess and verify a stable coalition structure in nondeterministic polynomial time. Our complexity results for these problems are summarized in Table 4. Starting our analysis with individual rationality, note that the ﬁrst statement of Lemma 5.3 provides the following characterization.

Corollary 6.1. For any AHG (N, ), a coalition structure Γ CN is individually rational if and only if for each player i N, it holds that i has at least one friend in Γ(i) or i is the only player in Γ(i).

By Corollary 6.1, individual rationality veriﬁcation is in P and existence is trivial because Γ = {{1}, . . . , {n}} is always individually rational. The next useful lemma only considers SF preferences.

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

Verification Existence

general sf general sf

ind. rationality in P in P YES YES

Nash stability in P in P YES YES ind. stability in P in P YES YES contr. ind. stability in P in P YES YES

core stability co NPcomplete co NPcomplete 1

in Σp 2 YES

str. core stability co NPcomplete co NPcomplete 1

in Σp 2 YES

perfectness in co NP in P in Σp 2

1 Even for avg-based SF and min-based SF AHGs, i.e., if all agents have avg-based SF preferences or all agents have min-based SF preferences. 2 In co NP for avg-based EQ and avg-based AL AHGs.

Table 4: Overview of complexity results of stability veriﬁcation and existence problems in altruistic hedonic games. The columns general give the results for general AHGs (with any mixture of avg-based and min-based SF, EQ, and AL preferences). The columns SF give the results for SF AHGs (with any mixture of avg-based and min-based SF preferences). A YES entry for one of the existence problems indicates that there always exists a coalition structure that fulﬁlls the considered stability concept in the considered class of AHGs. A gray entry indicates that only trivial upper bounds are known.

Lemma 6.2. Given avg-based or min-based SF preferences and coalitions C, D N i, where D is a clique of size k (in the underlying network of friends), it holds that

if i prefers C to D then i has at least k friends in C and

if i is indiﬀerent between C and D then C is a clique of size k.

Proof. Let C, D N i such that D is a clique of size k. Then i and all her friends in D each have k 1 friends in D, i.e., vi(D) = n(k 1), avg F i (D) = n(k 1), and min F i (D) = n(k 1). First, assume that i prefers C to D. Then, either (a) vi(C) > vi(D) or (b) vi(C) = vi(D) and avg F i (C) > avg F i (D) (or min F i (C) > min F i (D)). If (a) holds, then i obviously has at least k friends in C. If (b) holds, then vi(C) = vi(D) = n(k 1). Therefore, C consists of i and k 1 of i s friends, and no further players. However, this is a contradiction because, for this coalition, it is impossible that avg F i (C) > avg F i (D) = n(k 1) (or min F i (C) > min F i (D) = n(k 1)). Hence, case (a) has to be true. Second, assume that i is indiﬀerent between C and D. Then, again, vi(C) = n(k 1) implies that C consists of i and k 1 of i s friends. Since avg F i (C) = n(k 1) (or min F i (C) = n(k 1)), it is further implied that all of i s friends in C have k 1 friends. Hence, C is a clique of size k. K

Altruistic Hedonic Games

We continue with Nash stability and (contractually) individual stability and get general results for AHGs with any mixture of altruistic preferences. First, as for any reasonable class of hedonic games, we can verify these concepts in polynomial time.

Proposition 6.3. For any AHG (N, ), it can be tested in polynomial time whether a given coalition structure is Nash stable, individually stable, or contractually individually stable.

Proof. Let Γ be a coalition structure. For Nash stability, we need to check if for each player i N and for each coalition C Γ { }, i prefers Γ(i) to being added to C. For n players, there are at most n + 1 such coalitions, and the preference relation can be veriﬁed in polynomial time by Proposition 5.2. Similar arguments apply to individual and contractually individual stability. K

The existence problem is trivial for Nash stability and (contractually) individual stability because there always exist stable coalition structures.

Theorem 6.4. For any AHG (N, ), there exists a Nash stable, individually stable, and contractually individually stable coalition structure.

Proof. Let C = {i N | Fi = } be the set of players without friends and rename its members by C = {1, . . . , k}. The coalition structure {{1}, . . . , {k}, N \ C} is Nash stable: Each i C has a utility of 0 when being alone. As i has no friends, by Lemma 5.3.1 this is the highest utility i can get. Hence, i does not want to move to another coalition. Every j N \ C has at least one friend in N \ C, which implies uj(N \ C) > 0 by Lemma 5.3.1. Hence, j would rather like to stay in N \ C than to move to any of her enemies 1, . . . , k or to the empty coalition. Nash stability implies individual stability, which in turn implies contractually individual stability (see, e.g., Figure 2 on page 138 or Aziz & Savani, 2016). K

We now turn to core stability. Theorem 6.5 is inspired by a result of Dimitrov et al. (2006).

Theorem 6.5. For any SF AHG (N, ), there always exists a strictly core stable (and thus core stable) coalition structure.

Proof. We show that the coalition structure Γ consisting of the connected components of the underlying network of friends is strictly core stable (and thus core stable). We know that the players from diﬀerent coalitions in Γ are not friends: Each i N has all of her friends in Γ(i). For the sake of contradiction, assume that Γ is not strictly core stable, i.e., that there is a coalition C = that weakly blocks Γ. We then have C SF i Γ(i) for all i C and C SF j Γ(j) for some j C. Consider any player i C. Since i weakly prefers C to Γ(i), there have to be at least as many friends of i s in C as in Γ(i). Since Γ(i) contains all of i s friends, C also has to contain all friends of i s. Then all these friends of i s also have all their friends in C for the same reason (and so on). Consequently, C contains all players from the connected component Γ(i), i.e., Γ(i) C. Since C weakly blocks Γ, C cannot be equal to Γ(i) and so contains some player k / Γ(i). However, this is a contradiction because

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

3 4 . . . n

(a) Example 6.6

1 2 3 4 5 6

AL SF AL AL SF AL

(b) Example 6.7

(c) Example 6.8

Figure 7: Three networks of friends for Examples 6.6, 6.7, and 6.8

k is an enemy of i s and i would prefer Γ(i) to C if C contained the same number of friends but more enemies than Γ(i). K

Note that the proof of Theorem 6.5 showing that the coalition structure consisting of the connected components in the underlying network of friends is (strictly) core stable for SF preferences does not carry over to the other degrees of altruism. Indeed, the following example shows that this coalition structure may not be core stable in these cases.

Example 6.6. Consider an AHG (N, ) with n 8 agents and the network of friends in Figure 7a. Furthermore, consider the coalition structure Γ = {N} consisting of the grand coalition, i.e., of the only connected component in this network of friends. It holds that C = {1, 2, 3} blocks Γ under avg-based AL preferences: avg F i (C) = 2n for i {1, 2, 3} but avg F 1 (N) = v2(C)+v3(C)

2 = (n+3)+(2n+4)

2 = 1.5n + 3.5, avg F 2 (N) = 1.5n + 3.5, and avg F 3 (N) = v1(C)+v2(C)

2 = (n+3)+(n+3)

2 = n + 3. Hence, 1, 2, and 3 prefer C to N for n 8. Similar calculations show that C blocks Γ under avg-based and min-based EQ and under min-based AL preferences.

Note that for general AHGs with mixed preferences even a short path of only six agents can have a blocking coalition.

Example 6.7. Consider an AHG (N, ) with six agents and the network of friends in Figure 7b. The players have diﬀerent altruistic preferences: Players 2 and 5 have SF preferences while players 1, 3, 4, and 6 have AL preferences. (In this example, it does not matter whether the preferences are avg-based or min-based.) First, consider the coalition structure Γ = {N} consisting of the grand coalition. It holds that C = {1, 2, 3} blocks Γ: 1 prefers C to N because avg F 1 (C) = min F 1 (C) = v2(C) = 2n > 2n 3 = v2(N) = avg F 1 (N) = min F 1 (N); 2 prefers C to N because v2(C) = 2n > 2n 3 = v2(N); and 3 prefers C to N because avg F 3 (C) = min F 3 (C) = v2(C) = 2n > 2n 3 = avg F 3 (N) = min F 3 (N). Further, consider coalition structure = {{1, 2, 3}, {4, 5, 6}} that results from the core deviation of C. It then holds that every agent is in one of her most preferred coalitions. Thus is perfect and therefore also strictly core stable (again, see Figure 2 on page 138 or Aziz & Savani, 2016).

Example 6.7 shows that the coalition structure consisting of the connected components is not always core stable while there may exist another coalition structure that is even strictly core stable. However, the next example shows that a strictly core stable coalition structure does not need to exist in general. Example 6.8 shows this for the case of min-based EQ and AL preferences.

Altruistic Hedonic Games

Example 6.8. Consider the network of friends in Figure 7c. We show that there does not exist a strictly core stable coalition structure under min-based EQ preferences. A direct calculation gives the following: Under min-based EQ preferences,

1. the unique most preferred coalition of players 1 and 2 is A = {1, 2, 3},

2. the unique most preferred coalition of players 4 and 5 is B = {3, 4, 5}, and

3. player 3 has exactly two most preferred coalitions: A and B.

With these observations, we can directly conclude the following: If a given coalition structure Γ does not contain A, the coalition A weakly blocks Γ. So any strictly core stable coalition structure has to contain A. However, the same holds for B, and since A and B are not disjoint, they cannot both be contained in the same coalition structure. Thus there does not exist a strictly core stable coalition structure under min-based EQ preferences. Similar arguments work for the same example and min-based AL preferences.

Turning to the veriﬁcation problem of (strict) core stability, we have the following results.

Theorem 6.9. For general AHGs, (strict) core stability veriﬁcation is in co NP. For avgbased SF AHGs and min-based SF AHGs, (strict) core stability veriﬁcation is even co NPcomplete.

Proof. We start with showing the membership of (strict) core stability veriﬁcation in co NP for general AHGs. Let G be a network of friends on agents N and Γ a coalition structure. Γ is not (strictly) core stable if there is a coalition C N that (weakly) blocks Γ. Hence, we nondeterministically guess a coalition C N and check whether C blocks Γ. This can be done in polynomial time since we only need to check a linear number of preference relations, which in turn can be done in polynomial time (in the number of agents) for all models (see Proposition 5.2). To show co NP-hardness of (strict) core stability veriﬁcation under avg-based and minbased SF AHGs, we make use of a restricted variant of the NP-complete problem Exact Cover by 3-Sets (Garey, Johnson, & Stockmeyer, 1976); it was shown by Gonzalez (1985) that this problem remains NP-complete even when each element of the set occurs in exactly three of the 3-element subsets:

Restricted Exact Cover by 3-Sets (RX3C)

Given: An integer k 2, a set B = {1, . . . , 3k} and a collection S = {S1, . . . , S3k} of 3-element subsets of B (Si B and |Si| = 3 for 1 i 3k), where each element of B occurs in exactly three sets in S . Question: Does there exist an exact cover of B in S , i.e., a subset S S of size k such that every element of B occurs in exactly one set in S ?

We provide a polynomial-time many-one reduction from RX3C to the complements of our problems. Let (B, S ) be an instance of RX3C, consisting of a set B = {1, . . . , 3k} and a collection S = {S1, . . . , S3k} of 3-element subsets of B. We may assume, without loss of generality, that k > 5. From (B, S ) we construct the following AHG. The set of players is given by

N = {βb | b B} {ζS | S S } {αS,1, αS,2, αS,3 | S S } {δS,1, . . . , δS,4k 3 | S S }.

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

αS1,1 αS1,2 αS1,3

δS1,1 ... δS1,4k 3

αS3k,1 αS3k,2 αS3k,3

δS3k,1 ... δS3k,4k 3

Figure 8: Network of friends in the proof of Theorem 6.9

Deﬁne the sets

Beta = {βb | b B},

Zeta = {ζS | S S }, and

QS = {αS,1, αS,2, αS,3, δS,1, . . . , δS,4k 3} for each S S .

The network of friends is given in Figure 8, where a dashed rectangle around a group of players means that all these players are friends of each other:

All players in Beta are friends of each other.

For every S S , all players in QS are friends of each other.

For every S S , ζS is friends with αS,1, αS,2, αS,3, and the three βb with b S.

Consider the coalition structure Γ = {Beta} {{ζS} QS | S S }. We claim that S contains an exact cover for B if and only if Γ is not (strictly) core stable under the avg-based SF model, which in turn is true if and only if Γ is not (strictly) core stable under the min-based SF model. We start by showing the equivalence for the avg-based SF model (and for both core stability and strict core stability). Only if: Assume that there is an exact cover S S , |S | = k, for B. Consider C = Beta {ζS | S S }. Then C blocks Γ (i.e., C avg SF i Γ(i) for all i C) because

every βb Beta has 3k friends in C and only 3k 1 friends in Γ(βb) = Beta and

every ζS, S S , has 3 friends and 4k 4 enemies in C and 3 friends and 4k 3 enemies in Γ(ζS) = {ζS} QS.

Hence, Γ is not core stable (and thus not strictly core stable) under the avg-based SF model. If: Assume that Γ is not strictly core stable under the avg-based SF model. Then there is a coalition C N that weakly blocks Γ, i.e., C avg SF i Γ(i) for all i C and C avg SF j Γ(j) for some j C. First observe that in Γ every αS,j for S S and 1 j 3 is together with all her friends and none of her enemies. Hence, Γ(αS,j) is already αS,j s

Altruistic Hedonic Games

unique most preferred coalition, so there is no other coalition that αS,j would like to deviate to. Thus, for all S S and 1 j 3, we have αS,j / C. However, this implies that also no δS,l with S S and 1 l 4k 3 is in C because δS,l cannot weakly prefer C to Γ(δS,l) if C contains no α-player. Hence, we have shown that C Beta Zeta. Deﬁne #β = |Beta C| and #ζ = |Zeta C| as the numbers of, respectively, β-players and ζ-players in C. We will show that #β = 3k and #ζ = k. It is easy to see that there has to be at least one β-player in C. Consider some βb C. Since βb weakly prefers C to Γ(βb) = Beta, which is a clique of size 3k, and since βb is not contained in any other clique of size 3k, by Lemma 6.2 βb has at least 3k friends in C. Since βb has three ζ-friends in total, at least 3k 3 of βb s friends in C are β-players. Taking βb herself into account, we have #β 3k 2. Since these 3k 2 β-players have at least 3k friends in C, they all need to have at least one ζ-player as a friend in C. Therefore, #ζ k. Consider some ζS C. Since ζS has three friends and 4k 3 enemies in Γ(ζS), at most three friends in C, and she weakly prefers C to Γ(ζS), ζS has exactly three friends (three β-players) and at most 4k 3 enemies in C. Hence, C contains at most 4k 3+3+1 = 4k+1 players and |C| = #β + #ζ 4k + 1. For a contradiction, assume that #β = 3k 2. Then each of these β-players has only 3k 3 β-friends in C and additionally needs at least 3 ζ-friends in C. Since each β-player has exactly three ζ-friends and vice versa, we then have at least (3k 2) 3 = 9k 6 edges between the βand ζ-players in C. Then there are at least 3k 2 ζ-players in C. Thus #β + #ζ (3k 2) + (3k 2) = 6k 4, which is a contradiction (for k > 2) to #β + #ζ 4k + 1. Analogously, we get a contradiction when assuming that #β = 3k 1: In this case, each of the β-players in C has 3k 2 β-friends in C and additionally needs at least 2 ζ-friends in C. It follows that there are at least 2(3k 1) = 6k 2 edges between the βand ζ-players in C. Then there are at least 2k ζ-players in C. Thus #β + #ζ (3k 1) + (2k) = 5k 1, which is a contradiction (for k > 2) to #β + #ζ 4k + 1. Consequently, #β = 3k. So far, we have #β = 3k, #ζ k, and #β + #ζ 4k + 1. Hence, #ζ = k or #ζ = k + 1. For the sake of contradiction, assume that #ζ = k + 1. First, recall that each of these ζ-players has three β-friends in C. Then there are exactly (k + 1)3 = 3k + 3 edges between the β-players and the ζ-players in C. Since every β-player has at least one ζ-friend in C, every β-player has at least one edge to a ζ-player in C. Hence, there are at least 3k 3 β-players who have exactly one edge to a ζ-player in C and at most three β-players who have more than one edge to a ζ-player in C. Consider a ζS C who is friends with three βplayers who have only one ζ-friend in C. (There has to be such a ζ-player because otherwise there would be k + 1 ζ-players with a β-friend who has two ζ-friends. However, at most six ζ-players can be friends with one of these β-players. And 6 < k + 1 for k > 5.) Since ζS weakly prefers C to Γ(ζS) and has exactly 3 friends and 4k 3 enemies in C, it holds that avg F ζS(C) avg F ζS(Γ(ζS)). In C, ζS has three β-friends who all have the same valuation: avg F ζS(C) = n (3k) k. In Γ(ζS), ζS has three α-friends who all have the same valuation: avg F ζS(Γ(ζS)) = n (4k). Hence, avg F ζS(C) < avg F ζS(Γ(ζS)), which is a contradiction. Hence, #ζ = k. Finally, since every of the 3k β-players in C has one of the k ζ-players in C as a friend, it holds that {S | ζS C} is an exact cover for B.

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

This completes the proof for co NP-hardness of (strict) core stability veriﬁcation under the avg-based SF model. To show co NP-hardness of (strict) core stability veriﬁcation under min-based SF AHGs, we can use the exact same reduction and arguments as before. Only in the very end of the proof, we once consider the minimum over the friends valuations instead of the average. However, since in both coalitions the valuations are the same for all friends, the minimum and the average lead to the same result in this case. K

From Theorem 6.9 we immediately get the following corollary.

Corollary 6.10. For general AHGs, (strict) core stability veriﬁcation is co NP-complete.

We now turn to perfectness and establish the following characterization under SF preferences.

Proposition 6.11. For any SF AHG, a coalition structure is perfect if and only if it consists of the connected components of the underlying network of friends and all these components are cliques.

Proof. Only if: Assume that the coalition structure Γ CN is perfect. It then holds for every agent i N that she weakly prefers Γ(i) to every coalition C N i. It follows that every agent i N is in her most preferred coalition, where she is together with all her friends and none of her enemies. This implies that each coalition in Γ is a connected component and a clique. If: This implication is obvious. K

From Proposition 6.11 we get the following characterization of perfect coalition structures.

Corollary 6.12. For any SF AHG, there exists a perfect coalition structure if and only if all connected components of the underlying network of friends are cliques.

By Proposition 6.11 and Corollary 6.12, perfectness veriﬁcation and existence are in P for SF AHGs. We now turn to avg-based EQ and AL preferences. The next lemma will be used in the proof of Proposition 6.14 and says that if player j has a friend k in coalition C and k has another friend ℓ/ C who is not j s friend, then j prefers C {ℓ} to C under avg-based EQ and AL preferences. Hence, a coalition structure that contains C is not perfect.

Lemma 6.13. Let C N, k, j C, and ℓ N \ C with j Fk, k Fℓ, and j / Fℓ. Then C {ℓ} avg EQ j C and C {ℓ} avg AL j C.

Proof. Let C N, k, j C, and ℓ N \ C with j Fk, k Fℓ, and j / Fℓ. When ℓ joins the coalition C, k s valuation increases by n while j s valuation and the valuation of at most n 3 of j s friends (|(C Fj) \ {k}| n 3) decreases by one. Since the number of j s friends is the same in C {ℓ} and C, this means that uavg EQ j (C {ℓ}) > uavg EQ j (C)

and uavg AL j (C {ℓ}) > uavg AL j (C). Thus C {ℓ} avg EQ j C and C {ℓ} avg AL j C. K

The next proposition shows that whenever a perfect coalition structure exists in an avg-based EQ AHG or an avg-based AL AHG, it is unique and consists of the connected components of the underlying network of friends. This in particular means that every agent is together with all her friends.

Altruistic Hedonic Games

Proposition 6.14. Whenever a perfect coalition structure exists under avg-based EQ or AL preferences, it is unique and consists of the connected components of the underlying network of friends.

Proof. We will concentrate on the proof for EQ. The proof for AL is very similar. Let C be a coalition in a perfect coalition structure. Then C is the most preferred coalition of every player in C. First, for a contradiction, suppose C were not connected. Then, for any player i C, there is a player k C that is an enemy of i s and of all of i s friends in C. Hence, removing k from C increases the valuations of all players in (C Fi) {i} and thus increases i s utility, which is a contradiction to C being i s most preferred coalition. Second, observe that C contains an entire connected component: Suppose C is a proper subset of a connected component. Then there exist two players k C and ℓ/ C that are friends of each other. By Lemma 5.3.2, there exists another friend j Fk C. We distinguish the following cases which all lead to contradictions:

Case 1: There exists a friend j Fk C with ℓ/ Fj. Then, by Lemma 6.13, this is a contradiction to C being j s most preferred coalition because C {ℓ} avg EQ j C.

Case 2: For each j Fk C, it holds that ℓ Fj (and j Fℓby symmetry).

Case 2.1: There exists some x C \ Fk with ℓ/ Fx.

Case 2.1.1: x Ej for all j Fk C. Then C \ {x} avg EQ k C, which is a contradiction to C being k s most preferred coalition.

Case 2.1.2: There is a j Fk C with x Fj. Then C {ℓ} avg EQ x C by Lemma 6.13, which again is a contradiction.

Case 2.2: For each x C \ Fk, ℓ Fx. This implies that all players in C are ℓ s friends and vℓ(C {ℓ}) = n |C|. Thus, comparing coalitions C {ℓ} and C from k s point of view and letting λ denote |Fk C|, we obtain:

uavg EQ k (C {ℓ}) uavg EQ k (C)

= vk(C {ℓ}) + P j Fk C vj(C {ℓ}) + vℓ(C {ℓ})

1 + λ + 1 vk(C) + P j Fk C vj(C)

= 1 (2 + λ)(1 + λ)

(1 + λ)vk(C {ℓ}) (2 + λ)vk(C) + (1 + λ) X

j Fk C vj(C {ℓ})

j Fk C vj(C) + (1 + λ)vℓ(C {ℓ})

(1 + λ)vk(C {ℓ}) (2 + λ)vk(C) = n + |Ek C| and

j Fk C vj(C {ℓ}) (2 + λ) X

j Fk C vj(C) λ(1 + λ)n λ |C| n,

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

uavg EQ k (C {ℓ}) uavg EQ k (C) n + |Ek C| + λ(1 + λ)n λ |C| n + (1 + λ)(n |C|)

(2 + λ)(1 + λ)

= n + |Ek C| + λ(1 + λ)n + n |C|

(2 + λ)(1 + λ) > 0.

Therefore, C {ℓ} avg EQ k C, which again is a contradiction.

Since all cases lead to a contradiction, C has to be an entire connected component. K

Note that by Proposition 6.14, perfectness existence is in co NP under avg-based EQ and AL preferences: There exists a perfect coalition structure for a given game if and only if the coalition structure Γ that consists of the connected components of the network of friends is perfect. Hence, to show that there is no perfect coalition structure, we nondeterministically guess a player i N and a coalition C N i and check whether C avg EQ i Γ(i) (or C avg AL i Γ(i)) in polynomial time.

Corollary 6.15. In avg-based EQ AHGs and avg-based AL AHGs, perfectness existence is in co NP.

Under avg-based EQ and AL preferences, we further have the following restriction on perfect coalition structures.

Proposition 6.16. If there exists a perfect coalition structure for an avg-based EQ or avgbased AL AHG, all connected components have a diameter of at most two.

Proof. Assume that there is a coalition C in Γ that has a diameter greater than 2. Then there are agents i, j C with a distance greater than 2, i.e., j is an enemy of i s and all of i s friends. Hence, i and of all her friends have a higher valuation for C \ {j} than for C. It follows that i prefers C \ {j} to C under avg-based EQ and AL preferences. Consequently, Γ is not perfect. K

Interestingly, however, there also exist networks with a diameter of at most two that do not allow a perfect coalition structure, e.g., stars (i.e., one central vertex connected to a number of leaves).

Proposition 6.17. Under avg-based EQ preferences, trees with at least four vertices do not allow a perfect coalition structure. Under avg-based AL preferences, trees with at least three vertices do not allow a perfect coalition structure.

Proof. Trees with a diameter of more than two do not allow a perfect coalition structure by Proposition 6.16. Trees with a diameter of two are stars. Let i be the central player and j a leaf. It holds that N \ {j} avg EQ i N (and N \ {j} avg AL i N) such that {N} is not perfect, which in turn implies that there cannot be a perfect coalition structure by Proposition 6.14. K

Finally, turning to general AHGs, it is interesting to see that Proposition 6.14 does not extend to the general case. As we have seen in Example 6.7, general AHGs allow for perfect coalition structures that do not consist of the connected components of the underlying network of friends.

Altruistic Hedonic Games

7. Conclusions and Future Work

We have introduced and studied altruism in hedonic games where the agents utility functions may depend on their friends preferences. We have distinguished between three degrees of altruism, depending on the order in which an agent looks at her own and at her friends preferences, and between an averageand minimum-based aggregation of some agents preferences. Axiomatically, we have deﬁned desirable properties and have shown which of these are satisﬁed by which of our models and which are not. In particular, we have shown that all our altruistic preferences fulﬁll basic properties, such as reﬂexivity, transitivity, polynomial-time computability of utilities, and anonymity. Moreover, we have studied properties such as local unanimity, local friend dependence, and monotonicity. Speciﬁcally, local friend dependence is a crucial property that distinguishes altruistic preferences from previous models, e.g., from friend-oriented preferences (Dimitrov et al., 2006). We have considered two types of monotonicity, which combined with our six models of AHGs give 12 cases to study. Interestingly, monotonicity holds in only three of these cases while it fails to hold in the other nine cases. This contrasts with the results in altruistic coalition formation games (Kerkmann & Rothe, 2020) where monotonicity fails in three out of the corresponding 12 cases and is satisﬁed in the other nine cases (Kerkmann & Rothe, 2021). Comparing altruistic hedonic games to other types of hedonic games from the literature, we have seen that they can express diﬀerent preferences than the commonly studied representations. In terms of stability, altruistic hedonic games always admit, e.g., Nash stable coalition structures. In the case of selﬁsh-ﬁrst preferences, also core stable and strictly core stable outcomes are guaranteed to exist; both the veriﬁcation and the existence problem for perfectness is polynomial-time solvable; yet the veriﬁcation problems for core stability and strict core stability are computationally intractable, i.e., co NP-complete. We have also established characterizations for two of the stability notions, namely individual rationality and perfectness. We consider it important future work to complete the characterization of all stability notions (e.g., to characterize when the grand coalition is perfect under equal-treatment and altruistic-treatment preferences). Also, while the complexity results in Table 4 are complete for selﬁsh-ﬁrst altruistic hedonic games, they are not yet complete for the general case. It would therefore be interesting to see if we can ﬁnd matching lower and upper bounds in those cases where there is still a complexity gap. In particular, we consider it an important task to determine the complexity of ﬁnding or deciding the existence of (strictly) core stable coalition structures in equal-treatment and altruistic-treatment altruistic hedonic games. Also, there remain some open questions concerning the perfectness veriﬁcation and existence problems in equal-treatment and altruistic-treatment altruistic hedonic games. Comparing our altruistic extensions to the underlying friend-oriented preferences, we can see that our complexity results for selﬁsh-ﬁrst altruistic hedonic games mirror the known results for friend-oriented hedonic games (Aziz et al., 2013b; Bogomolnaia & Jackson, 2002; Dimitrov et al., 2006; Chen, Csáj, Roy, & Simola, 2022). So, the introduction of selﬁsh-ﬁrst altruism has no impact on the complexity of the considered stability problems. Yet, the introduction of equal-treatment or altruistic-treatment altruism might cause an increase in the complexity of the (strict) core stability existence problem. While it is easy to com-

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

pute strictly core stable coalition structures in friend-oriented hedonic games (cf. Dimitrov et al. (2006) or Theorem 6.5), this might not be the case for equal-treatment and altruistictreatment altruistic hedonic games. As mentioned earlier, we consider determining the precise complexity of these problems an important open problem. Another future direction might be the consideration of further altruistic models. It might be useful to extend our altruistic models and normalize by the size of the coalition to consider only relative valuations. This can be seen as an altruistic version of a friendoriented fractional hedonic game (Dimitrov et al., 2006; Aziz et al., 2019). For example, one could deﬁne

A avg EQf i B X

a (A Fi) {i}

va(A) |A| |(A Fi) {i}| X

b (B Fi) {i}

vb(B) |B| |(B Fi) {i}|

and study the common stability notions, etc. for these preferences. In addition, we propose to consider restrictions of the input such as constraining networks to special graph classes (e.g., interval graphs, where the width of an interval represents an agent s tolerance ) and studying problems of strategic inﬂuence (e.g., misreporting preferences to friends, pretending to be a friend while one in fact is an enemy, asserting control over the game as a whole). One could also consider diﬀerent weights for equal-treatment preferences because, as the number of friends increases, the weight of one s own opinion becomes diluted. This can be handled by weighting one s own opinion by 1/2 and the aggregated opinion of one s friends by 1/2. It could also be interesting to study the changes concerning stability if directed (nonmutual) networks of friends are considered. In a similar vein, the model can be extended to edge-weighted graphs, where the intensity of inﬂuence of a friend is given by the edge weight.

Acknowledgments

We are grateful to the anonymous AAMAS 16, STAIRS 20, and AAAI 21 reviewers for their helpful comments and suggestions. This work was supported in part by DFG grants RO1202/14-2 and RO-1202/21-1 and the project Online Participation funded by the NRW Ministry of Culture and Science.

Alcantud, J., & Arlegi, R. (2012). An axiomatic analysis of ranking sets under simple categorization. SERIEs Journal of the Spanish Economic Association, 3(1 2), 227 245.

Anagnostopoulos, A., Becchetti, L., de Keijzer, B., & Schäfer, G. (2013). Ineﬃciency of games with social context. In Proceedings of the 6th International Symposium on Algorithmic Game Theory, pp. 219 230. Springer-Verlag Lecture Notes in Computer Science #8146.

Apt, K., & Schäfer, G. (2014). Selﬁshness level of strategic games. Journal of Artiﬁcial Intelligence Research, 49, 207 240.

Altruistic Hedonic Games

Ashlagi, I., Krysta, P., & Tennenholtz, M. (2008). Social context games. In Proceedings of the 4th International Workshop on Internet & Network Economics, pp. 675 683. Springer-Verlag Lecture Notes in Computer Science #5385.

Aziz, H., Brandl, F., Brandt, F., Harrenstein, P., Olsen, M., & Peters, D. (2019). Fractional hedonic games. ACM Transactions on Economics and Computation, 7(2), 6:1 6:29.

Aziz, H., Brandt, F., & Harrenstein, P. (2013a). Pareto optimality in coalition formation. Games and Economic Behavior, 82, 562 581.

Aziz, H., Brandt, F., & Seedig, H. (2013b). Computing desirable partitions in additively separable hedonic games. Artiﬁcial Intelligence, 195, 316 334.

Aziz, H., & Savani, R. (2016). Hedonic games. In Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. (Eds.), Handbook of Computational Social Choice, chap. 15, pp. 356 376. Cambridge University Press.

Ballester, C. (2004). NP-completeness in hedonic games. Games and Economic Behavior, 49(1), 1 30.

Banerjee, S., Konishi, H., & Sönmez, T. (2001). Core in a simple coalition formation game. Social Choice and Welfare, 18(1), 135 153.

Barrot, N., Ota, K., Sakurai, Y., & Yokoo, M. (2019). Unknown agents in friends oriented hedonic games: Stability and complexity. In Proceedings of the 33rd AAAI Conference on Artiﬁcial Intelligence, pp. 1756 1763. AAAI Press.

Baumeister, D., & Rothe, J. (2015). Preference aggregation by voting. In Rothe, J. (Ed.), Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, Springer Texts in Business and Economics, chap. 4, pp. 197 325. Springer-Verlag.

Bilò, V., Celi, A., Flammini, M., & Gallotti, V. (2013). Social context congestion games. Theoretical Computer Science, 514, 21 35.

Bogomolnaia, A., & Jackson, M. (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38(2), 201 230.

Borel, É. (1921). La théorie du jeu et les équations intégrales à noyau symétrique gauche. In Comptes rendus hebdomadaires des séances de l Académie des sciences, Vol. 173. 1304 1308.

Brânzei, S., & Larson, K. (2011). Social distance games. In Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence, pp. 91 96. AAAI Press/IJCAI.

Bullinger, M., & Kober, S. (2021). Loyalty in cardinal hedonic games. In Proceedings of the 30th International Joint Conference on Artiﬁcial Intelligence, pp. 66 72. ijcai.org.

Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M., & Papaioannou, E. (2010). The impact of altruism on the eﬃciency of atomic congestion games. In Proceedings of the 5th International Symposium on Trustworthy Global Computing, pp. 172 188. Springer-Verlag Lecture Notes in Computer Science #6084.

Cechlárová, K., & Hajduková, J. (2003). Computational complexity of stable partitions with B-preferences. International Journal of Game Theory, 31(3), 353 364.

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

Cechlárová, K., & Hajduková, J. (2004). Stable partitions with W-preferences. Discrete Applied Mathematics, 138(3), 333 347.

Cechlárová, K., & Romero-Medina, A. (2001). Stability in coalition formation games. International Journal of Game Theory, 29(4), 487 494.

Chalkiadakis, G., Elkind, E., & Wooldridge, M. (2011). Computational Aspects of Cooperative Game Theory. Synthesis Lectures on Artiﬁcial Intelligence and Machine Learning. Morgan and Claypool Publishers.

Chen, J., Csáj, G., Roy, S., & Simola, S. (2022). Cores in friend-oriented hedonic games: Veriﬁcation is surprisingly harder than searching. Tech. rep. ar Xiv:2203.09655v1 [cs.GT], ACM Computing Research Repository (Co RR).

Chen, P., de Keijzer, B., Kempe, D., & Schäfer, G. (2014). Altruism and its impact on the price of anarchy. ACM Transactions on Economics and Computation, 2(4), Article 17, 17:1 17:45.

De Marco, G., & Morgan, J. (2007). Slightly altruistic equilibria in normal form games. Tech. rep. 185, Centre for Studies in Economics and Finance, University of Salerno, Fisciano, Italy.

Dimitrov, D., Borm, P., Hendrickx, R., & Sung, S. (2006). Simple priorities and core stability in hedonic games. Social Choice and Welfare, 26(2), 421 433.

Drèze, J., & Greenberg, J. (1980). Hedonic coalitions: Optimality and stability. Econometrica, 48(4), 987 1003.

Elias, J., Martignon, F., Avrachenkov, K., & Neglia, G. (2010). Socially-aware network design games. In Proceedings of the 29th Conference on Information Communications, pp. 41 45. IEEE.

Elkind, E., & Rothe, J. (2015). Cooperative game theory. In Rothe, J. (Ed.), Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, Springer Texts in Business and Economics, chap. 3, pp. 135 193. Springer-Verlag.

Faliszewski, P., Rothe, I., & Rothe, J. (2015). Noncooperative game theory. In Rothe, J. (Ed.), Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, Springer Texts in Business and Economics, chap. 2, pp. 41 134. Springer-Verlag.

Garey, M., Johnson, D., & Stockmeyer, L. (1976). Some simpliﬁed NP-complete graph problems. Theoretical Computer Science, 1, 237 267.

Gonzalez, T. (1985). Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38, 293 306.

Hare, B., & Woods, V. (2020). Survival of the Friendliest: Understanding Our Origins and Rediscovering Our Common Humanity. Penguin Random House, New York.

Hoefer, M., Penn, M., Polukarov, M., Skopalik, A., & Vöcking, B. (2011). Considerate equilibrium. In Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence, pp. 234 239. AAAI Press/IJCAI.

Altruistic Hedonic Games

Hoefer, M., & Skopalik, A. (2013). Altruism in atomic congestion games. ACM Transactions on Economics and Computation, 1(4), 21:1 21:21.

Kerkmann, A., Lang, J., Rey, A., Rothe, J., Schadrack, H., & Schend, L. (2020). Hedonic games with ordinal preferences and thresholds. Journal of Artiﬁcial Intelligence Research, 67, 705 756.

Kerkmann, A., & Rothe, J. (2020). Altruism in coalition formation games. In Proceedings of the 29th International Joint Conference on Artiﬁcial Intelligence, pp. 347 353. ijcai.org.

Kerkmann, A., & Rothe, J. (2021). Four faces of altruistic hedonic games. In Proceedings of the 8th International Workshop on Computational Social Choice. Nonarchival proceedings.

Koutsoupias, E., & Papadimitriou, C. (1999). Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pp. 404 413. Springer.

Ledyard, J. (1995). Public goods: A survey of experimental research. In Kagel, J., & Roth, A. (Eds.), The Handbook of Experimental Economics, chap. 2, pp. 111 194. Princeton University Press.

Monaco, G., Moscardelli, L., & Velaj, Y. (2018). Hedonic games with social context. In Proceedings of the 19th Italian Conference on Theoretical Computer Science, Vol. 2234, pp. 24 35. CEUR-WS.org.

Monaco, G., Moscardelli, L., & Velaj, Y. (2019). On the performance of stable outcomes in modiﬁed fractional hedonic games with egalitarian social welfare. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, pp. 873 881. IFAAMAS.

Nguyen, N., Nguyen, T., Roos, M., & Rothe, J. (2014). Computational complexity and approximability of social welfare optimization in multiagent resource allocation. Journal of Autonomous Agents and Multi-Agent Systems, 28(2), 256 289.

Nguyen, N., Rey, A., Rey, L., Rothe, J., & Schend, L. (2016). Altruistic hedonic games. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, pp. 251 259. IFAAMAS.

Nisan, N., Roughgarden, T., Tardos, É., & Vazirani, V. (Eds.). (2007). Algorithmic Game Theory. Cambridge University Press.

Olsen, M. (2012). On deﬁning and computing communities. In Proceedings of the 18th Computing: The Australasian Theory Symposium, Vol. 128, pp. 97 102.

Ota, K., Barrot, N., Ismaili, A., Sakurai, Y., & Yokoo, M. (2017). Core stability in hedonic games among friends and enemies: Impact of neutrals. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence, p. 359 365. AAAI Press.

Peleg, B., & Sudhölter, P. (2003). Introduction to the Theory of Cooperative Games. Kluwer Academic Publishers.

Kerkmann, Nguyen, Rey, Rey, Rothe, Schend & Wiechers

Peters, D. (2016). Complexity of hedonic games with dichotomous preferences. In Proceedings of the 30th AAAI Conference on Artiﬁcial Intelligence, pp. 579 585. AAAI Press.

Peters, D., & Elkind, E. (2015). Simple causes of complexity in hedonic games. In Proceedings of the 24th International Joint Conference on Artiﬁcial Intelligence, pp. 617 623. AAAI Press/IJCAI.

Popova, A., Regenwetter, M., & Mattei, N. (2013). A behavioral perspective on social choice. Annals of Mathematics and Artiﬁcial Intelligence, 68(1 3), 5 30. Special Issue: Algorithms, Approximation, and Empirical Studies in Behavioral and Computational Social Choice, edited by J. Goldsmith and J. Rothe.

Rahn, M., & Schäfer, G. (2013). Bounding the ineﬃciency of altruism through social contribution games. In Proceedings of the 9th International Workshop on Internet & Network Economics, pp. 391 404. Springer-Verlag Lecture Notes in Computer Science #8289.

Regenwetter, M., Grofman, B., Marley, A., & Tsetlin, I. (2006). Behavioral Social Choice: Probabilistic Models, Statistical Inference, and Applications. Cambridge University Press.

Rey, A., Rothe, J., Schadrack, H., & Schend, L. (2016). Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games. Annals of Mathematics and Artiﬁcial Intelligence, 77(3), 317 333.

Rosenthal, R. (1973). A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2, 65 67.

Rothe, J. (2019). How can we model emotional and behavioral dynamics in collective decision making?. In Laslier, J., Moulin, H., Sanver, R., & Zwicker, W. (Eds.), The Future of Economic Design, Studies in Economic Design, pp. 245 251. Springer.

Rothe, J. (2021). Thou shalt love thy neighbor as thyself when thou playest: Altruism in game theory. In Proceedings of the 35th AAAI Conference on Artiﬁcial Intelligence, pp. 15070 15077. AAAI Press.

Schlueter, J., & Goldsmith, J. (2020). Super altruistic hedonic games. In Proceedings of the 33rd International Florida Artiﬁcial Intelligence Research Society Conference, pp. 160 165. AAAI Press.

Sung, S., & Dimitrov, D. (2007). On core membership testing for hedonic coalition formation games. Operations Research Letters, 35(2), 155 158.

Sung, S., & Dimitrov, D. (2010). Computational complexity in additive hedonic games. European Journal of Operational Research, 203(3), 635 639.

von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100(1), 295 320.

von Neumann, J., & Morgenstern, O. (1944). Theory of Games and Economic Behavior. Princeton University Press.

Altruistic Hedonic Games

Wiechers, A., & Rothe, J. (2020). Stability in minimization-based altruistic hedonic games. In Proceedings of the 9th European Starting AI Researchers Symposium, Vol. 2655. CEUR-WS.org.

Woeginger, G. (2013a). Core stability in hedonic coalition formation. In Proceedings of the 39th International Conference on Current Trends in Theory and Practice of Computer Science, pp. 33 50. Springer-Verlag Lecture Notes in Computer Science #7741.

Woeginger, G. (2013b). A hardness result for core stability in additive hedonic games. Mathematical Social Sciences, 65(2), 101 104.