Game Theory
Volume 2013, Issue 1 512742
Research Article
Open Access

Subordinated Hedonic Games

Juan Carlos Cesco, 

Corresponding Author

Juan Carlos Cesco

Instituto de Matemática Aplicada San Luis (UNSL-CONICET), Avenida Ejército de Los Andes 950, 5700 San Luis, Argentina unsl.edu.ar

Departamento de Matemática (UN San Luis), Chacabuco y Pedernera, 5700 San Luis, Argentina unsl.edu.ar

Search for more papers by this author
First published: 29 July 2013
https://doi.org/10.1155/2013/512742
Academic Editor: Walter Briec

Abstract

Hedonic games are simple models of coalition formation whose main solution concept is that of core partition. Several conditions guaranteeing the existence of core partitions have been proposed so far. In this paper, we explore hedonic games where a reduced family of coalitions determines the development of the game. We allow each coalition to select a subset of it so as to act as its set of representatives (a distribution). Then, we introduce the notion of subordination of a hedonic game to a given distribution. Subordination roughly states that any player chosen as a representative for a coalition has to be comfortable with this decision. With subordination we have a tool, within hedonic games, to compare how a “convenient” agreement reached by the sets of representatives of different groups of a society is “valued” by the rest of the society. In our approach, a “convenient” agreement is a core partition, so this paper is devoted to relate the core of a hedonic game with the core of a hedonic game played by the sets of representatives. Thus we have to tackle the existence problem of core partitions in a reduced game where the only coalitions that matter are those prescribed by the distribution as a set of representatives. We also study how a distribution determines the whole set of core partitions of a hedonic game. As an interesting example, we introduce the notion of hedonic partitioning game, which resembles partitioning games studied in the case where a utility, transferable or not, is present. The existence result obtained in this new class of games is later used to provide a nonconstructive proof of the existence of a stable matching in the marriage model.

1. Introduction

Coalitional games are models which take into account the interaction between the players of the game. In general, any subgroup of players (a coalition) can influence the result of the game. However, it has been recognized that, sometimes, some of the coalitions can completely determine the development of the game. In their seminal paper, Kaneko and Wooders [1] introduce the class of partitioning games as a way to capture the fact that “In an n-cooperative game it may not be equally easy to form every coalition.” In those games, only a subset of coalitions play such an essential role that determines the behavior of all the other coalitions. This characteristic is shared for several of the games studied in the literature such as the marriage game [2], the bridge game [3], the assignment game [4], and the m-sided assignment game [5] among others. Kaneko and Wooders [1] present a transferable utility version for partitioning games and a nontransferable utility version as well and focus on the nonemptiness of the core of the games. As a key contribution, they provide a list of necessary and sufficient conditions to characterize a class of families of coalitions under which any possible induced partitioning game has nonempty core, a property motivated by the behavior exhibited by the assignment game. We point out that the essential coalitions in the well-known marriage game of Gale and Shapley [2] satisfy those conditions, although none of the versions of the games presented by Kaneko and Wooders [1] suit well to deal with the existence of a stable matching. Hedonic games [6, 7], which constitute another class of games, have received considerable attention in the last decade and seem to be more appropriate to deal with matching problems than coalitional games where a utility is present. A hedonic games (N, ⪰) is a simple model of coalition formation determined by a set of n players N and a profile of preferences ⪰  = (⪰1, …, ⪰n) where, for any i = 1, …, n, ⪰i is an ordering of the coalitions containing player i. The main solution concept for a hedonic game is that of core partition, namely, a partition of the set of players that is resistant to a certain class of objections raised by the coalitions in the game (Section 2). There are several sufficient conditions for the existence of core partitions, being those of top-coalition properties [6], consecutiveness, and ordinal balancedness [7] among the most well known. Iehlé [8] gives a complete answer to the existence problem in a general setting by introducing the notion of pivotal balancedness. To define pivotal balancedness first it is associated one of its subsets to each coalition S. Iehlé [8] calls this family of subsets a distribution. Iehlé′s condition states that a hedonic game has nonempty core if and only if there is a distribution such that the game is pivotally balanced with respect to this distribution (see Section 2). Thus, checking this condition is a two-step procedure. First, a distribution has to be considered, and then, the balancedness condition has to be verified.

On the other hand, in many situations, different groups in a society choose a subgroup to act as their representatives. Then, the agreements (if any) reached by the groups of representatives are imposed, one way or the other, to the whole society. An interesting issue is whether a “convenient” agreement for the representatives is also good for the rest of the society. With this idea in mind, we note that a set of representatives for a coalition S can be taken as an element ℐ(S) of a distribution ℐ, a relation that builds a bridge between our objective and a well-developed mathematical framework. We also point out that, although the notion of pivotally balancedness works very well to deal with the general existence problem of core partitions in hedonic games, it does not reflect to which extent a family of coalitions of representatives determines the behavior of the game. For instance, if a family ℐ of coalitions of representatives (a distribution) plays a reduced game where the only admissible coalitions are those in ℐ, an interesting issue is to look for relationships, if any, between the cores of both games. For instance, if π is a core partition in the reduced game (an agreement between the groups of representatives), is also π a core partition (a good agreement for the whole society) in the original game? Answers to this problem could help, at least, in two dimensions to the treatment of hedonic games. First, since we start with a distribution, the first step in the two-step procedure mentioned above is simplified. Second, in order to get core partitions in the original game, one can solve a reduced and possibly simpler game.

