# Subordinated Hedonic Games

Authors: Juan Carlos Cesco
Journal: Game Theory
 (2013)

---

## 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.


---

## Body

## 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 coalitionS 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 gamesubordinated 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 setN={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 (N,⪰^;𝒜), where 𝒜⊆𝒩 is a nonempty family and ⪰^=(⪰^i)i∈N is a preference profile with ⪰^i, for any i∈N, being a reflexive, complete, and transitive binary relation on 𝒜(i). For any i∈N, ≻^i will stand for the strict preference relation related to ⪰^i(S≻^iT if and only if S⪰^iT but not T⪰^iS). 𝒫𝒜(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(N,⪰^;𝒜) and π∈𝒫𝒜(N), we say that T∈𝒜blocksπ if, for any i∈T, T≻^iπ(i). The core C(N,⪰^;𝒜) of (N,⪰^;𝒜) is the set of partitions in 𝒫𝒜(N) blocked by no coalition. In a game (N,⪰^;𝒜), 𝒜 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 ⪰^i(≻^i) 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 (N,⪰^;𝒜), 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 ∑S∋iS∈ℬλS=1, 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 coalitionsF𝒜⊆𝒩, ℐ=(ℐ(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.
(
N
,
⪰
^
;
𝒜
) is ordinally balanced if for each balanced family ℬ⊆𝒜 there is a partition π∈𝒫𝒜(N) such that, for any i∈N,π(i)⪰^iB for some B∈ℬ(i).
Ordinal balancedness is first stated by Bogomolnaia and Jackson [7] for the case 𝒜=𝒩.Definition 4.
(
N
,
⪰
^
;
𝒜
) is pivotally balanced with respect to an 𝒜-distribution ℐ, if for each ℐ-balanced family ℬ⊆𝒜 there is a partition π∈𝒫𝒜(N) such that, for any i∈N, π(i)⪰^iB 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(N,⪰^;𝒜) be a hedonic game with 𝒜 as its family of admissible coalitions. Then, the core of (N,⪰^;𝒜) 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){1,2}≻{1,3}≻{1,2,3}≻{1},{1,2}≻{2,3}≻{1,2,3}≻{2},{3}≻{1,3}≻{2,3}≻{1,2,3}.
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)ℐ({1,2,3})={1,2},ℐ({1,2})={1,2},ℐ({1,3})={3},ℐ({2,3})={3},ℐ({i})={i}∀i=1,2,3.
The family 𝒜={{1},{2},{3},{1,2}} describes the set of essentially different coalitions in the distribution ℐ. Moreover, if we consider the game (N,⪰^;𝒜) where ⪰^ is restriction of ⪰ to the family 𝒜, namely, if
(3){1,2}≻^{1},{1,2}≻^{2},{3}⪰^{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 (N,⪰^;(A)) 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){1,2,3,4}≻{1}≻{1,2}≻{1,3}≻{1,4}≻{1,2,3}≻⋯,{1,2,3,3}≻{2,3,4}≻{2,3}≻{2}≻⋯,{1,2,3,4}≻{3,4}≻{3}≻{2,3}≻{3,4}≻{2,3,4}≻⋯,{1,2,3,4}≻{3,4}≻{2,4}≻{4}≻{1,2,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 (N,⪰^;𝒜), 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)𝒜(ℐ)={S∈𝒩:S=ℐ(T)forsomeT∈𝒩}
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 (N,⪰^;𝒜) 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(N,⪰^;𝒜) is included in the core of (N,⪰).(b)
If, for anyS∈𝒩 such that S∉𝒜(S≠ℐ(T) for any T⊆N), ℐ(S)≻iSfor any i∈ℐ(S), then the core of (N,⪰^;𝒜) is the same as the core of (N,⪰).Proof.
Letπ∈C(N,⪰^;𝒜). 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)S≻iπ(i).
But, because of subordination,
(7)ℐ(S)⪰iS
for all i∈ℐ(S). Then, for any i∈ℐ(S),
(8)ℐ(S)≻iπ(i),
and since ⪰^ is the restriction of ⪰ to 𝒜, from (8) we get that
(9)ℐ(S)≻^iπ(i)
for all i∈ℐ(S). But this indicates that ℐ(S) objects π in (N,⪰^;𝒜), a contradiction. Thus, C(N,⪰^;𝒜)⊆C(N,⪰).
To see part (b), let us assume thatπ=(π1,…,πs)∈C(N,⪰)∖C(N,⪰^;𝒜). 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 C(N,⪰)=C(N,⪰^;𝒜).In general, the reverse inclusion of that stated in (a) does not hold, mainly because some core partitions in(N,⪰) are not 𝒜-partitions in (N,⪰^;𝒜). 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 C(N,⪰^;𝒜). 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 (N,⪰^;𝒜) 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)ℐ({1,2,3})={1,3},ℐ({1,2})={1},ℐ({1,3})={1},ℐ({2,3})={3},ℐ({i})={i}foranyi=1,2,3.
Then 𝒜=𝒜(ℐ)={{1},{2},{3},{1,3}}. Let the preference profile ⪰ in (N,⪰) have preferences for players 1, 2, and 3 given by
(11){1}≻{1,2}⪰{1,3}⪰{1,2,3},{1,2}⪰{2,3}⪰{1,2,3}⪰{2},{3}≃{1,3}≃{2,3}⪰{1,2,3}.
Consequently, the preference profile ⪰^ defined on 𝒜 in the associated game (N,⪰^;𝒜) is
(12){1}≻^{1,3},{2}≃^{2},{3}≃^{1,3}.
It is easy to check that the only core partition of (N,⪰^;𝒜) 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 Theorem10 is sufficient for the coincidence of the cores of (N,⪰) and (N,⪰^;𝒜), 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){2}≻{1,2}⪰{2,3}⪰{1,2,3}.
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 (N,⪰^;𝒜).
Finally, when subordination is not present, we can say nothing about the inclusion stated in part (a) of Theorem10 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){1,2,3}≻{1,2}≻{2,3}≻{2}.
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 (N,⪰^;𝒜) 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, letN={1,2,3}, and let (N,⪰) a hedonic game with the preferences of players 1, 2, and 3 given by
(15){1,2,3}≻{1,2}≻{1,3}≻{1},{1,2,3}≻{1,2}≻{2,3}≻{2},{1,2,3}≻{3}≻{1,3}≻{2,3}.
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 (N,⪰^;𝒜) is equal to the corresponding game for the game (N,⪰) in Example 7, so its only core partition is π={{1,2},{3}}. Then C(N,⪰^;𝒜) is not included in C(N,⪰) in this case.
In the light of Theorem10, any condition guaranteeing the nonemptiness of the core of the game (N,⪰^;𝒜) (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 (N,⪰^;𝒜) 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 (N,⪰^;𝒜) 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 (N,⪰^;𝒜) 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 (N,⪰^;𝒜). Thus, there is an 𝒜-partition π such that, for each i∈N, π(i)⪰^iB′ 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.
Theorem10, 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 (N,⪰^;𝒜). 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 Proposition14 is no longer true when ordinal balancedness for the game (N,⪰^;𝒜) 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){1,2}≻{1,3}≻{1,2,3}≻{1},{1,2}≻{2,3}≻{1,2,3}≻{2},{1,3}≻{2,3}≻{1,2,3}≻{3}.
The only core partition in (N,⪰) is π={{1,2},{3}}. If ℐ is the distribution given by
(17)ℐ({1,2,3})={2,3},ℐ({1,2})={1,2},ℐ({1,3})={1,3},ℐ({2,3})={2,3},ℐ({i})={i}∀i=1,2,3,
then 𝒜=𝒜(ℐ)={{1},{2},{3},{1,2},{1,3},{2,3}}. The associated hedonic game (N,⪰^;𝒜) 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(N,⪰^;𝒜) 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 anyS∈𝒩, ℐk(S)⊆ℐk-1(S), there is a first k′=k′(S), k′≥1, such that ℐk′(S)=ℐk′-1(S). Now, for any S∈𝒩, we define ℐ′(S)=ℐ(ℐk′-1(S)). Then, for any S∈𝒩 we have that
(18)ℐ′(ℐ′(S))=ℐ′(ℐ(ℐk′-1(S)))=ℐ′(ℐk′(S))=ℐ(ℐk′-1(S))=ℐ′(S).
Moreover, for any givenS∈𝒩 and since the game (N,⪰) is subordinated to ℐ, we have that
(19)ℐ′(S)⪰iℐk′-1(S)⪰i⋯⪰iS,
for any i∈ℐ′(S), so the game (N,⪰) is also subordinated to ℐ′.In the game of Example17, ℐ′=ℐ.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 (N,⪰^;𝒜′) with 𝒜′=𝒜(ℐ′). We note that for any coalition S∈ℐ′ it holds that ℐ′(S)=S. Thus if (N,⪰^;𝒜′) 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 (N,⪰^;𝒜) is ordinally balanced or not, there is still another instance to get information about the core of the original game through the simpler game (N,⪰^;𝒜′). 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)≻iS for any S∉𝒜′, i∈ℐ(S).Example8 shows that a game (N,⪰) can be pivotally balanced with respect to a distribution ℐ with 𝒜=𝒜(ℐ), while the associated reduced game (N,⪰^;𝒜) is not pivotally balanced. Thus, in this case, there seems to be no information in the game (N,⪰^;𝒜) 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 (N,⪰^;𝒜) 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 C(N,⪰^;𝒜). 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 Theorem10.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 (N,⪰^;𝒜). 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 distribution ℐ, 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 (N,⪰^;𝒜) 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 tof 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 (N,⪰^;𝒜) 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 (N,⪰^;𝒜).
(c) First we are going to show that(N,⪰^;𝒜) 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 Proposition25 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(N,⪰^;𝒜) 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)γ(S;i)=S,
and for any S∉𝒜, i∈S let
(21)γ(S;i)=S*,
with S*∈{T∈𝒜(i):T⊆S} satisfying T⪰^iS* for all T∈{T∈𝒜(i):T⊆S}.Definition 30.
A partitioning hedonic game is a hedonic game(N,⪰) for which there exists a germ (N,⪰^;𝒜) such that, for any i∈N,⪰i is defined as:
(22)foranyS,T∈𝒜(i),S⪰iTiffS⪰^iT,foranyS∈𝒜(i),T∈𝒩(i)∖𝒜,S≻iT,foranyS,T∈𝒩(i)∖𝒜,S⪰iTiffγ(S;i)⪰^iγ(T;i).
Let us use (N,⪰∣𝒜) to denote a hedonic partitioning game with 𝒜 as its family of essential coalitions. We note that the associated reduced game (N,⪰^;𝒜) 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, C(N,⪰∣𝒜)=C(N,⪰^;𝒜), where (N,⪰^;𝒜) 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 C(N,⪰∣𝒜)=C(N,⪰^;𝒜).


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

