Coalitional Affinity Games and the Stability Gap

1 Introduction

Imagine the following scenario. You are organizing a party and have to come up with a seating arrangement, but this arrangement should take into consideration the relationships between the guests. For example, Alice is a good friend of Bob and would like to sit with him. However, Alice is feuding with Chris, Bob's best friend, and refuses to remain at any table with Chris. You want to make all the guests as happy as possible, but you also do not want guests changing the seating arrangement when they arrive. How should you assign the guests to tables?

The scenario just described has some interesting features. First, the agents (or guests) have value from interacting or being associated with others, and this value may be positive or negative. Second, the agents would like to coordinate with others, but ideally only with agents with whom they have a positive relationship. Finally, we would like stability. That is, once a group is seated at a table, they have no incentive to move.

In this paper we propose a model which explicitly captures the value, which we call the affinity, that an agent receives from being associated with another agent. In particular we study situations where an agent is interested in belonging to groups (coalitions) that contain agents for which it has high affinity, while avoiding groups that contain agents for which

Kate Larson

Cheriton School of Computer Science University of Waterloo Waterloo, Canada

klarson@uwaterloo.ca

it has negative affinity. By placing our affinity model into the context of non-transferable utility coalitional games [Peleg and Sudh¨olter, 2003], we are able to characterize and compare cooperative structures (i.e. coalition structures) that maximize social welfare with those that are stable (i.e. in the core). We argue that our affinity model is a rich representation that can be used to model many situations, while at the same time has enough structure to provide interesting characterizations of coalitions and coalition structures.

We organize the rest of the paper as follows. In the next section we introduce our affinity model, the affinity graph and coalitional affinity game. We also introduce the important concepts from the literature on coalitions that we use throughout the paper. In Section 3 we provide a complete characterization of the social-welfare maximizing coalition structure. We then study stability properties of the coalitional affinity game, using the core as the solution concept. In Section 5 we compare the social-welfare maximizing coalition structure with stable coalition structures. We ask the question "Assuming that stable coalition structures exist, how large a sacrifice, in terms of social welfare, does the group of agents have to make in order to be stable?" Experimental work, described in Section 6, support our theoretical findings from Section 5, while also showing that in practice, the core of coalitional-affinity games is often non-empty.

2 The Model

Let there be a set of agents N = {x1, . . . , xn}. For any pair of agents, we denote the affinity that agent xi has for xj as a(xi, xj) ∈ R which represents the value that agent xi receives from being associated with agent xj. We represent the agents and their affinities with an affinity graph.

Definition 1 An affinity graph, A = (N,E), is a weighted directed graph where

• N is a set of agents, N = {x1, . . . , xn},
• edge (xi, xj) ∈ E represents an affinity relation between agents xi and xj , and
• weight a(xi, xj) ∈ R is the value that agent xi receives from being associated with agent xj . 1

1 If (xi, xj) ̸∈ E then a(xi, xj) = 0.

Figure 1 is an example of an affinity graph. While the definition of an affinity graph is general, we will sometimes be interested in symmetric affinity graphs.

Given an affinity graph, A = (N, E), we are interested in understanding how agents will choose to interact with each other by forming coalitions. We define the utility of agent xi from belonging in coalition S ⊆ N as follows:

Referring back to Figure 1 where N = {x, y, z}, we have u(N, x) = 1 + 5 = 6, u(N, y) = 1 + 0 = 1 and u(N, z) = -3+0 = -3. Since an agent can always decide to not belong to a coalition, we are interested in coalitions where the utility of an agent is at least zero. If for agent xi ∈ S, u(S, xi) ≥ 0 then we say that S is individually rational for agent xi.

It is now possible to define a coalitional affinity game which is modeled as a characteristic function game with nontransferable utility [Peleg and Sudh¨olter, 2003].

Definition 3 Given an affinity graph A = (N,E), the coalitional affinity game, G(A), is the pair 〈N, v〉 where

• N is the set of agents defined by A, and
• for any S ⊆ N, v(S) ⊂ R|S| , such that for xi ∈ S, vi(S) = u(S, xi).

If A is symmetric, then we say that G(A) is a symmetric affinity game. While the value function, v, of a coalitional affinity game returns a vector given a coalition, where entry i is the value that agent xi receives from being in the coalition, we will sometimes abuse notation and say that the value of coalition S is