Unfortunately, as several examples show, there are no general results. What is missing is the description of some connection, apart from inclusion, between a coalition and its set of representatives. To tackle this point, we appeal to the notion of a hedonic game subordinated to a distribution. In order to deal with the reduced game played by the coalitions of representatives we present some results about a hedonic game with a restricted family of admissible coalitions. They are simple extensions of the main existence results proved by Iehlé [8]. Pápai [9] has already used the idea of restrict the family of feasible coalitions to get uniqueness results about core partitions in hedonic games, while the idea of subordination (Section 3) seems to be new. Subordination in a game (N, ⪰) roughly states that any player chosen as a representative of a coalition has to be comfortable with this decision. This is formalized by asking that if ℐ(S) stands for the set of representatives of a coalition S, then ℐ(S)⪰iS for any i ∈ ℐ(S). Subordination involves some degree of anonymity on the individual preferences, although it is weaker than the common ranking property [10] or the top-coalition condition [6]. When subordination is present, a balancedness condition has to be checked only on the family of representatives to guarantee the existence of core partitions. Moreover, under mild additional conditions, the family of representatives determines completely the core of the hedonic game.

The organization of the paper is as the following. In the next section, we present our version of hedonic games where some restrictions on the family of admissible coalitions are imposed. They are a straightforward extension of hedonic games as stated by Banerjee et al. [6] and Bogomolnaia and Jackson [7] where there is no restriction on the family of admissible coalitions. For this enlarged class of hedonic games we state two balancedness conditions extending those of ordinal balancedness of Bogomolnaia and Jackson [7] and pivotal balancedness of Iehlé [8]. Following those authors, we show that both conditions are sufficient to guarantee the existence of core partitions, while pivotal balancedness is also a necessary condition. In Section 3 we study the issue of subordination. The idea behind subordination is that, given a reduced family of coalitions, along with a profile of preferences, there are games whose core behavior is determined by this basic information. We state some sufficient conditions to guarantee the existence of core partitions and to guarantee that the core of the whole game is fully determined by the basic information given on a reduced family of coalition as well. Several examples and counter examples are also shown there. In Section 4 we relate subordination to other sufficient conditions guaranteeing the existence of core partitions in hedonic games like top-coalition properties [6] and consecutiveness [7]. At the end of this section, we introduce the notion of partitioning hedonic game. They always have a family of essential coalitions associated, and we prove that every partitioning game has nonempty core if the family of essential coalitions satisfies either condition (ii) or the equivalent condition (iii) of Theorem 2.7 of Kaneko and Wooders [1]. We use the results about hedonic partitioning games to elaborate a nonconstructive proof of the existence of a stable matching in the marriage game [2] different from the proof provided by Sotomayor [11]. To this end, we associate a partitioning hedonic game to each marriage problem, so that results in Section 4 can be used. We include a final Appendix where we sketch the existence proof of core partitions in hedonic games with a restricted family of admissible coalitions very similar to that of Theorem 3 of Iehlé [8].

2. Hedonic Games

To define a hedonic game, we start with a nonempty finite set N = {1, …, n}, the players, and its family 𝒩 of nonempty subsets, the coalitions. Given any family of coalitions 𝒜⊆𝒩 and a player i ∈ N, we denote by 𝒜(i) the subfamily of coalitions in 𝒜 containing player i. A hedonic game is a 3-tuple , where 𝒜⊆𝒩 is a nonempty family and is a preference profile with , for any i ∈ N, being a reflexive, complete, and transitive binary relation on 𝒜(i). For any i ∈ N, will stand for the strict preference relation related to if and only if but not .  𝒫𝒜(N) will denote the family of partitions π = {π1, …, πs} of N such that πj ∈ 𝒜 for any j = 1, …s. Given π = {π1, …, πs} ∈ 𝒫𝒜(N) and i ∈ N, π(i) will denote the unique set in π containing player i.

Given a hedonic game and π ∈ 𝒫𝒜(N), we say that T ∈ 𝒜 blocks π if, for any i ∈ T, . The core of is the set of partitions in 𝒫𝒜(N) blocked by no coalition. In a game , 𝒜 is the family of admissible coalitions. The most studied case in the literature is 𝒜 = 𝒩, namely, when there is no restriction on the set of admissible coalitions (see, e.g., [6–8]). When this is the case, we will omit 𝒜 from all the notation, and we will use ⪰i (≻i) instead of to denote the individual (strict) preference of a player i ∈ N. The case 𝒜 ≠ 𝒩, as stated in this paper, has already been used by Cesco [12] to study some existence result in many-to-one matching problems.

Definition 1. A nonempty collection 𝒜⊆𝒩 such that {i} ∈ 𝒜 for any i ∈ N is called essential.

Families with such a characteristic have been used by Kaneko and Wooders [1], Quint [5], and Le Breton et al. [13] among others to study the existence of core solutions in games where a restricted family of coalitions determines the behavior of the whole game. From now on, when dealing with a hedonic game , we will assume that the family 𝒜 is essential.

A family of coalitions ℬ⊆𝒩 is balanced if there exists a collection of positive real numbers (λS) S∈ℬ satisfying , for all i ∈ N. The numbers (λS) S∈ℬ are the balancing weights for ℬ. ℬ is minimal balanced if there is no proper balanced subfamily of it. In this case, the set of balancing weights is unique. A family of essential coalitions is 𝒜-partitionable [1] if and only if the only minimal balanced subfamilies that it contains are partitions.

Definition 2. Given a nonempty family of coalitions F𝒜⊆𝒩, ℐ = (ℐ(A)) A∈𝒜 is an 𝒜-distribution if, for each coalition A ∈ 𝒜, ℐ(A) ∈ 𝒜 and ℐ(A)⊆A. In addition, an 𝒜-distribution is simply called a distribution when 𝒜 = 𝒩.

Given an 𝒜-distribution ℐ, a family ℬ⊆𝒜 is ℐ-balanced if the family (ℐ(B)) B∈ℬ is balanced.

Definition 3. is ordinally balanced if for each balanced family ℬ⊆𝒜 there is a partition π ∈ 𝒫𝒜(N) such that, for any for some B ∈ ℬ(i).

