Loyalty in Cardinal Hedonic Games

1 Introduction

Decision making in multi-agent systems is highly driven by the idea of the , a rational decision taker

that seeks to maximize her individual well-being. Following the classical Theory of Games and Economic Behavior by von Neumann and Morgenstern, agents assign utilities to alternatives and aim for an outcome that maximizes individual utility. Such behavior entails many delicate situations in non-cooperative game theory such as the prisoner's dilemma or the tragedy of the commons [Hardin, 1968], where agents take decisions in their individual interest without regarding other agents. This leads to outcomes that are bad for the society as a whole and often, as it is the case in the prisoner's dilemma, agents have an incentive to coordinate to improve their respective situation.

From the theoretical point of view, one can either accept the existence of such dilemmata and study their social impact, for instance, by means of the price of anarchy [Koutsoupias and Papadimitriou, 1999], or one can ask for the degree of individual dependency on the social outcome necessary to escape a situation of inferior welfare. The latter idea is implemented by adapting the utility function of players as a weighted sum of individual and joint utility, an idea repeatedly developed in network design [Elias et al., 2010], artificial intelligence [Apt and Sch¨afer, 2014], or public choice [Mueller, 1986]. Specifically, the selfishness level by Apt and Sch¨afer is the lowest weight on the joint utility such that a Nash equilibrium becomes a social optimum.

On the other hand, empirical evidence does not only question whether agents behave according to the utility model by von Neumann and Morgenstern [Kahneman and Tversky, 1979], but even supports the hypothesis that human behavior is steered by the well-being of the whole society [Colman et al., 2008]. However, in scenarios of high competition, agents might also act spiteful towards other agents, i.e., there is an incentive to harm other agents [Levine, 1998].

In cooperative game theory, it seems to be an even more reasonable assumption to include other agents into the own valuation. We follow this line of thought in the setting of coalition formation, where we propose loyalty, a possibility to modify utilities by taking into account other agents' utilities towards which loyalty is perceived. Loyalty is a binary relation directly extracted from the agents' utilities over partnership, i.e., coalitions of size 2. Loyalty is sensed towards the agents within the own coalition that yield positive utility in a partnership. Following the paradigm of a chain that is only as strong as its weakest link, loyal utilities are obtained by taking the minimum of the own utility and the utilities of agents receiving our loyalty. As such, we obtain a loyal variant of the original game, which is itself a coalition formation game, and we can iterate towards various degrees of loyalty. As we will see, this process terminates in a game which satisfies a high degree of egalitarianism. We consider common solution concepts concerning group stability and efficiency for different degrees of loyalty and the limit game, and provide both existential and computational results.

