Subsidies, Stability, and Restricted Cooperation in Coalitional Games

1 Introduction

Transferable utility (TU) coalitional games are commonly used to model interactions where groups of agents differ in the profits that they can guarantee to themselves. Given that a particular coalition is formed (and specifically, the grand coalition of all agents), a key question that arises is how to allocate payments.

Various solution concepts have been suggested in recent decades, specifying desired allocations according to criteria of stability and fairness. Due to the increasing ubiquity of automated agents, and in pursuit of cooperative behavior among self-interested entities, such solutions are being studied and applied in multiple areas of AI research (recent papers include [Conitzer and Sandholm, 2006; Dang et al., 2006; Malizia et al., 2007]).

As a motivating example, consider three companies, A, B, and C, interested in a cooperative advertising campaign. Expected profit increases as more companies cooperate (e.g., due to exposure in multiple media). A joint effort by all three companies will result in a total profit of $12 Million (the value of the coalition {A,B,C}). Alternatively, the campaign can be carried out by just A and B (with profit of $10M), or each company can choose to advertise alone (with profit of $4M).

Enrico Malizia

D.E.I.S. Universit`a della Calabria Rende, Italy emalizia@deis.unical.it

If companies are to cooperate, they must decide how to share the resulting profits.

The core is one of the earliest and most attractive solution concepts, and it directly addresses the issue of stability. The core contains all payment allocations (called imputations) that are stable, in the sense that no subgroup of agents could gain more by "breaking away" from the grand coalition; that is, the payment allocated to the agents of every coalition is at least that coalition's value.

Unfortunately, in many TU games (including our example above) the core is empty, and the game is inherently unstable, as there is always a sub-coalition that is better off apart. Several relaxations of the core have been proposed in order to maintain stability in games with empty cores. One prominent approach is to assume that departing from the grand coalition incurs some cost to the deviating agents, i.e., that coalitions will be satisfied with a payoff that is slightly lower than their value. The least core aims to capture the minimal relaxation in coalitions' demands that will enable a stable imputation.

An alternative assumption is that certain coalitions are unlikely to form due to social reasons or other practical limitations (e.g., it may be difficult for a large coalition to coordinate its deviation). Such restrictions can take many forms, and generally make the game more stable, as fewer coalitions are likely to deviate from a proposed allocation. If companies A and B cannot cooperate without C, then the core in our previous example becomes non-empty (by allocating $4M to each of the companies).

Whereas the two previous relaxations depend on the environment or on the behavior of the agents themselves, a different approach is to stabilize the game with an external monetary intervention. By subsidizing particular outcomes of the game, for example the formation of the grand coalition, an external authority can induce stability. While the injection of sufficiently large subsidies can always guarantee a non-empty core (e.g., if every agent gets more than the highest value in the game), one would naturally like to minimize the intervention. The minimal subsidy that stabilizes the coalitional game is known as its Cost of Stability (CoS), and the set of now-stable imputations is called the extended core [Bachrach et al., 2009a]. In our advertising example, a subsidy of $2M allows us to allocate $5M to A, $5M to B, and $4M to C, thereby achieving full cooperation with a stable allocation.

The value of the least core (i.e., the minimal demand relaxation) and the cost of stability can both serve as measures of the (in)stability of a given game. This paper answers certain natural questions regarding the conceptual and quantitative relationship between these measures. We prove tight bounds on the ratio between the minimal subsidy (the CoS) and the minimal demand relaxation that each stabilizes the game. In addition, we measure the amount by which several natural restrictions on coalitions reduce the cost of stability.

Related work Subsidies have been proposed by several researchers, using different models and names. The reader is referred to the papers mentioned below for additional useful references and motivating examples.

Our work follows the model suggested by Bachrach et al. [2009a], which studied bounds and computational aspects of the CoS, focusing on the family of weighted voting games. That initial work has been extended by several other researchers [Resnick et al., 2009; Meir et al., 2010; Aziz et al., 2010], who addressed the computation of the CoS in various families of TU games, including Network Flow games, Graph games, Connectivity games, Anonymous games, and others.

A model for subsidies was independently suggested by Bejan and G´omez [2009], who focused (as we do) on the relationship between subsidies and other solution concepts. We adopt some of their notation, which is useful in our case as well. However, in their work the additional payment required to stabilize a game is gathered from the participating agents by means of a specific taxation system, rather than injected into the game by an external authority. We do not assume any form of taxation.

Particular attention has been devoted in Economics to subsidies in expense sharing games, where agents share the cost of a project, rather than its profits (see, for example, [Immorlica et al., 2005; Devanur et al., 2005]). Despite some small differences between the models, restricted cooperation can be similarly defined and studied in expense games, although we are unaware of such work.

Restrictions on the cooperation structure have also been studied extensively, where the specific restriction may depend on the particular application (see [Myerson, 1977; Faigle, 1989; Algaba et al., 2001; Pulido and SanchezSoriano, 2006]). While the interaction with many solution concepts (including the core) has been explicitly addressed, we are unaware of previous work that aims to quantify the affect of such restrictions on stability.

Paper structure Section 2 provides some notation, and gives the formal definition of the Cost of Stability. In Section 3 we compute worst-case bounds on the CoS of TU games with restricted interactions. Our main results are in Section 4, where we study the relationship between the extended core and the least core. We prove tight bounds on the ratio between the minimal subsidy and the minimal relaxation that are each sufficient to stabilize the game, thereby improving on the results of Bachrach et al. [2009a]. In the final section, we discuss the relationship to some other solution concepts, and propose future directions for research.

2 Preliminaries

We briefly present the definitions required for our model. A transferable utility (TU) coalitional game is defined by specifying the collective utility that can be achieved by every coalition of agents. Formally, G = 〈N, v〉, where N is a finite set of agents N = {1, . . . , n}, and v is a function v : 2N → R. For a singleton i ∈ N, we write v(i) instead of v({i}). The function v is called the characteristic function of the game. We assume by convention that v(∅) = 0. Also, we restrict our attention in this paper to positive, monotone games unless explicitly stated otherwise. That is v(S) ≥ 0 for all S, and v(S) ≥ v(S′ ) for all S′ ⊂ S.

A TU game is called simple if v(S) always equals either 0 or 1. Coalitions with v(S) = 1 are called winning coalitions. A TU game is superadditive if for all S, T ∈ 2N s.t. S ∩T = ∅, v(S ∪ T ) ≥ v(S) + v(T ).

A payoff vector x = (x1, . . . , xn) (also called a preimputation) divides the gains of the grand coalition among its members, where ∑i∈N xi = v(N). We call xi the payoff of agent i, and denote the payoff of a coalition S as x(S) = ∑i∈S xi. We denote the set of all preimputations in G by X(G).

A preimputation x ∈ X(G) is individually rational if no agent i can gain more than xi by itself, i.e., if xi ≥ v(i) for all i ∈ N. Individually rational preimputations are called imputations. Similarly, a coalition S ∈ 2N blocks x ∈ X(G), if x(S) < v(S). The core of G, denoted C(G), consists of all imputations that are not blocked by any coalition.

The least core Consider a game Gwith an empty core, and a value ϵ > 0. We define the weak ϵ-core of G as WCϵ(G) = {x ∈ X(G) : ∀S ∈ 2N , x(S) ≥ v(S) - ϵ|S|}. Clearly for a large enough ϵ, WCϵ(G) in not empty. We denote by ϵW(G) the smallest ϵ s.t. WCϵ(G) ̸= ∅. The ϵW-core of G is referred to as the weak least core, and denoted by WLC(G).

The strong ϵ-core is defined as SCϵ(G) = {x ∈ X(G) : ∀S ∈ 2N , x(S) ≥ v(S) - ϵ}, and we define ϵS(G) and the strong least core (SLC) accordingly.

The cost of stability Let Δ ≥ 0 be a payment that an external authority is willing to pay the grand coalition, in case such is formed. This induces a new game G(Δ) = 〈N, vΔ〉, s.t. vΔ(N) = v(N) +Δ. The value of all other coalitions remains unchanged. Clearly if Δ is large enough, then G(Δ) has a non-empty core (e.g., if Δ = n · v(N)). The Cost of Stability is defined as

The game induced by the minimal extra payment is denoted by G = G(CoS(G)) (which has a non-empty core).

A preimputation in G(Δ) is called a superimputation of G. A superimputation x′ is an extension of the preimputation x (denoted x′ ≥ x), if x′i ≥ xi for all i ∈ N. The extended core consists of all preimputations that can be extended to stable payoff vectors with minimal subsidy. Formally, EC(G) = {x ∈ X(G) s.t. ∃x′ ≥ x, x′ ∈ C(G)}.

In general, we define for any x ∈ X(G) its cost of stability, as the smallest payment required to extend x to a stable payoff vector, i.e.,

Clearly CoS(x, G)≥CoS(G), with equality iff x∈EC(G). The extended core in our initial example contains p = (5, 5, 2), which can be extended to the (minimal) stable superimputation (5, 5, 4). In contrast, p′ =(3, 4, 5) /∈ EC(G), as CoS(p′ , G) = 3 > 2 = CoS(G).

2.1 Balanced collections and linear programs

The CoS can also be formulated in a closed form, using the Bondareva-Shapley characterization of the core. We use a variant of the theorem that will be used later in Section 4.

Definition 1. Let D be a collection of coalitions, and denote by δS ∈ R+ the coefficient of coalition S. We say that D is a balanced collection if there are {δS}S∈D, such that for every agent i, ∑S∈D:i∈S δS = 1.

A balanced collection D is called minimal, if there is no D′ ⊊D s.t. D′ is balanced.

Theorem 1 (Bondareva-Shapley Theorem). The core of G is non-empty iff all [minimal] 1 balanced collections hold ∑S∈D δSv(S) ≤ v(N).

By a simple continuity argument, it follows that in G there is at least one [minimal] collection, for which the above holds with an equality. Such collections are called solutions of G. It is easy to verify that for any game G with empty core,

Another way to define the game G is by a linear program, where ∑i∈N xi should be minimized, and every constraint corresponds to a coalition (see [Bachrach et al., 2009a]). The solutions of the dual linear program (whose variables correspond to coefficients of coalitions), coincide with the solutions of G. See [Gilles, 2010] for a detailed discussion on balanced collections, and a proof of Theorem 1.

The relative CoS It is sometimes convenient to treat the external payment as a relative fraction of v(N) (as we do in Section 3). We therefore define the Relative Cost of Stability as

Note that the transformation is straightforward, as RCoS(G) = v(N)+CoS(G) v(N) . Trivial bounds on the RCoS are 1 ≤ RCoS(G) ≤ n, and these are tight.

3 Games with Restricted Coalitions

Suppose that there is some given subset of coalitions T ⊆ 2N that can deviate (we assume T contains all singletons). Given a game G = 〈N, v〉 and a restriction T , we define the restricted game G|T = 〈N, v|T 〉, where v|T (S) = v(S) if S ∈ T , and 0 otherwise. We emphasize that the restrictions are given exogenously to the game, and do not depend on the value function or the structure of the game.

Clearly, the more we restrict allowed coalitions, the fewer the constraints on allowed imputations, and therefore the core can only expand. This means that such restrictions can only decrease the CoS of the game. We now consider how some natural restrictions affect the (relative) CoS of the game.

1 There are versions with/without the minimality requirement.

1. Only coalitions of size at most k are allowed, i.e., T = {S ∈ 2N : |S| ≤ k}.
2. N is divided according to some fixed partition P = {C1, C2, . . . , Ck}, and T = {S ∈ 2N : S ⊆ Cj}.
3. Relations between agents are described by a (nondirected) communication graph (N,E). A coalition S is allowed only if the subgraph (S, E|S) is connected.

The third restriction was proposed by Myerson [1977], motivated by the approach that members of a coalition in a society are not allowed to communicate through non-members. Note that the second restriction is a special case of the third, where the graph is a block graph.

Example 1. Consider a simple game G with 5 agents, where every coalition of size at least 3 wins, and the coalition of the first two agents also wins. Without restrictions, the RCoS of G is 1 23 (we have to pay 13 to each agent). We can now observe how each of the restrictions affects the RCoS. Let T1 where only coalitions of size 2 are allowed, then C(G|T1 ) ̸= ∅ by paying 12 to each of the first two agents. Now, suppose that in T2 we partition the agents to C1 = {1, . . . , 4} and C2 = {5}. The core is still empty, but RCoS(G|T2 ) = 1 13 . Finally, assume that T3 is a communication graph. If T3 is a cycle, then the RCoS remains unchanged. If T3 is a line, then C(G|T3 ) ̸= ∅ (we can pay 1 to the middle node).

Without further assumptions on the game, restricting the coalitions does not give a better bound on the CoS (in the worst case): consider a simple game G = 〈N, v〉 where all nonempty coalitions win; then RCoS(G|T ) = n even if only singletons are allowed in T . We therefore consider only superadditive games, as in Example 1 (i.e., the original value function v is superadditive). Superadditivity is known to induce more stability. For example, it has been shown that if a game is superadditive and its set of coalitions T is restricted to an acyclic communication graph, then its core is non-empty [Demange, 2004] (i.e., it has RCoS of 1). Further, the following is known.

Theorem 2 ([Bachrach et al., 2009a]). Let G be a superadditive TU game (even without restrictions); then CoS(G) ≤ (√n - 1) v(N). Equivalently,

and this bound is tight (up to a small additive constant).

Proposition 3. For any superadditive TU game G:

1. If T ={S∈2N : |S|≤k}, thenRCoS(G|T )≤min{k,√n}. Also, for k=2 a stable superimputation with cost 2 can be found using a greedy algorithm.
2. If T is restricted to subsets of a partition P, then RCoS(G|T ) ≤ maxC∈P √|C|.
3. If T is restricted to a communication graph which has a single cycle, then RCoS(G|T ) ≤ 2.

Moreover, all bounds are tight (up to a small additive constant in 1. and 2.).

Proof. We prove each case separately.

Bounded coalition size, k = 2. We construct a superimputation p using the following algorithm.

Let S1={a1, a2} be the most expensive coalition in T .

find the most expensive coalition in T containing xt,

end for

First, observe that p is a stable superimputation. Let S = {a, b} be any coalition. If S was selected in some iteration, then either a or b gets the value of S and would therefore not participate. If S was not selected, then there is some St with v(St) ≥ v(S), and St contains one of a, b. Thus one of them is paid v(St) and would not participate in S.

It is left to prove that p(N) ≤ 2v(N). Clearly p(N) = ∑i∈N p(i) = ∑nt=1 v(St). Think of {St}nt=1 as nodes in a graph, where an edge connects two coalitions if they intersect. Since St is only connected to St-1 and St+1 (when they exist) we get a bipartite graph (L,R), where L contains all coalitions St with odd t, and R with even t. Coalitions inside L and R are pairwise disjoint. From superadditivity we have that p(N) holds

i.e., at most 2v(N).

While the greedy algorithm supplies us with a stable superimputation whose value is at most 2v(N), it is possible to do better (see next paragraph).

Bounded coalition size, k > 2. If k ≥ √n then by Theorem 2 we are done. Assume therefore k < √n. Consider a balanced collection D which is a solution of G.

Lemma 4 ([Bachrach et al., 2009b]). If G is superadditive, then there is a solution D in which any two sets S, S′ ∈ D with nonzero coefficients intersect.

Thus take any coalition S ∈ D of size at most k with a nonzero coefficient δS. There must be such a set, otherwise all coefficients are 0 (which means we can find a better solution to the dual program).

For tightness, let q = k - 1 and nq = k2 - 1 = q2 + q + 1. Take a game Gq = 〈Nq, vq〉 s.t. |Nq| = nq, and CoS(Gq) > √nq - 1 (such a game exists by the tightness example in Theorem 2). We now embed Gq in a game G = 〈N, v〉, where N = Nq ∪ {k2 , . . . , n}. Set v(N) = vq(Nq), v(S) = vq(S) if S ⊆ Nq, and v(S) = 0 otherwise. We thus have CoS(G) = CoS(Gq) > √nq - 1 > k - 1.

Using Lemma 4, it can be shown that when k = 2, CoS(G|T ) ≤ 1.5 (which is tight).

Partitions Take any C ∈ P, and the linear constraints induced by its subcoalitions. From Theorem 2 we can satisfy these constraints by paying at most p(C) ≤ √|C|v(C). We set the payoffs of each set C independently in the same manner. As there are no further constraints, p is stable. Also

where the last inequality is due to superadditivity of v.

A single cycle We construct a stable superimputation p′ , by paying v(N) to an arbitrary node in the circle, and solve the remaining game as a tree (using Demange's algorithm [Demange, 2004]). While this solution is quite simple, for the worst case it is asymptotically tight. We generalize the example given earlier as follows:

Consider a simple anonymous game where a coalition wins iff its size is at least ⌈(n + 1)/2⌉, and a communication graph with n nodes connected in a circle. Since the game is symmetric, we have pi = pj = p, and for smallest winning coalitions S, v(N) = v(S) ≤ p(S) = |S|p = ⌈(n + 1)/2⌉ p. that is, p(N) = np, which equals either (2 - 2 n+2 )v(N) (for odd n), or (2 - 1 n+1 )v(N) (for even n). ■

The lower bound example not only has coalitions of size k, but can also be embedded in a communication graph of degree k. We conjecture that this always holds, i.e., that RCoS(G|T ) ≤ d(T ), where d is the degree of the communication graph of T .

4 CoS and the Least Core

In this section we study the quantitive relation between the CoS and the Least core in coalitional games (not necessarily restricted ones). We use the following lemma (for a proof, see [Gilles, 2010]).

Lemma 5. Any minimal balanced collection has a size of at most n, and a unique set of balancing coefficients.

As an immediate corollary we get the following result, which has been independently shown by Malizia et al. [2007] using the geometric properties of the core.

Corollary 6. If the core of G is empty, then there is a set of coalitions of size at most n that are sufficient to determine the emptiness of the core.

The strong least core It trivially holds (see [Bachrach et al., 2009b]) that

While the upper bound is tight (consider a game where v(S) = 1 for all S ̸= ∅), it can be improved when the game is superadditive, as we will see next.

For the results in this section, we use the following construction. Given a game with an empty core G and ϵ =

ϵS(G), define a new game Gϵ = 〈N, vϵ〉, where vϵ(S) = v(S) - ϵ for all S ⊊ N, and vϵ(N) = v(N). Clearly C(Gϵ) = SCϵ(G) = SLC(G).

Theorem 7. For any superadditive game G, CoS(G) ≤ √n · ϵS(G), and this bound is tight.

Note that we can derive the √n bound that appears in Theorem 2, since ϵS(G) ≤ v(N).

We make use of the following lemma. The proof is omitted, but it uses techniques similar to those in [Bachrach et al., 2009b].

Lemma 8. Let 〈D, {δS}S∈D〉 be a balanced collection, then ∑S∈D δS ≤ √n.

Proof of Theorem 7. From Lemma 4, there is a balanced collection 〈D, {δS}S∈D〉 in which any two sets S and S′ with δS ̸= 0 and δS′ ̸= 0 intersect, and v(N) + CoS(G) = ∑S∈D δSv(S).

Since D is balanced, it must hold by Theorem 1 that

and by combining the last equation and (1),

From (4) and the lemma,

The tightness follows from the tightness of Theorem 2. That is, there is a game G in which CoS(G) ≥ (√n - O(1)) v(N) ≥ (√n - O(1)) ϵS(G). ■

Our main result is showing that the lower bound can be improved in the general case. We begin with a simple example. Consider the case of n = 2, and suppose there is an empty core. This simply means that v(1) + v(2) > v(1, 2). If we define z = v(1, 2) - (v(1) + v(2)), then we can easily see that CoS(G) = z = 2ϵW(G) = 2ϵS(G). With more agents, this ratio is generalized as follows.

Theorem 9. Let G be a game with an empty core. CoS(G) ≥ n n-1 ϵS(G), and this bound is tight.

Proof. For tightness, it is sufficient to consider a simple game where all coalitions of size at least n - 1 win.

Let G be a game with an empty core. Consider the strong least core of G, i.e., SLC(G). Let ϵ = ϵS(G).

Recall the game Gϵ. Similarly to the argument used in Section 2.1, there is a solution of Gϵ (a minimal balanced collection) 〈K, {δS}S∈K〉 s.t.

W.l.o.g. N /∈ K. Assume otherwise; then either K = {N} or {N} = K′ ⊊ K in contradiction to the minimality of K. However, if K = {N} is the only balanced collection with equality, then G can be stabilized with ϵ′ = 0 < ϵ, which is a contradiction to the minimality of ϵ = ϵS(G).

For all i ∈ N, 1 = ∑S∈K:i∈S δS. Summing over i ∈ N,

By definition, vϵ(S) = v(S) - ϵ, thus

By Equations (1) and (6),

Theorem 9 establishes a quantitative relationship between the CoS and the strong least core. However, the relationship could be deeper.

Conjecture 10. For any game G, SLC(G) ⊆ EC(G).

In other words, we conjecture that preimputations in the least core are the easiest to stabilize: for any x ∈ SLC(G), CoS(x, G) = CoS(G).

For small games, the conjecture indeed holds.

We have already seen that when n = 2, SLC(G), WLC(G) coincide, and are contained in EC(G). For n = 3 there is only a small number of minimal balanced collections, and we can simply go over all the possibilities. We again omit the full proof due to space constraints.

The weak least core In the weak ϵ-core, every agent in every coalition agrees to lower her demand by ϵ. Instead, we can increase the payoff of each agent by the same amount (see [Bejan and G´omez, 2009]); thus CoS(G) = n · ϵW(G).

Clearly, this means that WLC(G) ⊆ EC(G), as any preimputation z ∈ WLC(G) can be extended to a stable superimputation by adding ϵ to every coordinate.

Moreover, this tight relation allows us to conclude the following bounds from Theorems 7 and 9.

Corollary 13. For any superadditive game,

ϵS(G) ≥ √n · ϵW(G).

5 Discussion

We showed that various restrictions on the interaction of agents can significantly reduce the cost of stability in (superadditive) TU games. While we focused on profit games, we note that similar results hold when we impose restrictions on expense sharing games (as in [Meir et al., 2010]).

We established a tight lower bound for the CoS, in terms of the minimal relaxation that defines the least core. The upper bound is also improved, but only under conditions of superadditivity. Indeed, superadditive games have many attractive properties related to stability and to its computational aspects (see [Conitzer and Sandholm, 2006; Bachrach et al., 2009a; Demange, 2004]).

The nucleolus One difficulty with solution concepts such as the core and its variations is that even when they exist, they usually do not specify a unique imputation.

A unique solution that is highly motivated by the notion of stability is the nucleolus and its variations. Informally, the nucleolus is the preimputation that minimizes the dissatisfaction of all coalitions, sorted according to a certain lexicographic order (see, for example, [Bejan and G´omez, 2009] for definitions). Like any other preimputation, we can always stabilize the nucleolus by extending it with sufficient subsidies to a stable superimputation. Aziz et al. [2010] offered an alternative way to achieve a stable nucleolus: first extend the core, then compute the nucleolus in the extended game. For the percapita nucleolus, both solutions coincide, i.e., the per-capita nucleolus of the extended game G is an extension of the percapita nucleolus of G. This arises simply by adding ϵW(G) to every coordinate of the per-capita nucleolus, which is contained in the WLC.

It is an open problem whether the (standard) nucleolus N(G) has similar properties. Indeed, since it is contained in the SLC, we have that CoS(N(G),G) = CoS(G) in every game for which Conjecture 10 holds. We further conjecture that N(G) is a minimal extension of N(G), which is not entailed by the previous conjecture.

Future directions While our results indicate that there is a tight connection between the extended core and other solution concepts, there are many open questions for future research. Beyond the conjectures that we explicitly stated, it would be interesting to explore these relationships in specific families of TU games, such as those that were mentioned in the introduction.

While in the general case (non-superadditive) restricted cooperation cannot guarantee improved stability, it may dramatically reduce required subsidies in certain limited families of TU games. Such combinations are worth studying. In addition, the analysis in this paper can be extended to the CoS of coalition structures (as in Bachrach et al. [2009a]) and to expense games (as in Meir et al. [2010]).

Finally, the relation between the CoS and similar solution concepts in non-TU games (such as the strong price of anarchy) should be studied.

Acknowledgments

This work was partially supported by Israel Science Foundation grant #898/05, the Israel Ministry of Science and Technology grant #3-6797, and the Google Inter-University Center for Electronic Markets and Auctions.