Ordinal balancedness is first stated by Bogomolnaia and Jackson [7] for the case 𝒜 = 𝒩.

Definition 4. is pivotally balanced with respect to an 𝒜-distribution ℐ, if for each ℐ-balanced family ℬ⊆𝒜 there is a partition π ∈ 𝒫𝒜(N) such that, for any i ∈ N, for some B ∈ ℬ(i). The game is pivotally balanced if it is pivotally balanced with respect to some 𝒜-distribution ℐ.

This general concept of pivotal balancedness was introduced by Iehlé [8] for the case 𝒜 = 𝒩.

Remark 5. Ordinal balancedness implies pivotal balancedness with respect to the 𝒜-distribution ℐ = (χA) A∈𝒜, where χA stands for the indicator vector of the coalition A, namely, when χA is the n-dimensional vector with χA(j) = 1 if player j belongs to A and χA(j) = 0 if player j does not belong to A.

The following result is a simple extension of the main characterization proved by Iehlé [8, Theorem 3] and whose proof is carried out in a similar way. However, for the sake of completeness, we sketch the proof in the Appendix.

Theorem 6 (see Iehlé [8].)Let be a hedonic game with 𝒜 as its family of admissible coalitions. Then, the core of is nonempty if and only if the game is pivotally balanced.

3. Subordinated Games

As a motivation for the content of this section, let us start with an example which is a slight modification of Game 5 of Banerjee et al. [6].

Example 7. Let (N, ⪰) be a hedonic game with N = {1,2, 3} and where the preferences for players 1,2, and 3 are given in the three lines below (in this example and in the following ones as well, we will omit the subscript i in the symbol describing the preference of player i to avoid misleading):

(1)
The only core partition in (N, ⪰) is π = {{1,2}, {3}}. According to Iehlé [8, Proposition 1], (N, ⪰) is pivotally balanced with respect to the distribution ℐ given by
(2)
The family 𝒜 = {{1}, {2}, {3}, {1,2}} describes the set of essentially different coalitions in the distribution ℐ. Moreover, if we consider the game where is restriction of ⪰ to the family 𝒜, namely, if
(3)
are the restricted preferences for players 1, 2, and 3, respectively, then it is easy to check that π is also the only core partition of this game with a restricted family of admissible coalition.

In this example, the game (N, ⪰) is pivotally balanced with respect to the family (A), and this family determines completely the core of the game in the sense that the core of the reduced game coincides with that of (N, ⪰). However, as the following example shows, there can be no relation at all between the core of a hedonic game and the core of a reduced game related to one of the distributions the game is pivotally balanced to.

Example 8. Let the (N, ⪰) be a game with N = {1,2, 3,4} and with preferences for players 1, 2, 3, and 4 given by

(4)
respectively. This game is pivotally balanced since π = {{1,2, 3,4}} is clearly a core partition in (N, ⪰). Moreover, according to Iehlé [8, Proposition 1], the game is pivotally balanced with respect to the distribution ℐ, where ℐ(S) = S for any S with |S| < 4 and ℐ({1,2, 3,4}) = {1,2, 3}. In this case, 𝒜 coincides with the family of all coalitions with cardinality less than four. However, in the associated game , it is a simple exercise to check that there is a blocking coalition in 𝒜 for any of the fifteen 𝒜-partitions that this game have. Therefore, this game has no core partition.

The aim of this section is to explore more deeply these kind of relationships. To this end we start by defining what we mean by a subordinated game.

Definition 9. A hedonic game (N, ⪰) is subordinated to a distribution ℐ when, for any i ∈ N and any S ∈ 𝒩(i), ℐ(S)⪰iS whenever ℐ(S) contains player i.

The game (N, ⪰) in Example 7 is subordinated to the distribution ℐ showed there.

We point out that, for any given distribution ℐ in a hedonic game (N, ⪰), the family
(5)
is an essential family of coalitions since ℐ({i}) = {i}, and therefore, {i} ∈ 𝒜 for any i ∈ N.

When subordination is present, the behavior of the coalitions in a distribution determines, to some extent, the core of a hedonic game. The next result illustrates this point. Given a hedonic game (N, ⪰) and a distribution ℐ, let be the hedonic game having 𝒜 = 𝒜(ℐ) as its family of admissible coalitions and where is the restriction of ⪰ to 𝒜.

Theorem 10. Let (N, ⪰) be a hedonic game subordinated to a distribution ℐ with 𝒜 = 𝒜(ℐ). Then,

  • (a)

    the core of is included in the core of (N, ⪰).

  • (b)

    If, for any S ∈ 𝒩 such that S ∉ 𝒜 (S ≠ ℐ(T) for any T⊆N), ℐ(S)≻iS

for any i ∈ ℐ(S), then the core of is the same as the core of (N, ⪰).

Proof. Let . We will show that π ∈ C(N, ⪰) too. Clearly, there is no S ∈ 𝒜 objecting π. So, let us assume that there is S ∉ 𝒜 objecting π. Then, for each i ∈ S, we have that

(6)
But, because of subordination,
(7)
for all i ∈ ℐ(S). Then, for any i ∈ ℐ(S),
(8)
and since is the restriction of ⪰ to 𝒜, from (8) we get that
(9)
for all i ∈ ℐ(S). But this indicates that ℐ(S) objects π in , a contradiction. Thus, .

To see part (b), let us assume that . Then, for at least one j = 1, …, s, πj ∉ 𝒜. Let T = ℐ(πj). Then, for each i ∈ T, T≻iπj. Thus, T is an objection to π, a contradiction proving that .

In general, the reverse inclusion of that stated in (a) does not hold, mainly because some core partitions in (N, ⪰) are not 𝒜-partitions in . On the other hand, we note that the game in Example 7 is a subordinated game for which condition (b) of Theorem 10 holds, which supports the equality between the core of (N, ⪰) and that of . However, in general, the inclusion in (a) of Theorem 10 is strict as Example 8 shows. Furthermore, the inclusion can be strict even though the core of is nonempty. The next example illustrates this point.