As a simple but interesting consequence of Theorem31, 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 setsM 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 eachm∈M, if μ(m)≠m, then μ(m)∈W.(b)
For eachw∈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 (N,⪰^;𝒜) with 𝒜 as its family of admissible coalitions where, for each i∈N,⪰^i is defined on 𝒜(i) as follows. If i=m for some m∈M,S⪰^iT if and only ifS∩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.Ifi=w for some w∈W, S⪰^iT if and only ifS∩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 anyi∈N, we also declare that S⪰iT when |S|=|T|=1.With each partitionπ in the game (N,⪰^;𝒜), 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 (N,⪰^;𝒜), the associated game to the marriage problem. Therefore, the set of stable matchings of (M,W,⪰M,⪰W) is always nonempty.Proof.
From Theorem31 we have that C(N,⪰∣𝒜)=C(N,⪰^;𝒜) is nonempty. We claim that μπ is a stable matching for each core partition π in (N,⪰^;𝒜). 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, π(m)⪰^mm, and according to the definition ⪰^m 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 S≻^mπ(m) when μπ(m)≠m (|π(m)|=2). We also get that S≻^mπ(m) when π(m)=m (|π(m)|=1). In a similar way we obtain that m≻wμπ(w) implies that S≻^wπ(w) 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 (N,⪰^;𝒜) 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.