We study coalition formation in the framework of hedonic games [Dr`eze and Greenberg, 1980; Banerjee et al., 2001; Bogomolnaia and Jackson, 2002]. Our contribution lies in studying aspects of empathy in hedonic games [Brˆanzei and Larson, 2011; Monaco et al., 2018; Nguyen et al., 2016]. Previous work considers empathy between agents through various alternative utility functions based on friendship relations among the agents extracted from utility functions or a social network. Closest to our work are altruistic hedonic games introduced by Nguyen et al. [2016] and subsequently studied by Wiechers and Rothe [2020], Kerkmann and Rothe [2020], and Schlueter and Goldsmith [2020]. Our first degree of loyalty in symmetric friend-oriented hedonic games coincides with minimum-equal-treatment altruistic hedonic games as defined by Wiechers and Rothe [2020]. We significantly extend their model, but since most of our hardness results work for the restricted class of symmetric friend-oriented hedonic games, they have immediate consequences for this type of altruistic hedonic games. Also, loyal variants of hedonic games fit into the framework of super altruistic hedonic games by Schlueter and Goldsmith [2020] if their aggregation is modified by taking the average instead of the minimum of other agents' utilities.

2 Preliminaries andModel

We start with some notation. Define [i] = {1, . . . , i} and [i, j] = {i, . . . , j} for i, j ∈ Z, i ≤ j.

Also, we use standard notions from graph theory. Let G = (V,E) be an undirected graph. For a subset of agents W ⊆ V , denote by G[W] the subgraph of G induced by W. Given two vertices v, w ∈ V , we denote by dG(v, w) their distance in G, i.e., the length of a shortest path connecting them. The graph G is called regular if there exists a non-negative integer r such that every vertex of G has degree r.

In the following subsections, we introduce hedonic games, our concept of loyalty, and desirable properties of coalition structures.

2.1 Cardinal Hedonic Games

Let N = {1, . . . , n} be a finite set of agents. A coalition is a non-empty subset of N. By Ni we denote the set of coalitions agent i belongs to, i.e., Ni = {S ⊆ N : i ∈ S}. A coalition structure, or simply a partition, is a partition π of the agents N into disjoint coalitions, where π(i) denotes the coalition agent i belongs to. A hedonic game is a pair (N,≿), where ≿ = (≿i)i∈N is a preference profile specifying the preferences of each agent i as a complete and transitive preference relation ≿i over Ni. In hedonic games, agents are only concerned about their own coalition. Accordingly, preferences over coalitions naturally extend to preferences over partitions as follows: π ≿i π′ if and only if π(i) ≿i π′ (i).

Throughout the paper, we assume that rankings over the coalitions in Ni are given by utility functions ui : Ni → R, which are extended to evaluate partitions in the hedonic way by setting ui(π) = ui(π(i)). A hedonic game together with a representation by utility functions is called cardinal hedonic game. Because the sets Ni are finite, preferences could in principle always be represented by cardinal values. This is impractical due to two reasons. First, such utility functions require exponential space to represent. Therefore it would be desirable to consider classes of hedonic games with succinct representations. Second, we would like to compare different agents' utility functions such that a certain cardinal value expresses the same intensity of a preference for all agents. This cannot be guaranteed by arbitrary utility representations of ordinal preferences. Our model of loyalty is therefore particularly meaningful in succinctly representable classes of cardinal hedonic games. These include the following classes of hedonic games, which aggregate utility functions over single agents of the form ui : N → R where ui(i) = 0, which can be represented by a complete weighted digraph.

• Additively separable hedonic games (ASHGs) [Bogomolnaia and Jackson, 2002]: utilities are aggregated by taking the sum of single utilities, i.e., ui(π) = ∑j∈π(i) ui(j).
• Friend-oriented hedonic games (FOHGs) [Dimitrov et al., 2006]: the restriction of ASHGs where utilities for other agents are either n (the agent is a friend) or -1 (the agent is an enemy), i.e., for all i, j ∈ N with i ̸= j, ui(j) ∈ {n,-1}. Given an FOHG, the set Fi = {j ∈ N : ui(j) = n} is called friend set of agent i. The unweighted digraph GF = (N, A) where (i, j) ∈ A if and only if j ∈ Fi is called friendship graph. An FOHG can be represented by specifying the friend set for every agent or by its friendship graph.
• Modified fractional hedonic games (MFHGs) [Olsen, 2012]: utilities are aggregated by dividing the sum of single utilities by the size of the coalition minus 1, i.e., ui(π) = 0 if π(i) = {i}, and ui(π) = ∑j∈π(i) ui(j) |π(i)|-1 , otherwise. In other words, the utility of a coalition structure is the expected utility achieved through another agent in the own coalition selected uniformly at random.

A cardinal hedonic game is called mutual if, for all pairs of agents i, j ∈ N, ui(j) > 0 implies uj(i) > 0. It is called symmetric if, for all pairs of agents i, j ∈ N, ui(j) = uj(i). Clearly, symmetric games are mutual. Throughout most of the paper, we will consider at least mutual variants of the classes of hedonic games, which we just introduced.

2.2 Loyalty in Hedonic Games

We are ready to define our concept of loyalty. Given a cardinal hedonic game, its loyal variant needs to specify two key features. First, for every agent, we need to identify a loyalty set, which contains the agents towards which loyalty is expressed. Second, we need to specify how loyalty is expressed, i.e., how to obtain new, loyal utility functions.

Formally, given a cardinal hedonic game and an agent i ∈ N, we define her loyalty set as Li = {j ∈ N \ {i}: ui({i, j}) > 0}. In other words, agents are affected by agents that influence them positively when being in a joint coalition. Note that for all hedonic games considered in this paper, the loyalty set is equivalently given by Li = {j ∈ N \ {i}: ui({i, j}) > ui(i)}, i.e., it contains the agents with which i would rather form a coalition of size 2 than staying on her own. The loyalty graph is the directed graph GL = (N, A) where (i, j) ∈ A if and only if j ∈ Li.

It remains to specify how agents aggregate utilities in a loyal way. Given a cardinal hedonic game, its loyal variant is defined on agent set N by the utility function uLi (π) = minj∈π(i)∩(Li∪{i}) uj(π(i)). Interestingly, the loyal variant is itself a hedonic game, and we can consider its own loyal variant. Following this reasoning, we recursively define the k-fold loyal variant by setting the 1-fold loyal variant to the loyal variant and the (k + 1)-fold loyal variant to the loyal variant of the k-fold loyal variant. Also, we denote by uki and Lki the utility function and the loyalty set of an agent i, and by GkL the loyalty graph of the k-fold loyal variant.

In fact, we will see that this process terminates after at most n steps in a limit game that satisfies egalitarianism at the level of coalitions. For simplicity, we restrict attention to mutual cardinal hedonic games, where the loyalty sets defines a symmetric binary relation and the loyalty graph can be represented by an undirected graph. 1 For an agent i ∈ N, let GπL(i) be the agents in the connected component of the subgraph of GL induced by π(i) containing i. Now, define the locally egalitarian variant of a cardinal hedonic game as the game on agent set N with utilities given by uEi (π) = minj∈GπL (i) uj(π). In other words, an agent receives the minimum utility among all agents reachable within her coalition in the loyalty graph.

Finally, we introduce a technical assumption. A mutual cardinal hedonic game is called loyalty-connected if, for all agents i ∈ N and coalition structures π, ui(GπL(i)) ≥ ui(π). This property precludes negative influence through agents outside the reach of loyalty, and is satisfied by reasonable classes of cardinal hedonic games like ASHGs, MFHGs, or fractional hedonic games [Aziz et al., 2019].

2.3 Solution Concepts

We evaluate the quality of coalition structures by measures of stability and efficiency.

A common concept of group stability is the core. Given a coalition structure π, a coalition C ⊆ N is blocking π (respectively, weakly blocking π) if for all agents i ∈ C, ui(C) > ui(π) (respectively, for all agents i ∈ C, ui(C) ≥ ui(π), where the inequality is strict for some agent in C). A coalition structure π is in the core (respectively, strict core) if there exists no non-empty coalition blocking (respectively, weakly blocking) π.

A fundamental concept of efficiency is Pareto optimality. A coalition structure π′ Pareto dominates a coalition structure π if, for all i ∈ N, ui(π′ (i)) ≥ ui(π(i)), where the inequality is strict for some agent in N. A coalition structure π is called Pareto optimal if it is not Pareto dominated by another coalition structure. In other words, given a Pareto optimal coalition structure, every other coalition structure that is better for some agent, is also worse for another agent.

Another concept of efficiency concerns the welfare of a coalition structure. There are many notions of welfare dependent on how to aggregate single agents' utilities for a social evaluation. In the context of loyalty, egalitarianism seems to be especially appropriate. It aims to maximize the well-being of the agent that is worst off. Formally, the egalitarian welfare of a partition π is defined as E(π) = mini∈N ui(π(i)). Also, let E k (π) denote the egalitarian welfare of the k-fold loyal variant. Following this definition, coalition structures maximizing egalitarian welfare are not necessarily Pareto optimal. However, there exists always a Pareto optimal coalition structure maximizing egalitarian welfare. Specifically, a coalition structure maximizes leximin welfare if its utility vector, sorted in non-decreasing order, is lexicographically largest. A coalition structure maximizing leximin welfare is Pareto optimal and maximizes egalitarian welfare.

1 This restriction is in accordance with our results, but it can be lifted with some technical effort.

Apart from finding efficient coalition structures, an individual goal of an agent i is to be in a best coalition, i.e., in a coalition in Ni maximizing her utility. Formally, the problem of, given a cardinal hedonic game, an agent i∗ ∈ N, and a rational number q ∈ Q, deciding if there exists a subset C ⊆ N with i∗ ∈ C and ui∗(C) ≥ q, is called BestCoalition.

3 Loyalty Propagation and Best Coalitions

Our first proposition collects some initial observations. It states, how loyalty propagates through the loyalty graph for higher degree loyal variants, terminating with the locally egalitarian variant, and considers egalitarian welfare.

Proposition 1. Let a mutual cardinal hedonic game on agent set N with |N| = n be given. Let k ≥ 1, i ∈ N, and π a coalition structure. Then, the following statements hold.

1. The loyalty graph and loyalty sets are the same for all loyal variants, i.e., GkL = G1L and Lki = L1i .
2. Loyalty extends to agents at distance k, i.e., uki (π) = min{uj(π) : j ∈ π(i) with dGL[π(i)](i, j) ≤ k}.
3. Utilities converge to the utilities of the locally egalitarian variant, i.e., uli = uEi for all l ≥ n.
4. Egalitarian welfare is preserved, i.e., E k (π) = E(π).

Proof. The first statements follow immediately frommutuality. We prove the second statement by induction over k. For k = 1, the assertion follows directly from the definition of the loyal variant.

Now, let k ≥ 2 be an integer. Let C = π(i), CL = π(i) ∩ (Li ∪ {i}), H = GL[π(i)], and for p ≥ 1, let Cp(j) = {m ∈ C with dH(j, m) ≤ p}. Then,

There, the second equality follows by induction, the third equality by definition of the loyalty graph, and the last equality by observing that the vertices with a distance of at most k from i are precisely the vertices with a distance of at most k - 1 from an arbitrary neighbor.

The third statement follows from the second one, and the final statement follows from the observation that the minimum utility among agents in a coalition structure is preserved when transitioning to a loyal variant.

Example 1. We provide an example showing that part 4 of Proposition 1 does not extend to leximin welfare.

Consider a symmetric FOHG with agent set N = {ai, bi, ci : 1 ≤ i ≤ 4} ∪ {z1, z2}, and the friendship graph in Figure 1. It can be shown that the coalition structure π = {{zi, a2i-1, a2i, b2i-1, b2i, c2i-1, c2i}: i = 1, 2} maximizes leximin welfare for its 2-fold loyal variant (consider agents of type bi). However, π is not even Pareto optimal under the original utilities. Indeed, π′ = {{z1, a1, a4, b1, b4, c1, c4}, {z2, a2, a3, b2, b3, c2, c3}} is a Pareto improvement. All agents receive at least the same utility, and a2, a4, c1, and c3 are better off.

Our next goal is to reason about finding best coalitions for an agent. Note that this problem can usually be solved in polynomial time. For instance, in ASHGs, given an agent i, every coalition that contains i together with all agents that give positive utility to i and no agent that gives negative utility to i is a best coalition for i. By contrast, we obtain hardness results for loyalty even in symmetric FOHGs. While it is possible to determine the number of friends of the unhappiest friend in a best coalition in polynomial time [Wiechers and Rothe, 2020], the problem becomes hard if the number of enemies is to be minimized at the same time. We omit some proof details and proofs due to space restrictions, but they can all be found in the extended version of the paper.

Theorem 2. Let k ≥ 1. Then, BestCoalition is NPcomplete for the k-fold loyal variant of symmetric FOHGs.

Proof sketch. Membership in NP is clear. For hardness, we provide a reduction from the NP-complete problem SetCover [Karp, 1972]. An instance of SetCover consists of a triple (A, S, κ), where A is some finite ground set, S ⊆ 2A is a set of subsets of A, and κ is an integer. The instance (A, S, κ) is a Yes-instance if there exists S′ ⊆ S with ⋃B∈S′ B = A and |S′ | ≤ κ. The reduction is illustrated in Figure 2.

Let k ∈ N. Define M = ⌊ k-1 2 ⌋. Given an instance (A, S, κ) of SetCover, define a = |A|. We define an instance ((N, (Fi)i∈N), i∗ , q) of BestCoalition based on an FOHG (N, (Fi)i∈N) represented via friend sets by specifying each individual component. The agent set is defined as N = {wi : i ∈ [0, a+2]}∪{vi : i ∈ [0, a-1]}∪{αj i , βj i : i ∈ [a], j ∈ [M]} ∪ A ∪ S, and consists of representatives of the elements of A and S, and auxiliary agents. If k is even, set i∗ = w0 and if k is odd, i∗ = v0. The friend sets are given as

• Fw0 = {w1, v0, . . . , va-1},
• Fw1 = {w0,w2,w3, . . . ,wa+2},
• Fwi = {wj : j ∈ [a+2], j ̸= i} for i ∈ [2, a+2],
• Fvi = {w0, α1 1 , . . . , α1a } for i ∈ [0, a - 1] if k > 2,
• Fvi = {w0} ∪ A for i ∈ [0, a - 1] if k ≤ 2,
• Fα1i = {v0, . . . , va-1, β1 i } for i ∈ [a],
• Fαji = {βj-1 1 , . . . , β j-1 a , βj i } for i ∈ [a], j ∈ [2,M],
• Fβj i = {αj i , αj+1 1 , . . . , αj+1 a } for i ∈ [a], j ∈ [M -1],
• FβM i = {αM i } ∪A for i ∈ [a],
• Fx = {βM i : i ∈ [a]} ∪ {s ∈ S : x ∈ s} for x ∈ A if k > 2,
• Fx = {v0, . . . , va-1} ∪ {s ∈ S : x ∈ s} for x ∈ A if k ≤ 2, and
• Fs = {x ∈ A: x ∈ s} for s ∈ S (in other words, Fs = s).

Finally, with n = |N|, specify the threshold utility q = n(a + 1) - (a + κ) for k = 1 and q = n(a + 1) - (1+κ+2(M +1)a), otherwise. Note that the distance between i∗ and the xi in the loyalty graph is exactly k.

If (A, S, κ) is a Yes-instance, let S′ ⊆ S be a set cover of A with at most κ sets. For k = 1, consider the coalition C = A ∪ S′ ∪ {v0, . . . , va-1, w0, w1}. For k ≥ 2, consider the coalition C = (N \ S) ∪ S′ . It is quickly checked that in each case ukv0 (C) ≥ q.

Conversely, assume that C is a coalition with i∗ ∈ C and uki∗(C) ≥ q. Then, all agents that have a distance of at most k in the loyalty graph have to be included due to the degrees of vertices at a distance of at most k. In particular, A ⊆ C for any k. Let S′ = C ∩ S.

First, consider the case k = 1. Then, uv0 (C) = n(a + 1) - a - |S′ |. Hence u1v0 (C) ≥ q implies that |S′ | ≤ κ. In addition, every agent x ∈ A must have at least a + 1 friends present in C. In other words, for every x ∈ A there exists s ∈ S′ with x ∈ s. Hence, S′ is a cover of A with at most κ elements.

For arbitrary k ≥ 2, it holds that ui∗(C) = n(a+1)-1|S′ | - (M + 2)a. Hence u1v0 (C) ≥ q implies that |S′ | ≤ κ. The remainder follows analogous to the case k = 1.

Since the instances in the previous reduction contain agents with an arbitrarily large distance (parametrized by k), we cannot deduce direct consequences for the locally egalitarian variant. However, it is possible to bound the diameter in the reduced instances globally to obtain a similar result.

Theorem 3. BestCoalition is NP-complete for the locally egalitarian variant of symmetric FOHGs.

If we change the underlying class of hedonic games, we can circumvent the hardness results of the last two theorems.

Theorem 4. Let k ≥ 1. Then, BestCoalition can be solved in polynomial time for the k-fold loyal variant and the locally egalitarian variant of symmetric MFHGs.

4 Coalition Structures in the Core

In this section we consider group stability in the locally egalitarian variant and the loyal variants.

4.1 Core in the Locally Egalitarian Variant

We start with a general lemma yielding a sufficient condition for existence of Pareto optimal coalition structures in the core.

Lemma 5. Consider a class of hedonic games with the following two properties:

1. Restrictions of the game to subsets of agents are in the class.
2. For every coalition in any game of the class, the value of the coalition is the same for every player in the coalition.

Then, for every game in the class, there exists a coalition structure in the core which is Pareto optimal.

Weakening the second condition of the lemma to the existence of some coalition that is best for all of its members is sufficient to find a coalition structure in the core. We discuss this in the extended version of the paper. Interestingly, the lemma can be applied to the locally egalitarian variant of cardinal hedonic games under fairly weak assumptions.

Theorem 6. Let a loyalty-connected, mutual cardinal hedonic game be given. Then, there exists a Pareto optimal coalition structure in the core of its locally egalitarian variant.

Proof. Let a loyalty-connected, mutual cardinal hedonic game be given and consider its locally egalitarian variant. We modify the utility functions such that uEi (C) stays the same if C is connected in the loyalty graph, and set it to 0, otherwise. It suffices to find a Pareto optimal member of the core under this modification, because, by loyalty-connectivity, splitting coalitions into their connected components in the loyalty graph is weakly better for every agent, even under uE . Consider the class of hedonic games given by this modified n-fold loyal variant together with all of its restrictions, in which we apply the same modifications towards the utility values for non-connected coalitions.

By Proposition 1, the utility for a coalition is the same for every player in the coalition. Hence, all requirements of Lemma 5 are satisfied and we find the desired coalition structure.

In the extended version of the paper, we provide an example for the necessity of loyalty-connectivity in the previous theorem.

Example 2. We extend an example by Wiechers and Rothe [2020] that shows that the previous result cannot be strengthened to find a coalition structure in the strict core. Consider the symmetric FOHG on agent set {a, b, c, d, e} with loyalty graph depicted below.

Consider its locally egalitarian variant. Then, {a, b, c} is the unique best coalition for agents b and c and among the best coalitions for agent a. Hence, it has to be contained in every coalition structure in the strict core. Similarly, {a, d, e} has to be a coalition in the strict core. As these conditions cannot be satisfied simultaneously, the strict core is empty.

Note that both the coalition structure {{a, b, c}, {d, e}} and {{a, d, e}, {b, c}} are in the core and Pareto optimal.

The construction in Lemma 5 gives rise to a simple recursive algorithm that computes Pareto optimal coalition structures in the core. Still, the computational complexity highly depends on the underlying cardinal hedonic game. While a modified version of the algorithm by Bullinger [2020] for computing Pareto optimal coalition structures in symmetric MFHGs finds a coalition structure in the core of their locally egalitarian variants, a version of our reduction on best coalitions shows an intractability for FOHGs.

Theorem 7. The following statements hold.

1. Computing a coalition structure in the core can be done in polynomial time for the locally egalitarian variant of symmetric MFHGs.
2. Computing a coalition structure in the core is NP-hard for the locally egalitarian variant, even in the class of symmetric FOHGs with non-empty core.

4.2 Core in the Loyal Variants

In contrast to the locally egalitarian variant, the k-fold loyal variant may have an empty core for arbitrary k. This is even true in a rather restricted class of symmetric ASHGs with individual values restricted to {n, n + 1, -1}.

Proposition 8. For every k ≥ 1, there exists a symmetric ASHG with O(k) agents such that the core of its k-fold loyal variant is empty.

Proof sketch. We only describe the instance. Let k ∈ N. We define an ASHG (N, (ui)i∈N). Set m = k if k is an even number and m = k + 1 if k is odd. Let Ai = {ai, bi1 , . . . , bim, ci1 , . . . , cim} for i ∈ [3]. Define N = ⋃3i=1 Ai as the set of agents and let n = |N|. Reading indices i modulo 3, we define symmetric utilities according to

• u(ai, bi1 ) = u(ai, ci1 ) = n + 1 for i ∈ [3],
• u(bim, ai+1) = u(cim, ai+1) = n for i ∈ [3],

• u(bij , bij+1 ) = u(cij , cij+1 ) = n + 1 for i ∈ [3], j ∈ [m-1], and
• u(v, w) = -1 for all other utilities.

We can use the previous counterexample as a gadget in a sophisticated reduction to obtain computational hardness.

Theorem 9. Let k ≥ 1. Deciding whether the core is nonempty is NP-hard for the k-fold loyal variant of symmetric ASHGs.

Naturally, the question arises whether the core is always non-empty for loyal variants of FOHGs. While we leave the ultimate answer to this question as an open problem, we give evidence into both directions. First, we determine certain graph topologies that allow for coalition structures in the core. By contrast, we provide an intractability result for the computation of coalition structures in the core, and in the extended version of the paper we show that the dynamics related to blocking coalitions can cycle.

Proposition 10. Let a symmetric FOHG with connected, regular friendship graph be given. Then the coalition structure consisting of the grand coalition is in the strict core for the k-fold loyal variant for every k ≥ 1.

Proof. Assume that the friendship graph is regular with every vertex having degree r. Singleton coalitions are clearly not weakly blocking, so we may assume that r ≥ 2. In addition, we may assume that a weakly blocking coalition induces a connected subgraph of G. In a weakly blocking coalition C ⊊ N, some agent would have less than r friends, strictly decreasing her utility. Hence, the grand coalition is in the strict core.

Albeit the previous proposition may look rather innocent, regular substructures in the loyalty graph have been very useful in dealing with core (non-)existence (see, e.g., the many cycles in the games of Proposition 8 and Theorem 9).

For symmetric FOHGs with a tree as loyalty graph, it is easy to see that a coalition structure is in the core if and only if its coalitions form an inclusion-maximal matching. In the case of ASHGs, we can apply a greedy matching algorithm to compute coalition structures in the core.

Proposition 11. Let k ≥ 1. A coalition structure in the core of the k-fold loyal variant can be computed in polynomial time for symmetric ASHGs with a tree as loyalty graph.

On the negative side, even under the existence of core partitions, it may be hard to compute them. Interestingly, the next theorem does not cover the case k = 1.

Theorem 12. Let k ≥ 2. Computing a coalition structure in the core is NP-hard for the k-fold loyal variant of symmetric FOHGs with non-empty core.

On the other hand, if the games originate from symmetric MFHGs, we obtain a polynomial-time algorithm by a modification of the algorithm in Theorem 7.

Theorem 13. Let k ≥ 1. Computing a coalition structure in the core can be done in polynomial time for the k-fold loyal variant of symmetric MFHGs.

5 Conclusion and Open Problems

We have introduced loyalty in hedonic games as a possible way to integrate relationships of players in a coalition into the coalition formation process. Given a hedonic game, players can modify their utilities to obtain a new hedonic game which regards loyalty among coalition partners. Applying loyalty multiple times yields a sequence of hedonic games with increasing loyalty, eventually terminating in a hedonic game with utilities that represent a local form of egalitarianism. The limit game usually contains Pareto optimal coalition structures in the core, but their efficient computability is dependent on the initial input game. We show that computing best coalitions is hard if the input is an FOHG, a reduction that can also be applied to the computation of coalition structures in the core, revealing a close relationship of the two problems. An overview of our results is given in Table 1.

Our work offers plenty directions for further investigation. First, similarly to altruistic hedonic games, one can make the aggregation mechanism for loyal utilities dependent on a priority amongst the agents, or take averages instead of sums. This yields new notions of loyalty that are worth to investigate and compare. Second, it would be interesting to approach loyalty for other underlying classes of hedonic games such as fractional hedonic games. This includes also to find a reasonable way to define loyalty for purely ordinal input. Note that our (equivalent) definition of the loyalty set is also applicable in this case. Finally, an intriguing open problem concerns the existence of coalition structures in the core for loyal variants of FOHGs, in particular for the 1-fold variant, where we could not show hardness of the computational problem.

Acknowledgements

This work was supported by the German Research Foundation under grants BR 2312/12-1 and 277991500/GRK2201. We would like to thank Ina Seidel, Johannes Bullinger, Anna Maria Kerkmann, and J¨org Rothe for valuable discussions, and thank the anonymous reviewers.