Example 11. Let (N, ⪰) be a hedonic game with N = {1,2, 3}, and let ℐ be the distribution given by

(10)
Then 𝒜 = 𝒜(ℐ) = {{1}, {2}, {3}, {1,3}}. Let the preference profile ⪰ in (N, ⪰) have preferences for players 1, 2, and 3 given by
(11)
Consequently, the preference profile defined on 𝒜 in the associated game is
(12)
It is easy to check that the only core partition of is π = ({1}, {2}, {3}). Thus, while π is still a core partition in (N, ⪰), it is also simple to check that π* = ({1}, {2,3}) is a core partition in (N, ⪰) too.

While condition (b) of Theorem 10 is sufficient for the coincidence of the cores of (N, ⪰) and , respectively, when subordination is present, the next example shows that it is not necessary.

Example 12. Let (N, ⪰) and ℐ be like in Example 11. We now replace the individual preference of player 2 by the following one:

(13)
Then, although this new game does not satisfy condition (b) of Theorem 10, it is easy to check that π = ({1}, {2}, {3}) is the only core partition in both games (N, ⪰) and .

Finally, when subordination is not present, we can say nothing about the inclusion stated in part (a) of Theorem 10 as the two games in the next example show.

Example 13. Let us start with the game (N, ⪰) and the same distribution ℐ used in Example 7. We now modify the individual preference of player 2 as follows:

(14)
Then the game with preference profile with this new preference for player 2 is no longer subordinated to the distribution ℐ since ℐ({1,2, 3}) = {1,2}, but {1,2}⋡{1,2, 3} for player 2. Nevertheless, its only core partition is still π = {{1,2}, {3}}. On the other hand, the associated game coincides with that of Example 7. Then, its only core partition is π = {{1,2}, {3}} too, and the inclusion stated in part (a) of Theorem 10 is verified although subordination is not present.

Now, let N = {1,2, 3}, and let (N, ⪰) a hedonic game with the preferences of players 1, 2, and 3 given by

(15)
The only core partition in (N, ⪰) is π′ = {{1,2, 3}}. Now, let ℐ be the same distribution used in Example 7. Again, since ℐ({1,2, 3}) = {1,2} but {1,2}⋡{1,2, 3} for player 2, (N, ⪰) is not subordinated to ℐ. Also, the game is equal to the corresponding game for the game (N, ⪰) in Example 7, so its only core partition is π = {{1,2}, {3}}. Then is not included in C(N, ⪰) in this case.

In the light of Theorem 10, any condition guaranteeing the nonemptiness of the core of the game (e.g., pivotal balancedness) will be a sufficient condition for the nonemptiness of the subordinated game (N, ⪰) to ℐ. Thus, the nonemptiness of the core of implies the pivotal balancedness of (N, ⪰), although Theorem 10 does not exhibit a family 𝒜 such that the game (N, ⪰) be pivotally balanced with respect 𝒜. However, if we impose on the more strict condition of ordinal balancedness, then we can also exhibit, easily, such a distribution.

Proposition 14. Let (N, ⪰) be a hedonic game subordinated to a distribution ℐ with 𝒜 = 𝒜(ℐ). If is ordinally balanced, then (N, ⪰) is pivotally balanced with respect to the distribution ℐ.

Proof. Let ℬ be an ℐ-balanced family of coalitions in (N, ⪰). Then, the family {ℐ(B)} B∈ℬ is balanced. Since for each B ∈ ℬ, ℐ(B) ∈ 𝒜, {ℐ(B)} B∈ℬ is also balanced in . Thus, there is an 𝒜-partition π such that, for each i ∈ N, for some B′∈{ℐ(B)} B∈ℬ, with B′ containing player i. However, since (N, ⪰) is subordinated to ℐ, we get that π(i)⪰iℐ(B)⪰iB for some B∈ℬ such that ℐ(B) = B′.

Corollary 15. Let (N, ⪰) be a hedonic game subordinated to a distribution ℐ with 𝒜 = 𝒜(ℐ). If 𝒜 is partitionable then (N, ⪰) is pivotally balanced with respect to the distribution ℐ.

Remark 16. Theorem 10, Proposition 14 and its Corollary 15 are related to a given game (N, ⪰) and a distribution ℐ. Hence we derive the family 𝒜 = 𝒜(ℐ) of essential coalitions and the reduced game . If we start with a family 𝒜 of essential coalitions and (N, ⪰) is now any hedonic game (N, ⪰) subordinated to a distribution ℐ such that 𝒜 = 𝒜(ℐ), those results can be extended to a whole family of games.

The result in Proposition 14 is no longer true when ordinal balancedness for the game is replaced by pivotal balancedness as Example 17 shows.

Example 17. Let us consider Game 5 of Banerjee et al. [6], which is the game (N, ⪰) with N = {1,2, 3} and where the individual preferences for players 1, 2, and 3 are given by

(16)
The only core partition in (N, ⪰) is π = {{1,2}, {3}}. If ℐ is the distribution given by
(17)
then 𝒜 = 𝒜(ℐ) = {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}}. The associated hedonic game is not ordinally balanced. In fact, the family ℬ = {{1,2}, {1,3}, {2,3}} is 𝒜-balanced. However, for any π ∈ 𝒫𝒜(N) in this game, there is always a player i that strictly prefers the worst coalition he belongs to in ℬ to π(i). For instance, if π = {{3}, {1,2}}, player 3 strictly prefers either {1,3} or {2,3} to π(3) = {3}. On the other hand, it is easy to check that (N, ⪰) is subordinated to 𝒜, but, clearly, it is not pivotally balanced with respect to ℐ. Nevertheless, since its core is nonempty, it is pivotally balanced with respect to another distribution (see [8]).