## 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 tof 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 (N,⪰^;𝒜) 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 (N,⪰^;𝒜).
(c) First we are going to show that(N,⪰^;𝒜) 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 Proposition25 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(N,⪰^;𝒜) 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)γ(S;i)=S,
and for any S∉𝒜, i∈S let
(21)γ(S;i)=S*,
with S*∈{T∈𝒜(i):T⊆S} satisfying T⪰^iS* for all T∈{T∈𝒜(i):T⊆S}.Definition 30.
A partitioning hedonic game is a hedonic game(N,⪰) for which there exists a germ (N,⪰^;𝒜) such that, for any i∈N,⪰i is defined as:
(22)foranyS,T∈𝒜(i),S⪰iTiffS⪰^iT,foranyS∈𝒜(i),T∈𝒩(i)∖𝒜,S≻iT,foranyS,T∈𝒩(i)∖𝒜,S⪰iTiffγ(S;i)⪰^iγ(T;i).
Let us use (N,⪰∣𝒜) to denote a hedonic partitioning game with 𝒜 as its family of essential coalitions. We note that the associated reduced game (N,⪰^;𝒜) 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, C(N,⪰∣𝒜)=C(N,⪰^;𝒜), where (N,⪰^;𝒜) 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 C(N,⪰∣𝒜)=C(N,⪰^;𝒜).


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

As a simple but interesting consequence of Theorem31, 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 setsM 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 eachm∈M, if μ(m)≠m, then μ(m)∈W.(b)
For eachw∈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 (N,⪰^;𝒜) with 𝒜 as its family of admissible coalitions where, for each i∈N,⪰^i is defined on 𝒜(i) as follows. If i=m for some m∈M,S⪰^iT if and only ifS∩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.Ifi=w for some w∈W, S⪰^iT if and only ifS∩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 anyi∈N, we also declare that S⪰iT when |S|=|T|=1.With each partitionπ in the game (N,⪰^;𝒜), 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 (N,⪰^;𝒜), the associated game to the marriage problem. Therefore, the set of stable matchings of (M,W,⪰M,⪰W) is always nonempty.Proof.
From Theorem31 we have that C(N,⪰∣𝒜)=C(N,⪰^;𝒜) is nonempty. We claim that μπ is a stable matching for each core partition π in (N,⪰^;𝒜). 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, π(m)⪰^mm, and according to the definition ⪰^m 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 S≻^mπ(m) when μπ(m)≠m (|π(m)|=2). We also get that S≻^mπ(m) when π(m)=m (|π(m)|=1). In a similar way we obtain that m≻wμπ(w) implies that S≻^wπ(w) 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 (N,⪰^;𝒜) 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.



---

*Source: 512742-2013-07-29.xml*