This definition implicitly assumes that agents' utilities are comparable. While this assumption is quite strong, it is commonly made in much of the coalition literature (see, for example [Bachrach and Rosenschein, 2008]) including work studying coalitions in networks (see, for example [Jackson and Wolinsky, 1996]).

As is standard, we define a coalition structure, P, to be a partition of the set of agents into coalitions. We are interested in properties of different coalition structures, such as the social welfare of a coalition structure and whether it is stable.

Definition 4 The social welfare of coalition structure P = (S1, . . . , Sm) is SW(P) = ∑mi=1 ∑xj∈Si u(Si, xj ).

The notion of stability we use in this paper is the core solution concept. We emphasize that this definition does not rely on any assumptions concerning inter-agent utility comparisons.

Definition 5 A coalition structure P = (S1, . . . , Sm) is in the core if there is no coalition B ⊆ N such that ∀x ∈ B, if x ∈ Si then u(B, x) ≥ u(Si, x) and for some j, 1 ≤ j ≤ m, ∃y ∈ Sj such that u(B, y) > u(Sj, y). If the inequality is strict then P is in the weak core.

If a coalition structure P is in the core, then it is resistant against group deviations. No set of agents, B, can break away by forming a new coalition and improve the utility for at least one member, while not degrading the other agents. If such a coalition exists, then it is called a blocking coalition.

We introduce a weaker stability concept, inner stability, which limits the type of group deviations that can occur.

Definition 6 A coalition structure, P = (S1, . . . , Sm) exhibits inner stability if there is no blocking coalition B such that B ⊂ Si for some i, 1 ≤ i ≤ m.

If a coalition structure exhibits inner stability then any blocking coalition must "cross coalition boundaries" by drawing members from at least two different coalitions.

2.1 RelatedModels