Even when we do not have much more information about the game and consequently we are not aware whether Proposition 14 applies or not, there is still a procedure that can be useful to gather information about the game (N, ⪰) in many cases.

Definition 18. Given a hedonic game (N, ⪰) and a distribution ℐ, we say that a distribution ℐ′ is finer than ℐ if ℐ′(S)⊆ℐ(S) for any S ∈ 𝒩.

We point out that when a distribution ℐ satisfies that ℐ(S) = S for all S, then pivotal balancedness and ordinal balancedness coincide.

In the next result we are going to use the following notation. Given a distribution ℐ, for any S ∈ 𝒩, and for any natural number k, let ℐk(S) = ℐ(ℐk−1(S)). We agree in putting ℐ0(S) = S.

Lemma 19. Given a hedonic game (N, ⪰) subordinated to a distribution ℐ with 𝒜 = 𝒜(ℐ), there is a finer distribution ℐ′ than ℐ with ℐ′(ℐ′(S)) = ℐ′(S) for any S ∈ 𝒩 and such that (N, ⪰) is also subordinated to the distribution ℐ′.

Proof. Since, for any S ∈ 𝒩, ℐk(S)⊆ℐk−1(S), there is a first k′ = k′(S), k′ ≥ 1, such that . Now, for any S ∈ 𝒩, we define . Then, for any S ∈ 𝒩 we have that

(18)

Moreover, for any given S ∈ 𝒩 and since the game (N, ⪰) is subordinated to ℐ, we have that

(19)
for any i ∈ ℐ′(S), so the game (N, ⪰) is also subordinated to ℐ′.

In the game of Example 17, ℐ′ = ℐ.

The rationale behind the definition of distribution ℐ′ is that the set of representatives of a coalition S(ℐ(ℐ(S))) can also be a set of representatives of S. What subordination implies is that if the members of a coalition want to represent a set of representatives of a coalition S (ℐ(ℐ(S))⪰iℐ(S) for all i ∈ ℐ(ℐ(S))) then they are willing to represent the coalition S too. We point out that, since always ℐ(ℐ(S))⊆ℐ(S), the distribution ℐ′ is endowed with a certain minimality property. Namely, for any S ∈ 𝒩, ℐ′(S) is the smaller set (with respect to inclusion) that it is able to act as a representative of coalition S, according to the rules of selection of representatives prescribed by the distribution ℐ. Moreover, ℐ′(S) is defined in a unique way. Under the hypothesis of Lemma 19, we can consider the game with 𝒜′ = 𝒜(ℐ′). We note that for any coalition S ∈ ℐ′ it holds that ℐ′(S) = S. Thus if is ordinally balanced then, because of Proposition 14, (N, ⪰) is pivotally balanced with respect to the distribution ℐ′. Therefore, when subordination is present, wether we know that the game is ordinally balanced or not, there is still another instance to get information about the core of the original game through the simpler game . An interesting example is when the family 𝒜′ = {{i} : i ∈ N}. This case illustrates the situation where each coalition S is willing to admit a set with only one player as its set of representatives. Then, according to Theorem 10, the partition π = {{1}, …, {n}} is a core partition in (N, ⪰). Moreover, if for any S, |S| > 1, and i ∈ ℐ′(S) there is 1 ≤ k ≤ k′(S) such that ℐk(S)≻iℐk−1(S), then π is the only core partition in (N, ⪰), for in this case ℐ′(S) ≻i S for any S ∉ 𝒜′, i ∈ ℐ(S).

Example 8 shows that a game (N, ⪰) can be pivotally balanced with respect to a distribution ℐ with 𝒜 = 𝒜(ℐ), while the associated reduced game is not pivotally balanced. Thus, in this case, there seems to be no information in the game about the core of (N, ⪰). However, when subordination is present we obtain a positive result.

Definition 20. Given a hedonic game (N, ⪰), we say that a distribution ℐ with 𝒜 = 𝒜(ℐ) is tight if for any partition π ∈ 𝒫(N) there is a partition π* ∈ 𝒫𝒜(N) such that, for any i ∈ N, π*(i)⪰iπ(i).

Theorem 21. Let (N, ⪰) be a hedonic game subordinated to a tight distribution ℐ with 𝒜 = 𝒜(ℐ). Then, the core of is nonempty if and only if the core of (N, ⪰) is nonempty.

Proof. Let us assume first that π is a core partition in (N, ⪰). Since ℐ is tight, there is a partition π* ∈ 𝒫𝒜(N) such that π*(i)⪰iπ(i) for any i ∈ N. We claim that π* is a core partition in . If this was not the case, there would be S ∈ 𝒜 such that S⪰iπ*(i) ⪰iπ(i) for any i ∈ S, but then S would block π, a contradiction.

The other implication follows directly from part (a) of Theorem 10.

Remark 22. From the proof of the latter theorem, it follows that, when a game (N, ⪰) is pivotally balanced with respect to a tight distribution ℐ with 𝒜 = 𝒜(ℐ), the pivotal balancedness of (N, ⪰) always implies that of . However, when subordination is not present, this condition is not necessary as the second game in Example 13 illustrates. On the other hand, Example 8 shows a case of a pivotally balanced game (N, ⪰) with respect to a distribu tion ℐ, where the distribution ℐ is not tight and the the associated reduced game is not pivotally balanced. Thus, without “tightness,” the pivotal balancedness of a reduced game is independent of that of (N, ⪰).

Remark 23. When subordination is present in a game (N, ⪰), for any given partition π and any i ∈ N,  ℐ(π(i))⪰iπ(i). However, although ℐ(π(i)), i = 1, …, n, is an 𝒜-family of mutually exclusive sets, it is not, in general, a partition. Thus, tightness provides a related but stronger characteristic than subordination about the game.

4. Subordination and Other Sufficient Conditions

Subordination seems to be a strong condition capable of linking core properties of a hedonic game with core properties of some of its reduced games constructed based on a restricted family of coalitions. Many of the games studied in the literature share the characteristic that its behavior also depends on particular subfamilies of coalitions. The aim of this section is to relate some of these games to subordination.

4.1. Consecutive Games

Consecutive games were studied by Bogomolnaia and Jackson [7]. In order to define them, let N = {1,2, …, n} be a finite set and f : N → N a bijection, namely, an ordering on N. A coalition S ∈ 𝒩 is consecutive with respect to f if f(i) < f(k) < f(j) with i, j ∈ S implies that k ∈ S too.

Definition 24. A hedonic game (N, ⪰) is consecutive if there is an ordering f on N such that S⪰i{i} for some i ∈ N implies that S is consecutive with respect to f.

Proposition 25. Let (N, ⪰) be a consecutive game and f an ordering on N that makes the game consecutive. Then,

  • (a)

    (N, ⪰) is subordinated to the distribution ℐ defined by ℐ(S) = S if S is consecutive (with respect to f) and ℐ(S) = {i} for some i ∈ S if S is not consecutive.

  • (b)

    If 𝒜 = 𝒜(ℐ), the core of (N, ⪰) and the core of coincide.

  • (c)

    (N, ⪰) is pivotally balanced with respect to the distribution ℐ.

Proof. (a) Clearly ℐ(S)⪰iS for any i ∈ S when S is consecutive. On the other hand, ℐ(S) = {i}≻iS when S is not consecutive. Thus, (N, ⪰) is subordinated to ℐ.

(b) Since 𝒜 = 𝒜(ℐ) = {S ∈ 𝒩 : S is consecutive}, S ∉ 𝒜 implies that S is not consecutive, and thus, ℐ(S)≻iS for the unique element i of ℐ(S). Then, condition (b) of Theorem 10 also applies. So, the core of (N, ⪰) is the same as the core of .

(c) First we are going to show that is ordinally balanced. Let ℬ⊆𝒜 be a balanced family of coalitions. From Greenberg and Weber [14, Proposition 1], it follows that the family 𝒜 is partitionable, so (c) follows from Corollary 15.

Remark 26. We point out that part (c) of Proposition 25 has already been proven by Iehlé [8, Proposition 3]. Iehlé′s proof and ours are somehow different, but both are based on Proposition 1 of Greenberg and Weber [14].

4.2. Top-Coalition Property

The top-coalition property [6] is another well-known condition guaranteeing the existence of a core partition in a hedonic game (N, ⪰). It is also connected to subordination, as the following result shows. We recall that U ∈ 𝒩 is a top coalition of S ∈ 𝒩 if U⊆S and for any i ∈ U and T⊆S with i ∈ T, U⪰iT.

Definition 27. A hedonic game (N, ⪰) satisfies the top-coalition property if for any coalition U⊆N there is a top-coalition of U. One says that a distribution ℐ is a top-coalition distribution of (N, ⪰) if, for any S, ℐ(S) is a top-coalition of S.

Proposition 28. Let (N, ⪰) be a hedonic game satisfying the top-coalition property. Then, (N, ⪰) is subordinated to any top-coalition distribution ℐ.

Proof. It follows directly from the definition of ℐ.

Many of the examples presented in Banerjee et al. [6, Section 6] also satisfy the property that the top-coalition distribution chosen is ordinally balanced. However, unlike consecutive games, a hedonic game satisfying the top-coalition property may have core partitions although a top-coalition distribution is not, for instance, ordinally balanced. Let us see the following example.

Example 29. Let us consider Game 5 of Banerjee et al. [6] again (see  Example 13) but now with the distribution ℐ assigning ℐ(S) = S for any S with |S| < 3 and ℐ({1,2, 3}) = {1,2}. Then, ℐ(S) is a top coalition for any S. However, for ℬ = {{1,2}, {2,3}, {1,3}} there is no partition π such that, for any i = 1,2, 3, π(i)⪰iB for at least one B ∈ ℬ, whose members are elements of the family {ℐ(S)} S⊆N. In fact, any partition π has to contain a coalition with only one element. For this element i, it holds that i is not ⪰i for any of the coalitions of ℬ containing it. Of course, the game is not pivotally balanced with respect to ℐ either. However, the game is pivotally balanced with respect to the distributions ℐ′({1,2, 3}) = {1,2}, ℐ′({1,2}) = {1,2}, ℐ′({1,3}) = {3}, ℐ′({2,3}) = {3}, ℐ′({i}) = {i}, i = 1,2, 3 obtained from ℐ by the procedure described by Iehlé [8, Proposition 3].

4.3. Partitioning Hedonic Games

Hedonic partitioning games do not seem to have been studied from this approach before. Our motivation to study them comes from partitioning games as introduced by Kaneko and Wooders [1] in the context of cooperative games where a utility, transferable or not, is present. In addition, we also introduce this new class of games to have a tool to deal with matching problems from a game theoretic point of view. Partitioning games, as Kaneko and Wooders [1] show in their fundamental paper, take the idea that the development of a game can depend on a restricted family 𝒜 of coalitions to the utmost extreme. Not only the development of a particular game is completely determined by 𝒜 but also a whole class of games related to this family has its development prescribed by 𝒜. In partitioning games, the behavior of any coalition S outside the family 𝒜 is determined by its 𝒜-partitions.

In order to define a partitioning hedonic game, we start with a hedonic game with a restricted family 𝒜 of admissible coalitions which we will call the germ of the partitioning hedonic game. For any S ∈ 𝒜, i ∈ S, let
(20)
and for any S ∉ 𝒜, i ∈ S let
(21)
with S* ∈ {T ∈ 𝒜(i) : T⊆S} satisfying for all T ∈ {T ∈ 𝒜(i) : T⊆S}.