In this section we describe two models which are closely related to coalitional affinity games. Coalitional affinity games are a special subclass of hedonic games [Dr`eze and Greenberg, 1980; Bogomolnaia and Jackson, 2002]. Hedonic games are non-transferable utility games where each agent's utility depends on the identity of the other members of its coalition. Thus our model represents hedonic games where the pair-wise relationships between coalition members are important. 2 While we cannot represent all hedonic games, we capture an interesting subclass and our representation allows us to leverage the underlying relationships between agents when providing characterizations of social-welfare maximizing and stable coalition structures.

Another related model was proposed by Deng and Papadimitriou [Deng and Papadimitriou, 1994]. They also used a weighted (undirected) graph to model the relationship between agents, and defined the value of a coalition S, v(S), as we do in this paper. However, an important distinction between their work and ours is that they assumed transferable utility, and thus agents were able to freely redistribute the value of a coalition amongst themselves. This key difference in the models (transferable vs. non-transferable utility) means that the results obtained (and the techniques used) do not apply in our setting, as we illustrate later.

3 Social Welfare and Affinity Games

Given an affinity graph one question we are interested in is how the agents should be assigned to coalitions so as to maximize the social welfare. In general, this coalition-structure generation problem is challenging since if there are n agents, then there are O(nn ) possible coalition structures. While there has been much work on searching for social-welfare maximizing coalitions for general coalition problems (see, for example [Rahwan et al., 2007], we are interested in understanding whether there are any particular properties in the affinity-graph representation that can be used to characterize the social-welfare maximizing coalition structure.

2 We can also model certain situations where the utility depends on the number of members, and not on their identities.

In this section we note the relationship between the socialwelfare maximizing coalition structure and the minimal cut of the affinity graph. This observation provides us with a complete characterization of the structure of social-welfare maximizing coalition structures. Recall that a k-cut of weighted graph G = (N,E) is a partition of N into k disjoint sets P = (S1, S2, . . . , Sk), where Si ⊆ N and Si ∩ Sj = ∅ if i ̸= j. The size of the cut is equal to the sum of the weight of the edges between each Si, Sj ∈ P. A minimal k-cut is a k-cut that is no larger than any other k-cut.

Lemma 1 Given an affinity game G(A) , and a fixed value k, 1 ≤ k ≤ n, a minimal k-cut of A has the highest social welfare amongst all coalition structures of size k.

Proof: For any coalition structure of size k, Pk = (S1, . . . , Sk), let w(Si, Sj) be the sum of the weights of the edges in the cut between coalitions Si and Sj. That is

Then, the weight of the cut of Pk is

Since the value of a coalition, Si is equal to ∑x,y∈Si a(x, y), the social welfare of Pk is

Therefore, the social welfare of Pk is equal to the sum of all edges in Aminus the edges in the cut. That is

Therefore, the coalition structure of size k that maximizes social welfare, P ∗ k , is the one that minimizes Cut(P ∗ k ). □

Theorem 1 Given affinity game G(A), let P ∗ k be a minimal k-cut of affinity graph A = (N,E). Then a social welfare maximizing coalition is P ∗ = maxk [P ∗ 1 , . . . , P ∗ n ].

Proof: Proof follows immediately from Lemma 1. □

Theorem 1 provides a characterization of the socialwelfare maximizing coalition structure for an arbitrary affinity graph. If the affinity graph is symmetric (Definition 2) then we are able to describe additional properties of the socialwelfare maximizing coalition structure, P ∗ .

Theorem 2 Let G(A) be a symmetric affinity game, and let P ∗ = (S∗ 1 , . . . , S∗ k ) be the social-welfare maximizing coalition structure. Then, for any S∗ i ∈ P ∗ , any cut of S∗ i is nonnegative.

Due to space limitations we are unable to include the proof of Theorem 2. However, the proof involves assuming that a social-welfare maximizing coalition structure, P ∗ , has a negative cut, and then deriving a contradiction by finding another coalition structure P ′ such that SW(P ′ ) > SW(P ∗ ).

Theorem 2 does not imply that coalition structures that maximize social welfare in symmetric affinity games only contain coalitions who's members all have positive affinity. Instead, if agents x, y ∈ S∗ i and a(x, y) < 0, then there must exist other agents in S∗ i \ {y} such that

Informally, if a coalition belongs to the social-welfare maximizing coalition structure, and if two agents in the coalition dislike each other, then there must be other agents in the coalition that the two agents like.

Corollary 1 follows directly from Theorem 2.

Corollary 1 If G(A) is a symmetric affinity game and P ∗ = (S∗ 1 , . . . , S∗ k ) is a social-welfare maximizing coalition structure, then ∀S∗ i ∈ P ∗ , S∗ i is individually rational.

Proof: Let x ∈ S∗ i . If |S∗ i | = 1 then u(S∗ i , x) = 0 and so S∗ i is individually rational. Assume that |S∗ i | > 1. Then u(S∗ i , x) = ∑(x,y)|y∈S∗ i a(x, y). From Theorem 2, we know that every cut of S∗ i is non-negative. Therefore,

since otherwise we could find a cut ({x}, S∗ i \ {x}) which is strictly negative. That is u(S∗ i , x) ≥ 0. □

4 Stability and Affinity Games

In this section we study the stability of different coalition structures for affinity games, and in particular how the existence of stable coalition structures (where we use the core as our definition of stability) depends on the underlying affinity graph. We first note that for a general affinity game, the core may be empty. Figure 2 is an example of an affinity game for which there is no coalition structure in the core. 3 While

3 The grand coalition, ({x, y, z}) is blocked by coalition {z}, ({x}, {y}, {z}) is blocked by {x, z}, ({x}, {y, z}) is blocked by for general affinity games, the core may be empty, there are interesting affinity-graph structures for which there are positive results. Our first two results follow immediately from the definition of the utility functions of the agents.

Theorem 3 Let G(A) be an affinity game. If for all (xi, xj) ∈ E, a(xi, xj) ≥ 0, then the grand coalition is in the core.

Theorem 4 Let G(A) be an affinity game. If for all (xi, xj) ∈ E, a(xi, xj) ≤ 0 then the coalition structure P = ({x1}, {x2}, . . . , {xn}) is in the core.

We contrast Theorem 4 with the transferable-utility case. In particular, if agents have transferable utilities then the core is non-empty if and only if there is no negative cut (Lemma 2) [Deng and Papadimitriou, 1994]. This discrepancy highlights the differences in our models.

If the affinity graph is symmetric then we can further expand our understanding of stable coalition structures. Our next result shows that the social-welfare maximizing coalition structure, while not necessarily belonging in the core, still satisfies an interesting stability property.

Theorem 5 If affinity game G(A) is symmetric, then the social-welfare maximizing partition, P ∗ exhibits inner stability.

Proof: Let P ∗ = (S∗ 1 , . . . , S∗ k ) be the social-welfare maximizing coalition structure. Assume that there exists S∗ j with blocking coalition B ⊂ S∗ j . Since B blocks S∗ j then for all xi ∈ B, u(B, xi) ≥ u(S∗ j , xi) and the inequality is strict for at least one agent. However, since B ⊂ S∗ j , u(S∗ j , xi) = u(B, xi) + ∑xk∈S∗ j \B a(xi, xk), and so

where Cut(B, S∗ j \B) is the weight of the cut between B and S∗ j . Therefore, Cut(B, S∗ j \ B) < 0. But this is not possible (Theorem 2). Therefore B can not exist, and thus P ∗ exhibits inner stability. □

5 Stability and Social Welfare

In this section we study the relationship between the core and social welfare. Our first observation is that for affinity games, if a coalition structure, P , is in the core, then this does not imply that it must also be a social-welfare maximizing coalition structure. 4 Figure 3 illustrates this. The social-welfare maximizing coalition structure is P ∗ = ({x, t}, {y, z}). However P ∗ is not in the core when W > 3 since {x, y} is a blocking coalition. In fact, the coalition structure P C =

{y}, and coalition structure ({x, z}, {y}) is blocked by {y, z} while ({y, z}, {x}) is blocked by {x, z}.

4 Researchers on coalitions in other network-based games have also made similar observations [Jackson and Wolinsky, 1996].

({x, y}, {t, z}) is in the core but SW(P C ) = 2W + 2 < 4W -4 = SW(P ∗ ). While the core members may not maximize social welfare, and the social welfare maximizing coalition structure may not be in the core, we are still interested in understanding the relationship between the two concepts. In particular, we are interested in understanding the potential loss of social welfare that comes from being in the core. We call this loss the stability gap.

Definition 7 Let G(A) be an affinity game with a non-empty core. Let P ∗ be the social-welfare maximizing coalition structure, and let P C be a member of the core. The stability gap of P C is

If Gap(P C ) = 1 then P C is a social-welfare maximizing coalition structure. If Gap(P C ) > 1 then P C sacrifices social welfare in exchange for stability. For a given affinity game G(A) we are particularly interested in measuring the stability gap of the member of the core with the lowest social welfare,

and the stability gap of the member of the core with the highest social welfare

Clearly, Gapmin(A) ≥ Gapmax(A) for any affinity graph with a non-empty core. We also note that Gapmin(A) has parallels with the price of anarchy while Gapmax(A) has parallels with the price of stability [Nisan et al., 2007].

We start by looking at general affinity graphs. Unfortunately, our first result is negative.

Theorem 6 Let G(A) be an affinity game with a non-empty core. Then, Gapmax(A) can be unbounded.

Proof: Consider the graph A = (N,E) where N = {x0, x1, . . . , xn-1}. Let

That is, A is a star with x0 as the center. Now, let a(x0, x1) = a(x1, x0) = 1 and for all xi such that 1 < i < n let a(x0, xi) = -1 and a(xi, x0) = W for some W ≥ 1. The social-welfare maximizing coalition structure P ∗ is the grand coalition, and SW(P ∗ ) = (n - 2)(W - 1) + 2. The only coalition structure in the core, however, is P C = ({x0, x1}, {x2}, . . . , {xn-1}), and SW(P C ) = 2. Therefore, for arbitrary W > 1,

While Theorem 6 is distressing since it states that even core members with the highest social welfare can still be arbitrarily worse than the maximum social welfare, if we place some restrictions on the affinity graph, then the sacrifice in terms of social welfare is significantly reduced.

Theorem 7 Let G(A) be a symmetric affinity game with a non-empty core. Then Gapmin(A) is bounded by 2, and this bound is tight.

Proof: Let P C be amember of the core of affinity graphA. We will show that SW(P C ) ≥ 12 SW(P) for any coalition structure P = (S1, . . . , Sm). Before starting the proof, we need to introduce the notation used in the rest of the proof. First, for agents i, j ∈ N define

Then

since it is the sum of all weights of edges inside each coalition of P (and does not count the cut edges between coalitions).

Second, for agents {x1, x2, . . . , xt} let P - x1 - . . . - xt denote a new coalition structure

We say that a coalition structure P1 = (C1, . . . , Ck) blocks another coalition structure P2 = (S1, . . . , Sm) if there exists some Ci ∈ P1 such that ∀x ∈ Ci, u(C, x) ≥ u(Sj , x) where x ∈ Sj .

Finally, we will abuse notation and for any partition P = (S1, . . . , Sm) and agent x ∈ Si, we say u(P, x) = u(Si, x).

We can now start the proof. Since P C is in the core, by definition of the core it follows that it is not blocked by P. Therefore, there exists at least one agent, say x1, such that u(P, x1) ≤ u(P C , x1). Now, consider coalition structure P - x1. P - x1 does not block P C and so there must exist some agent x2 such that u(P - x1, x2) ≤ u(P C , x2) by definition of the core. We can continue this process and iteratively remove agents in the order x1, x2, . . . , xn-1. Each new coalition structure does not block P C since P C is in the core. Therefore, we get the following inequalities;

Summing, we get

Since

we have

and so

Substituting in Equation 1 we get

Since this holds for all coalition structures, it must also hold for the social-welfare maximizing coalition structure, P ∗ .

To show that the bound is tight, consider the example in Figure 3. Recall that the coalition structure P ∗ = ({x, t}, {y, z}) maximizes welfare with SW(P ∗ ) = 4W - 4. The coalition structure P C = ({x, y}, {t, z}) is in the core, and SW(P C ) = 2W + 2. The stability gap of P C is 4W-4 2W+2 , which converges to 2 as W → ∞. □

6 Experiments

Section 5 showed that for symmetric affinity games, the sacrifice in social welfare in order to achieve stability was bounded by a constant (2), while in general affinity games it could be unbounded. These results relied on the assumption that the core was non-empty. In this section we describe a series of experiments that we conducted on randomly generated symmetric affinity games, to answer the following questions: i) How often is the core non-empty? and ii) What are Gapmax(A) and Gapmin(A) in practice?

To generate random symmetric affinity games we generated graphs with |N| ranging from 4 to 10. For each edge in the graph we assigned an integer weight from interval [-W,W], chosen uniformly at random. We generated 1000 graphs for each W. In the rest of this section we show results for W ∈ {1, 5, 25, 125, 700} since these were illustrative of general trends, irrespective of the number of agents. For each graph we exhaustively searched the space of coalition structures to find the social-welfare maximizing coalition structure, and if the core was non-empty, we found the member of the core with the highest social welfare, and with the lowest social welfare.

In our first set of experiments we studied the frequency with which the core and weak core actually exists. Table 1 presents our findings. We note that the weak core was never empty, and that core was non-empty for a significant number of the random affinity games.

In our next set of experiments we restricted ourselves to affinity games where the core is non-empty. Table 2 contains our findings. We note that the stability gap is always very close to one, indicating that the sacrifice with respect to social welfare in order to gain stability is actually very low, and for many instances we found that the core and weak core did contain the social-welfare maximizing coalition structure. 5 In the rest of this section we propose a hypothesis as to why this was so.

In Theorem 5 we proved that for any symmetric affinity game, the social-welfare maximizing coalition structure, P ∗ = (S∗ 1 , . . . , S∗ k ), satisfies inner stability. This means that in order for P ∗ to not belong in the core, there must exist a blocking coalition, B, that draws its members from different coalitions in P ∗ . Thus, these agents, once inside B, derive their utility from edges that belong to the minimum cut. Since we allow negative affinities, then it is likely that many of the edges in the minimal cut will also be negative while edges inside coalitions in P ∗ will likely be positive. Therefore, it is unlikely that agents in B will actually be able to improve their utility compared to if they stay in S∗ i . Thus, we hypothesize that on many randomly generated graphs, the existence of such a blocking coalition, B, is rare.

7 Conclusion and FutureWork

In this paper we introduced coalitional affinity games, a family of non-transferable utility games that explicitly model the values that agents receive from being associated with others. In these games, an agent is interested in joining coalitions with agents for which it has high affinity, while avoiding coalitions that contain agents for which it has low affinity.

5 For both the core and weak core, the standard deviation for Gapmax was always less than 0.05 and for Gapmin it was always less than 0.2.

Given our model, we provided a characterization of the social-welfare maximizing coalition structure, and showed that it corresponds to the minimal k-cut of the underlying affinity graph. We then studied stability properties of affinity games using the core as the solution concept. We investigated the relationship between the core and social welfare and proposed a new measure, the stability gap, that represents the sacrifice in social welfare that is made in exchange for stability. We showed that for general affinity games, this sacrifice is unbounded. However, for a subclass of affinity games (symmetric affinity games), we showed that the bound is two.

There are several research directions we would like to pursue. First, our experimental results illustrated that for symmetric affinity games, the core was rarely empty. We are interested in general properties of random graphs and would like, if possible, to prove that with high probability, the core is non-empty. Second, our current model only captures affinities between pairs of agents. We would like to extend this so that affinities among groups of agents could be captured, thus modelling all hedonic games. Preliminary work using hypergraphs looks promising.