Definition 30. A partitioning hedonic game is a hedonic game (N, ⪰) for which there exists a germ such that, for any i ∈ N, ⪰i is defined as:

(22)
Let us use (N, ⪰∣𝒜) to denote a hedonic partitioning game with 𝒜 as its family of essential coalitions. We note that the associated reduced game to the partitioning game (N, ⪰∣𝒜) coincides with its germ.

Theorem 31. Let a partitionable essential family of coalitions 𝒜 be given. Then, every partitioning hedonic game (N, ⪰∣𝒜) has nonempty core. Moreover, , where is any germ of (N, ⪰∣𝒜).

Proof. Let ℐ be a distribution such that ℐ(S) = S for any S ∈ 𝒜, and ℐ(S) ∈ 𝒜 if S ∉ 𝒜. Clearly 𝒜 = 𝒜(ℐ). We claim that (N, ⪰∣𝒜) is subordinated to ℐ. In fact, for any S ∈ 𝒜, clearly ℐ(S) = S ⪰iS for any i ∈ ℐ(S). And if S ∉ 𝒜, ℐ(S)≻iS for any i ∈ ℐ(S) according to the construction of the preference ≻i. Since 𝒜 is partitionable [1] then, according to Corollary 15, the core of (N, ⪰∣𝒜) is nonempty. Moreover, since condition (b) of Theorem 10 also holds, we have that .

4.4. The Marriage Model: A Nonconstructive Proof of the Existence of Stable Matchings

As a simple but interesting consequence of Theorem 31, we derive a new nonconstructive (see also [11]) proof about the existence of a stable matching in the marriage model of Gale and Shapley [2]. To do this, we first associate a partitioning hedonic game to each marriage problem. Then, we will show that the core of the game is related to the set of stable matchings.

The marriage model consists of two finite sets of agents, the sets M of “men” and the set W of “women.” It is assumed that any man m ∈ M is endowed with a preference ⪰m over the set W ∪ {m} and that any woman w has a preference ⪰w on the set M ∪ {w}. Individual preferences are assumed to be reflexive, complete, and transitive on their corresponding domains. Let us denote by (M, W, ⪰M, ⪰W) a marriage problem, where ⪰M = (⪰m) m∈M and ⪰W  = (⪰w) w∈W are the preference profiles corresponding to the men and women.

A matching is a function μ : M ∪ W → M ∪ W satisfying the following.
  • (a)

    For each m ∈ M, if μ(m) ≠ m, then μ(m) ∈ W.

  • (b)

    For each w ∈ W, if μ(w) ≠ w, then μ(w) ∈ M.

  • (c)

    μ(μ(k)) = k for all k ∈ M ∪ W.

A matching μ is stable if μ(k)⪰kk for all k ∈ M ∪ W (individual stability) and if there is no pair m ∈ M, w ∈ W such that μ(m) ≠ w, μ(w) ≠ m, and w≻mμ(m) and m≻wμ(w) (pairwise stability). The pair (m, w) is called a blocking pair.

Given a marriage problem (M, W, ⪰M, ⪰W), let us consider the family 𝒜 = {S⊆M ∪ W : |S| = 2, |S∩M| ≤ 1, |S∩W| ≤ 1}. Clearly 𝒜 is essential. Moreover, it is a partitionable family as follows from the result of Kaneko and Wooders [1] about the existence of core points for every assignment game [4].

Given a marriage problem (M, W, ⪰M, ⪰W) let N = M ∪ W and 𝒜 as before. To such a problem, we associate the hedonic game with 𝒜 as its family of admissible coalitions where, for each is defined on 𝒜(i) as follows. If i = m for some if and only if
  •  

    S∩W⪰mT∩W when |S| = |T| = 2,

  •  

    S∩W⪰mm when |S| = 2 and T = 1,

  •  

    m⪰mT∩W when |S| = 1 and T = 2.

  •  

    If i = w for some w ∈ W, if and only if

  •  

    S∩M⪰mT∩M when |S| = |T| = 2,

  •  

    S∩M⪰mw when |S| = 2 and T = 1,

  •  

    w⪰mT∩M when |S| = 1 and T = 2.

For any i ∈ N, we also declare that S⪰iT when |S| = |T| = 1.

With each partition π in the game , we associate the matching μπ, where, for each m ∈ M, μπ(m) = π(m)∩W if |π(w)| = 2 and μπ(m) = m if |π(m)| = 1. Similarly, for each w ∈ W, μπ(w) = π(w)∩W if |π(w)| = 2 and μπ(w) = w if |π(w)| = 1.

Now, we are ready to state the following result.

Theorem 32. Let (M, W, ⪰M, ⪰W) be a marriage problem. Then, there is a one-to-one correspondence between the stable matchings of (M, W, ⪰M, ⪰W) and the core partitions of the partitioning game (N, ⪰∣𝒜) whose germ is , the associated game to the marriage problem. Therefore, the set of stable matchings of (M, W, ⪰M, ⪰W) is always nonempty.

Proof. From Theorem 31 we have that is nonempty. We claim that μπ is a stable matching for each core partition π in . To see this, let m ∈ M. If μπ(m) ≠ m, then |π(m)| = 2, and since π is a core partition, m cannot be strictly preferred to π(m). Thus, , and according to the definition this implies that π(m)∩W = μπ(m)⪰mm. A similar argument shows that, for each w ∈ W, μπ(w)⪰ww for any w ∈ W such that μπ(w) ≠ w. Then, μπ is individually stable.

On the other hand, let us assume that there is a blocking pair (m, w) to μπ. We claim that the coalition S = {m, w} objects the partition π, leading to a contradiction. Indeed, from w≻mμπ(m) we get that S∩W≻mμπ(m)∩W or, equivalently, that when μπ(m) ≠ m (|π(m)| = 2). We also get that when π(m) = m (|π(m)| = 1). In a similar way we obtain that m ≻w μπ(w) implies that showing that S blocks π. Thus, there is a one-to-one correspondence between the stable matchings of the marriage problem and the core partitions of which coincides with the core of the partitioning game C(N, ⪰∣𝒜).

Remark 33. When all men have identical preferences and all women have identical preferences as well (Becker [15] marriage game), Banerjee et al. [6] give an existence result also generating a hedonic game similar to our partitioning game. For this particular case they also reach a uniqueness result.

5. Conclusions

In this paper we introduce the concept of subordination in hedonic games. It is an appropriate tool to relate the core partitions of a game with the core partitions of a suitable derived subgame. We also extend to hedonic games the notion of partitioning games previously developed in cooperative games where a utility is present. We use results about subordination to show that a particular class of partitioning hedonic games behave pretty much in the same way as partitioning games behave in the class of cooperative games where a utility is present. As an interesting consequence we derive a new nonconstructive proof of the existence of stable matchings in the marriage model. Finally, in the sake of completeness, we present a proof of the existence of core partitions in hedonic games with a restricted family of admissible coalitions.

Acknowledgments

The author would like to thank CONICET and UNSL (Argentina) for their financial support.

    Appendix

    Proof of Theorem 6 (a sketch). Let π be a core partition in (N, ⪰, 𝒜). Then the game is pivotally balanced with respect to any 𝒜-distribution ℐ such that ℐ(S)⊆{i ∈ S : π(i)⪰iS} (see [8, Proposition 1]).

    To see the converse, we will parallel Iehle′s proof of Theorem 10 of the latter reference.

    Let us first take a utility profile for each i ∈ N, namely, a function ui : 𝒜(i) → ℝ such that ui(S) ≥ ui(T) if and only if S ⪰i T. Such a utility profile always exists. Now we construct an NTU-game (N, V; 𝒜) with the restricted family of admissible coalitions 𝒜 where, for any S ∈ 𝒜,  S ≠ N,

    (A.1)
    and, if Π is the family of all 𝒜-partitions of N,
    (A.2)
    We now show that if (N, ⪰, 𝒜) is pivotally balanced with respect to an 𝒜-distribution ℐ then, for any ℐ-balanced family of coalitions ℬ⊆𝒜, (N, ⪰, 𝒜) satisfies a generalized version of b-balancedness [16] for NTU-games with a restricted family of coalitions. We claim that this condition implies that there is x ∈ ∂V(N)∖int ⋃S∈𝒜V(S) (given a set S⊆Rn, ∂S and int S stand for the boundary and the interior of S, resp.). Such a point x is called a core-point in (N, V; 𝒜). To prove this claim, we will parallel the first part of Billera′s proof of Theorem 1 in Billera [16]. We note that, for any N ≠ S ∈ 𝒜, V(S) is generated, in the sense indicated by (A.1), by a unique vector , where if i ∈ S and if i ∉ S. We now construct the matrix M1, with rows indexed by the players in N, and the columns indexed by the members of 𝒜∖N and whose entries are given by
    (A.3)
    where is chosen such that for any N ≠ S ∈ 𝒜, i ∈ S. On the other hand, let M2 be another matrix with the same dimension as M1 and whose entries are given by
    (A.4)
    Namely, the columns of M2 are the indicator vectors of the coalitions in 𝒜 different from N. Since the family 𝒜 contains the individual coalitions and if m = |𝒜∖𝒩| (we note that m ≥ n), we have that the convex set
    (A.5)
    is bounded. So, we can apply a well-known result of Scarf [17, Theorem 2] to guarantee the existence of a subbasis (A subbasis for the linear system M2y ≤ χN is a set S1, …, Sk of linearly independent columns of M2 for which there is a vector y such that M2y ≤ χN, and yS = 0 for any S ≠ S1, …, Sk.)  S1, …, Sk for the linear system of inequalities so that if we define
    (A.6)
    then for each column S of M1 there is a row i of M1, satisfying such that
    (A.7)
    Therefore, the vector u = (ui) i∈N does not belong to int  V(S) for any S ∈ 𝒜∖𝒩. If we are able to show that u ∈ V(N), then any Pareto optimal point x ≥ u will be a core point in (N, V; 𝒜). To see this, we first note that, by construction, u ∈ V(Sj) for any j = 1, …, k. On the other hand, since S1, …, Sk is a subbasis, there is y = (yS) S∈𝒜∖𝒩 such that M2y ≤ χN and yS = 0 if S ≠ S1, …, Sk. We claim that, in fact, M2y = χN. Then, the subbasis S1, …, Sk contains a balanced subfamily ℬ. Since the game (N, V; 𝒜) satisfies the balancedness property and u ∈ V(S) for any S ∈ ℬ, we conclude that u ∈ V(N). We mention that the proof of the claim is the same given by Billera [16] during the proof of Theorem 6 for the case that the game is “finitely generated,” so we omit it here.

    To end the proof of the theorem we have to show that the existence of a core point x in (N, V; 𝒜) implies the existence of a core partition in (N, ⪰; 𝒜). Nevertheless, since x ∈ V(N), there is an 𝒜-partition π of N such that xi ≤ π(i) for any i ∈ N. We claim that π is a core partition in (N, ⪰; 𝒜). In fact, any blocking coalition S to π would imply that ui(S) > ui(π(i)) ≥ xi for any i ∈ S and thus that x ∈ int V(S), a contradiction.

    Remark 34. The proof of the existence of a core point given previously for a particular case of “finitely generated” NTU game with a restricted family of admissible coalitions can be extended, with minor modifications, to the general case of a “finitely generated” NTU game and later, following Billera [16], to a general NTU game (N, V; 𝒜) with a restricted family of admissible coalitions.

      The full text of this article hosted at iucr.org is unavailable due to technical difficulties.