Hedonic coalition formation games with variable populations: core characterizations and (im)possibilities

Abstract

We consider hedonic coalition formation games with variable sets of agents and extend the properties competition sensitivity and resource sensitivity (introduced by Klaus, Games Econ Behav 72:172–186, 2011, for roommate markets) to hedonic coalition formation games. Then, we show that on the domain of solvable hedonic coalition formation games, the Core is characterized by coalitional unanimity and Maskin monotonicity (see also Takamiya, Maskin monotonic coalition formation rules respecting group rights. Niigata University, Mimeo, 2010, Theorem 1). Next, we characterize the Core for solvable hedonic coalition formation games by unanimity, Maskin monotonicity, and either competition sensitivity or resource sensitivity (Corollary 2). Finally, and in contrast to roommate markets, we show that on the domain of solvable hedonic coalition formation games, there exists a solution not equal to the Core that satisfies coalitional unanimity, consistency, competition sensitivity, and resource sensitivity (Example 2).

1 Introduction

We consider hedonic coalition formation games with variable sets of agents. Hedonic coalition formation games are used to model economic and political environments where agents form coalitions; examples being the provision of public goods in local communities or the formation of clubs and organizations.

A hedonic coalition formation game consists of a finite non-empty set of agents and a list of agents’ preferences such that each agent’s preference relation strictly ranks the coalitions she is a member of. The dependence of an agent’s utility on the identity of members of her coalition is referred to as the “hedonic aspect” in Drèze and Greenberg (1980). The formal model of hedonic coalition formation games was introduced by Banerjee et al. (2001) and Bogomolnaia and Jackson (2002). Marriage markets and roommate markets (see Gale and Shapley 1962; Roth and Sotomayor 1990) are special cases of hedonic coalition formation games with coalitions of size one or two. Furthermore, hedonic coalition formation games are reduced forms of general coalition formation games where, for each coalition, the way its total payoff is to be divided among its members is fixed in advance and known to all agents.

Given a hedonic coalition formation game, an outcome is a partition of the set of agents (coalition structure), that is, a collection of pairwise disjoint coalitions whose union is equal to the set of agents. The existence of partitions that are stable in some sense is often a main concern. In this paper, we focus on core stability (see Sung and Dimitrov 2007; Karakaya 2011, for stability concepts studied in the literature). A partition is core stable if there is no coalition such that all its members strictly prefer it to the coalition they belong to. We say that a hedonic coalition formation game is solvable if it has at least one core stable partition.¹

A solution is a correspondence that associates each hedonic coalition formation game with a non-empty subset of partitions. On the domain of solvable hedonic coalition formation games, a solution is core stable if it only assigns core stable partitions, and the Core is the solution that always assigns all core stable partitions.

Takamiya (2010) considers a coalition formation problem that consists of a finite set of agents and a list of feasible coalitions that are allowed to be formed (a specification of the hedonic coalition formation model introduced by Pápai 2004). Every agent has (possibly weak) preferences over all feasible coalitions that contain herself. Takamiya (2010, Theorem 1) shows that under some assumptions on the domain of agents’ preferences, a solution is coalitionally unanimous² and Maskin monotonic³ if and only if it is the (strict) Core.⁴

We consider hedonic coalition formation games where every coalition is feasible and agents have strict preferences (in the remainder of this introduction we discuss our and previous results obtained under the strict preference assumption). We show that on the domain of solvable hedonic games, if a solution is coalitionally unanimous and Maskin monotonic, then it is a subsolution of the Core (Lemma 3a), and on the domain of all hedonic games, no solution is coalitionally unanimous and Maskin monotonic (Lemma 3b). The proof of Lemma 3 implies that the domain of solvable hedonic games is a maximal domain for the existence of a coalitionally unanimous and Maskin monotonic solution (Corollary 1).

Our first characterization result parallels Takamiya’s (2010, Theorem 1) result: on the domain of solvable hedonic coalition formation games (with strict preferences), the Core is characterized by coalitional unanimity and Maskin monotonicity (Theorem 1). Both results (Takamiya 2010, Theorem 1; Theorem 1) extend results by Toda (2006, Lemmas 3.3 and 3.5 imply a similar characterization) for marriage markets. For marriage markets, a similar characterization is obtained by replacing Maskin monotonicity with consistency⁵ (Toda 2006, Lemmas 3.4 and 3.6), but this result does not hold for hedonic coalition formation games: for hedonic coalition formation games, Example 1 specifies a solution not equal to the Core satisfying coalitional unanimity and consistency.

Klaus (2011) introduced the properties competition sensitivity⁶ and resource sensitivity⁷ for roommate markets as an extension to population monotonicity as used in marriage markets (see Toda 2006). Then, Klaus (2011, Theorem 1) shows that on the domain of solvable roommate markets the Core is characterized by (weak) unanimity, Maskin monotonicity, and either competition sensitivity or resource sensitivity. We show that these results also hold for solvable hedonic coalition formation games by showing that coalitional unanimity in Theorem 1 can be replaced with unanimity,⁸ and either competition sensitivity or resource sensitivity, i.e., unanimity, Maskin monotonicity, and either competition sensitivity or resource sensitivity characterize the Core on the domain of solvable hedonic coalition formation games (Corollary 2). However, on the domain of all hedonic coalition formation games, no solution satisfies unanimity, Maskin monotonicity, and either competition sensitivity or resource sensitivity (Theorem 2). With these results relying on Lemma 3 (and its proof) it follows that the domain of solvable hedonic games is a maximal domain for the existence of a unanimous, Maskin monotonic, and either competition sensitive or resource sensitive solution (Corollary 3).

Can and Klaus (2013) show that on the domain of solvable roommate markets the Core is characterized by (weak) unanimity, consistency, and either competition sensitivity or resource sensitivity. However, these results cannot be extended to hedonic coalition formation games, i.e., we show that on the domain of solvable hedonic coalition formation games, there exists a solution not equal to the Core that satisfies coalitional unanimity, consistency, competition sensitivity, and resource sensitivity (Example 2).

Our paper is organized as follows. In Sect. 2 we present the hedonic coalition formation model, basic properties of solutions, and the Core. In Sect. 3, we introduce the variable population properties competition sensitivity, resource sensitivity, and consistency. Section 4 contains our results.

2 Hedonic coalition formation, basic properties, and the core

Let $\mathbb {N}$ be the set of potential agents and $\mathcal {N}$ be the set of all non-empty finite subsets of $\mathbb {N}$, i.e., $\mathcal {N}=\{N\varsubsetneq \mathbb {N}\mid \infty>|N|>0\}$. For any $N\in \mathcal {N}$, a nonempty subset H of N is called a coalition of N. For each $N\in \mathcal {N}$ and each $i\in N$, by $\Sigma ^{N}_{i}=\{H\subseteq N\mid i\in H\}$ denote the set of all coalitions of N containing agent i.

For $N\in \mathcal {N}$, and $i\in N$, $L(\Sigma ^{N}_{i})$ denotes the set of all linear orders over $\Sigma ^{N}_{i}$.⁹ For $i\in N$ and $\succeq _i\in L(\Sigma ^{N}_{i})$, given $S,T\in \Sigma ^{N}_{i}$, $S\succ _i T$ means that agent i strictly prefers S to T and $S\succeq _i T$ means that $S\succ _i T$ or $S=T$ and that agent i weakly prefers S to T; e.g., for $S,T,U\in \Sigma ^{N}_{i}$, [$\succeq _{i}:S\succ _{i}T\succ _{i}\{i\}\succ _{i}U\succ _{i}\ldots$] means that i would first like to be a member of S, then of T, and then i would prefer to stay alone rather than being a member of the coalition U, etc. For a coalition H with $i\in H$, if $H\succ _{i}\{i\}$, then agent i finds coalition H acceptable and if $\{i\}\succ _{i}H$, then agent i finds coalition H unacceptable.

For any $H\subseteq N\in \mathcal {N}$, $i\in H$, and $\succeq _{i}\in L(\Sigma ^{N}_{i})$, $Ch_{i}(H,\succeq _{i})=\{T\in \Sigma ^{H}_{i} \mid T\succeq _{i}S$ for every $S\in \Sigma ^{H}_{i}$} denotes agent i’s choice set from coalition H (based on preferences $\succeq _{i}$). Since agents have strict preferences, $|Ch_{i}(H,\succeq _{i})|=1$.

We denote the set of all preference profiles of agents in N by $\mathcal {R}^N=\prod _NL(\Sigma ^{N}_{i})$. A hedonic coalition formation game, or simply a hedonic game, consists of a set of agents $N\in \mathcal {N}$ and their preferences $\succeq \in \mathcal {R}^N$ and is denoted by $(N,\succeq )$.

A partition $\pi$ for hedonic game $(N,\succeq )$ is a set $\pi =\{H_{1},H_{2},\ldots ,H_{K}\}$ ($K\le |N|$ is a positive integer) such that (i) for any $k\in \{1,\ldots ,K\}$, $H_{k}\ne \emptyset$, (ii) $\bigcup _{k=1}^{K}H_{k}=N$, and (iii) for any $k,l\in \{1,\ldots ,K\}$ with $k\ne l$, $H_{k}\cap H_{l}=\emptyset$. Given any partition $\pi$ and any $i\in N$, we let $\pi (i)\in \pi$ denote the unique coalition in $\pi$ containing agent i. For $S\subseteq N$, let $\pi (S)=\bigcup _{i\in S}\pi (i)$. We denote the set of partitions for hedonic game $(N,\succeq )$ by $\Pi (N,\succeq )$ (even though this set does not depend on preferences $\succeq$). If it is clear which hedonic game $(N,\succeq )$ we refer to, partitions are assumed to be elements of $\Pi (N,\succeq )$. Since agents only care about their own coalitions, we use the same notation for preferences over coalitions and partitions: for all agents $i\in N$ and partitions $\pi ,\pi '$, $\pi \succeq _{i} \pi '$ if and only if $\pi (i)\succeq _{i}\pi '(i)$.

In the sequel, we consider two domains of hedonic games: the domain of all hedonic games and the domain of so-called solvable hedonic games (Definition 5). To avoid notational complexity when introducing solutions and their properties, we use the generic domain of all hedonic games $\mathfrak {D}$.

A solution $\varphi$ on $\mathfrak {D}$ is a correspondence that associates with each hedonic game $\left( N,\succeq \right) \in \mathfrak {D}$ a nonempty subset of partitions, i.e., for all $(N,\succeq )\in \mathfrak {D}$, $\varphi \left( N,\succeq \right) \subseteq \Pi \left( N,\succeq \right)$ and ${\varphi \left( N,\succeq \right) \ne \emptyset }$. A subsolution (supersolution) $\psi$ of $\varphi$ on $\mathfrak {D}$ is a correspondence that associates with each hedonic games $(N,\succeq )\in \mathfrak {D}$ a nonempty subset (superset) of partitions in $\varphi {(N,\succeq )}$, i.e., for all hedonic games $(N,\succeq )\in \mathfrak {D}$, $\psi (N,\succeq )\subseteq \varphi (N,\succeq )$ [$\psi (N,\succeq )\supseteq \varphi (N,\succeq )$] and $\psi {(N,\succeq )}\ne \emptyset$. A proper subsolution (proper supersolution) $\psi$ of $\varphi$ on $\mathfrak {D}$ is a subsolution (supersolution) of $\varphi$ on $\mathfrak {D}$ such that $\psi \ne \varphi$.

The first property of a solution we introduce is a voluntary participation condition based on the idea that no agent i can be forced to be a member of a coalition that is unacceptable to her.

Definition 1

(Individual rationality) A partition $\pi$ is individually rational for hedonic game $(N,\succeq )$ if for all $i\in N$, $\pi (i)\succeq _{i}\{i\}$. $IR(N,\succeq )$ denotes the set of all these partitions. A solution $\varphi$ on $\mathfrak {D}$ is individually rational if it only assigns individually rational partitions, i.e., for all $(N,\succeq )\in \mathfrak {D}$, $\varphi (N,\succeq )\subseteq IR(N,\succeq )$.

Next, we introduce the well-known condition of Pareto optimality and the weaker condition of unanimity.

Definition 2

(Pareto optimality) A partition $\pi$ is Pareto optimal for hedonic game $(N,\succeq )$ if there is no other partition ${\pi '\in \Pi (N,\succeq )}$ such that for all $i\in N$, $\pi '\succeq _{i}\pi$ and for some $j\in N$, $\pi '\succ _{j}\pi$. $PO(N,\succeq )$ denotes the set of all these partitions. A solution $\varphi$ on $\mathfrak {D}$ is Pareto optimal if it only assigns Pareto optimal partitions, i.e., for all $(N,\succeq )\in \mathfrak {D}$, $\varphi (N,\succeq )\subseteq PO(N,\succeq )$.

Definition 3

(Unanimity) A partition $\pi$ is the unanimously best partition for $(N,\succeq )$ if it is such that for all $i\in N$, $Ch_{i}(N,\succeq _{i})=\pi (i)$. A solution $\varphi$ on $\mathfrak {D}$ is unanimous if it only assigns the unanimously best partition whenever it exists, i.e., for all hedonic games $(N,\succeq )\in \mathfrak {D}$ with a unanimously best partition $\pi$, $\varphi (N,\succeq )=\{\pi \}$.

Note that Pareto optimality implies unanimity.

The next property requires that a coalition that is unanimously best for its members is always formed.

Definition 4

(Coalitional unanimity) Let $(N,\succeq )$ be a hedonic game and $H\subseteq N$ such that for all $i\in H$, $Ch_{i}(N,\succeq _{i})=H$. Then, coalition H is unanimously best for all agents in H. A solution $\varphi$ on $\mathfrak {D}$ is coalitionally unanimous if it only assigns partitions at which all unanimously best coalitions are formed, i.e., for all $(N,\succeq )\in \mathfrak {D}$, if $H\subseteq N$ is a unanimously best coalition and $\pi \in \varphi (N,\succeq )$, then $H\in \pi$.

Note that coalitional unanimity implies unanimity, and coalitional unanimity and Pareto optimality are logically unrelated.

Next, we define core stability for hedonic games. A partition $\pi$ for hedonic game $(N,\succeq )$ is blocked by a coalition $T\subseteq N$ if for all $i\in T$, $T\succ _{i}\pi (i)$. If T blocks $\pi$, then T is called a blocking coalition for $\pi$. A partition is individually rational if no blocking coalition $\{i\}$, $i\in N$, exists.

Definition 5

(Core stability, solvability, and the core solution) A partition $\pi$ is core stable for hedonic game $(N,\succeq )$ if there is no blocking coalition for $\pi$. $Core(N,\succeq )$ denotes the set of all these partitions. A hedonic game is solvable if core stable partitions exist, i.e., $(N,\succeq )$ is solvable if and only if $Core(N,\succeq )\ne \emptyset$. Furthermore, on the domain of solvable hedonic games, a solution $\varphi$ is core stable if it only assigns core stable partitions, i.e., for all $(N,\succeq )$ such that $Core(N,\succeq )\ne \emptyset$, $\varphi (N,\succeq )\subseteq Core(N,\succeq )$. Finally, on the domain of solvable hedonic games, the Core is the solution that always assigns all core stable partitions.

Banerjee et al. (2001) introduce the so-called “top-coalition property” for a hedonic game $(N,\succeq )$ and show that if a hedonic game has the top-coalition property, then a core stable partition always exists.¹⁰ We note that a coalition $H\subseteq N$ is a top-coalition of N if and only if H is unanimously best for its members. Hence, the top-coalition property, as well as coalitional unanimity, are based on the existence of a unanimously best coalition, but the top-coalition property describes a restriction of the class of hedonic games while coalitional unanimity is the property of a solution.

Iehlé (2007) introduced pivotal balancedness and showed that it is both a necessary and sufficient condition for the existence of a core stable partition. Hence, a hedonic game is solvable if and only if it is pivotally balanced (for a definition of pivotal balancedness and the proof of this equivalence we refer the interested reader to Iehlé 2007).

Finally, we introduce Maskin monotonicity (Maskin 1977, 1999): if a partition is chosen in one hedonic game, then it is also chosen in a hedonic game that results from a Maskin monotonic transformation, which essentially means that the partition (weakly) improved in the preference ranking of all agents.

Let $(N,\succeq )$ be a hedonic game. Then, for any agent $i\in N$ and partition $\pi \in \Pi (N,\succeq )$, the lower contour set of $\succeq _{i}$ at $\pi$ is $L_{i}(\succeq _{i},\pi ):=\left\{ T\in \Sigma ^{N}_{i} \mid \pi (i)\succeq _{i}T\right\}$. For preference profiles $\succeq ,\succeq '\in \mathcal {R}^N$ and partition $\pi \in \Pi (N,\succeq )$, $\succeq '$ is a Maskin monotonic transformation of $\succeq$ at $\pi$ if for all $i\in N$, $L_{i}(\succeq _{i},\pi )\subseteq L_{i}(\succeq '_{i},\pi )$.

Definition 6

(Maskin monotonicity) A solution $\varphi$ on $\mathfrak {D}$ is Maskin monotonic if for all hedonic games $(N,\succeq ),(N,\succeq ')\in \mathfrak {D}$, and all $\pi \in \varphi (N,\succeq )$ such that $\succeq '$ is a Maskin monotonic transformation of $\succeq$ at $\pi$, $\pi \in \varphi (N,\succeq ')$.

Maskin monotonicity is one of the key concepts in implementation theory. However, here we focus on Maskin monotonicity as a desirable property in itself.

Proposition 1

On the domain of solvable hedonic games, any core stable solution, in particular the Core, satisfies individual rationality, Pareto optimality, unanimity, and coalitional unanimity. On the domain of solvable hedonic games, the Core satisfies Maskin monotonicity.

The last statement of Proposition 1 implies that the domain of solvable hedonic games is closed under Maskin monotonic transformations at core stable partitions.

Proof

It is easily checked that any core stable solution satisfies individual rationality, Pareto optimality, unanimity, and coalitional unanimity. We now show that the Core satisfies Maskin monotonicity.

Let $(N,\succeq )$ be a solvable hedonic game and let $\pi \in \Pi (N,\succeq )$ be such that $\pi \in Core(N,\succeq )$. Let $(N,\succeq ')$ be a solvable hedonic game such that $\succeq '$ is a Maskin monotonic transformation of $\succeq$ at $\pi$. We will show that $\pi \in Core(N,\succeq ')$. Suppose not. Then, there exists a blocking coalition $T\subseteq N$ for $\pi$, i.e., for all $j\in T$, $T\succ '_{j}\pi (j)$. So, for all $j\in T$, $T\notin L_{j}(\succeq '_{j},\pi )$. This fact, together with $L_{i}(\succeq _{i},\pi )\subseteq L_{i}(\succeq '_{i},\pi )$ for all $i\in N$, implies that for all $j\in T$, $T\notin L_{j}(\succeq _{j},\pi )$. This means that for all $j\in T$, $T\succ _{j}\pi (j)$, contradicting $\pi \in Core(N,\succeq )$. $\square$

3 Variable population properties

3.1 Population sensitivity properties

The following two population sensitivity properties were introduced for and applied to roommate markets by Klaus (2011) and Can and Klaus (2013) (some notation and wording to introduce the population sensitivity properties are taken from Klaus 2011).

Hedonic games and matching markets, e.g., marriage markets (one-to-one two-sided matching markets) or roommate markets (one-to-one one-sided matching markets), are discrete markets where, loosely speaking, the commodities to be traded are the agents themselves. Thus, agents are consumers and resources at the same time. We investigate two properties that capture the effect a newcomer has on incumbent agents: competition and resource sensitivity. Competition sensitivity focuses on the newcomer as additional consumer and requires that some incumbents will suffer if competition is caused because the newcomer initiates new trades. Resource sensitivity focuses on the newcomer as additional resource and requires that some incumbents will benefit if there are new trades, i.e., the extra resource is consumed. We next formalize these two properties.

Consider the change of a hedonic game $(N,\succeq )$ when a finite set of agents or newcomers $\widehat{N}\subset \mathbb {N}\backslash N$ shows up. Then, the new set of agents is $N'=N\cup \widehat{N}$ and $(N',\succeq ')$, $\succeq '\in \mathcal {R}^{N'}$, is an extension of $(N,\succeq )$ if agents in N extend their preferences to $L(\Sigma ^{N'}_{i})$ such that

• (i) for all $i\in N'$, $\succeq '_i\in L(\Sigma ^{N'}_{i})$ and

• (ii) for all $i\in N$ and all $S,T\in \Sigma ^{N}_{i}$, $S\succeq _{i}T$ if and only if $S\succeq '_{i}T$.

Note that $\succeq \in \mathcal {R}^{N}$ is the restriction of $\succeq '\in \mathcal {R}^{N'}$ to N. We denote the restriction of $\succeq '$ to N by $\succeq '_{N}$, i.e., $\succeq '_{N}=\succeq$.

We will extend some of the results by Klaus (2011) and Can and Klaus (2013) for roommate markets to hedonic games (Lemmas 1–7, Theorems 1 and 2, and Corollary 2) and show that other results cannot be extended (see Example 2).¹¹ Both population sensitivity properties have their origin in the well-known solidarity property population monotonicity¹² (see Toda 2006, for marriage markets). As in Toda (2006) and Klaus (2011) we apply the pessimistic view of comparing sets of partitions (matchings in their models) throughout this article.¹³

Loosely speaking, our first population sensitivity property—competition sensitivity—models the following: if a coalition consisting of only incumbents newly forms after newcomers have arrived, then one of these incumbents suffers from the increased competition by the newcomers and is worse off.

Definition 7

(Competition sensitivity) A solution $\varphi$ on $\mathfrak {D}$ is competition sensitive if the following holds. Let $(N,\succeq )\in \mathfrak {D}$ be a hedonic game and assume that $(N',\succeq ')\in \mathfrak {D}$, $N'=N\cup \widehat{N}$, is an extension of $(N,\succeq )$. Then, for all partitions $\pi \in \varphi (N,\succeq )$ there exists a partition $\pi '\in \varphi (N',\succeq ')$ such that for all coalitions $H\subseteq N$ that are newly formed at $\pi '$, at least one agent in H is worse off, i.e., if $H\subseteq N$, $H\notin \pi$, and $H\in \pi '$, then there exists at least one agent $i\in H$ such that $\pi (i)\succ '_{i}\pi '(i)$.¹⁴

Loosely speaking, our second population sensitivity property—resource sensitivity—models the following: if a coalition consisting of only incumbents splits up after newcomers have arrived, then one of these incumbents benefits from the increase of resources by the newcomers and is better off.

Definition 8

(Resource sensitivity) A solution $\varphi$ on $\mathfrak {D}$ is resource sensitive if the following holds. Let $(N,\succeq )\in \mathfrak {D}$ be a hedonic game and assume that $(N',\succeq ')\in \mathfrak {D}$, $N'=N\cup \widehat{N}$, is an extension of $(N,\succeq )$. Then, for all partitions $\pi '\in \varphi (N',\succeq ')$ there exists a partition $\pi \in \varphi (N,\succeq )$ such that for all coalitions $H\subseteq N$ that are not formed at $\pi '$ anymore, at least one agent in H is better off, i.e., if $H\subseteq N$, $H\in \pi$, and $H\notin \pi '$, then there exists at least one agent $i\in H$ such that $\pi '(i)\succ '_{i}\pi (i)$.¹⁵

Proposition 2

On the domain of solvable hedonic games, any core stable solution satisfies competition sensitivity and resource sensitivity. In particular, the Core satisfies competition sensitivity and resource sensitivity.

Proof

Let $\varphi$ be a core stable solution on the domain of solvable hedonic games. Let $(N,\succeq )$ be a solvable hedonic game and assume that $(N',\succeq ')$, $N'=N\cup \widehat{N}$, is an extension of $(N,\succeq )$ that is solvable.

Competition sensitivity: Assume that $\varphi$ is not competition sensitive, i.e., there exist $\pi \in \varphi (N,\mathbin {\succeq })$, $\pi '\in \varphi (N',\succeq ')$, and $H\subseteq N$ such that $H\in \pi '$, $H\notin \pi$, and for all $i\in H$, $\pi '(i)\succ '_{i}\pi (i)$. Thus, H is a blocking coalition for $\pi$; contradicting $\pi \in \varphi (N,\succeq )\subseteq Core(N,\succeq )$.

Resource sensitivity: Assume that $\varphi$ is not resource sensitive, i.e., there exist $\pi \in \varphi (N,\succeq )$, $\pi '\in \varphi (N',\succeq ')$, and $H\subseteq N$ such that $H\in \pi$, $H\notin \pi '$, and for all $i\in H$, $\pi (i)\succ '_{i}\pi '(i)$. Hence, H is a blocking coalition for $\pi '$; contradicting $\pi '{\in }\varphi (N',\succeq ')\subseteq Core(N',\succeq ')$. $\square$

3.2 Consistency

Consistency is one of the key properties in many frameworks with variable sets of agents. Thomson (2013) provides an extensive survey of consistency for various economic models, including marriage markets. For roommate markets, Can and Klaus (2013) use consistency, together with some basic properties and population sensitivity properties to characterize the Core.

For hedonic games, consistency essentially requires that when at a partition assigned by the solution a set of coalitions (of the partition) leave, then the solution should still partition the remaining agents as before.

Given a hedonic game $(N,\succeq )$, a partition $\pi \in \Pi (N,\succeq )$, and $N'\subseteq N$ such that $\pi (N')=N'$, the reduced hedonic game of $(N,\succeq )$ at $\pi$ to $N'$ equals $(N',\succeq _{N'})$. Given a hedonic game $(N,\succeq )$, a partition $\pi \in \Pi (N)$, and $N'\subseteq N$ such that $\pi (N')=N'$, we define the reduced partition $\pi '$ of $\pi$ to $N'$ as follows:

• (i) $\pi '\in \Pi (N',\succeq _{N'})$ and

• (ii) for all $i\in N'$, $\pi '(i)=\pi (i)$.

We denote the reduced partition of $\pi$ to $N'$ by $\pi _{N'}$. Note that $\pi _{N'}\in \Pi (N',\succeq _{N'})$.

Definition 9

(Consistency) A solution $\varphi$ on $\mathfrak {D}$ is consistent if the following holds. For each $(N,\succeq )\in \mathfrak {D}$ and each $\pi \in \varphi (N,\succeq )$, if $(N',\succeq _{N'})\in \mathfrak {D}$ is a reduced hedonic game of $(N,\succeq )$ at $\pi$ to $N'$ (i.e., $\pi (N')=N'$), then $\pi _{N'}\in \varphi (N',\succeq _{N'})$.

Proposition 3

On the domain of solvable hedonic games, the Core satisfies consistency.

Proof

Let $(N,\succeq )$ be a solvable hedonic game, $\pi \in Core(N,\succeq )$, and assume that $(N',\succeq _{N'})$ is a solvable reduced hedonic game of $(N,\succeq )$ at $\pi$ to $N'$. Thus, $Core(N',\mathbin {\succeq }_{N'})\ne \emptyset$.

Assume, by contradiction, that $\pi _{N'}\not \in Core(N',\succeq _{N'})$. Then, there exists a blocking coalition $H\subseteq N'$ for $\pi _{N'}$ (at preferences $\succeq _{N'}$). However, since for all $i\in H$, $\pi _{N'}(i)=\pi (i)$ and $\succeq _{N'}$ is the restriction of $\succeq$ to $N'$, $H\subseteq N$ is also a blocking coalition for $\pi$; contradicting $\pi \in Core(N,\succeq )$. $\square$

4 Results

4.1 Relations between properties

Our first result shows that a result corresponding to Toda (2006, Lemma 3.1) and Klaus (2011, Lemma 3) holds for hedonic games.

Lemma 1

On any domain that includes the domain of solvable hedonic games, unanimity and competition sensitivity imply coalitional unanimity.

Proof

Let $\varphi$ be a solution on a domain that includes solvable hedonic games that satisfies unanimity and competition sensitivity. Let $(N,\succeq )$ be a (solvable) hedonic game and $H\subseteq N$ such that for all $i\in H$, $Ch_{i}(N,\succeq _{i})=H$. To prove that $\varphi$ satisfies coalitional unanimity, we show that for all $\pi \in \varphi (N,\succeq )$, $H\in \pi$.

If $H=N$, then $\pi =\{H\}$ is the unanimously best partition for $(N,\succeq )$. Hence, by unanimity, $\varphi \left( N,\succeq \right) =\{\pi \}$.

Assume $H\varsubsetneq N$, $S:=N\setminus H$, and let $\widehat{N}=\{n\}$ be a set consisting of one newcomer. Let $(N',\succeq ')$ be an extension of $(N,\succeq )$ such that $N'=N\cup \widehat{N}$, for all $i\in H$, $Ch_{i}(N',\mathbin {\succeq '_i})=H$, and for all agents $j\in (S \cup \widehat{N})$, $Ch_{j}(N',\mathbin {\succeq '_j})=S\cup \widehat{N}$. For the solvable hedonic game $(N',\succeq ')$, $\pi '=\{H,S\cup \widehat{N}\}$ is the unanimously best partition. Hence, by unanimity, $\varphi (N',\succeq ')=\{\pi '\}$. By competition sensitivity, for all $\pi \in \varphi (N,\succeq )$, if H is newly formed at $\pi '$, then at least one agent in H is worse off. Since at $\pi '$ coalition H is unanimously best for the members of H, for all $\pi \in \varphi (N,\succeq )$, $H\in \pi$. $\square$

Our next result shows that a result corresponding to Klaus (2011, Lemma 4) holds for hedonic games.

Lemma 2

On any domain that includes the domain of solvable hedonic games, unanimity and resource sensitivity imply coalitional unanimity.

Proof

Let $\varphi$ be a solution on a domain that includes solvable hedonic games that satisfies unanimity and resource sensitivity. Let $(N,\mathbin {\succeq })$ be a (solvable) hedonic game and $H\subseteq N$ such that for all $i\in H$, $Ch_{i}(N,\mathbin {\succeq _{i}})=H$. To prove that $\varphi$ satisfies coalitional unanimity, we show that for all $\pi \in \varphi (N,\mathbin {\succeq })$, $H\in \pi$.

If $H=N$, then $\pi =\{H\}$ is the unanimously best partition for $(N,\succeq )$. Hence, by unanimity, $\varphi \left( N,\succeq \right) =\{\pi \}$.

Assume $H\varsubsetneq N$ and consider the reduced preferences $\mathbin {\overline{\succeq }}=\mathbin {\succeq _{H}}$. Since for all $i\in H$, $Ch_{i}(N,\mathbin {\succeq _{i}})=H$ and $H\varsubsetneq N$, we also have for all $i\in H$, $Ch_{i}(H,\mathbin {\overline{\succeq }_i})=H$. Hence, for the solvable hedonic game $(H,\mathbin {\overline{\succeq }})$, $\overline{\pi }=\{H\}$ is the unanimously best partition. Hence, by unanimity, $\varphi (H,\mathbin {\overline{\succeq }})=\{\overline{\pi }\}$.

Let $\widehat{N}:=N\setminus H$ and $N=H\cup \widehat{N}$. Consider the extension $(N,\mathbin {\succeq )}$ of $(H,\mathbin {\overline{\succeq }})$ that is obtained by adding newcomers $\widehat{N}$. By resource sensitivity, for all ${\pi }\in \varphi (N,\mathbin {\succeq })$, if H is not formed at $\pi$ anymore, then at least one agent in H is better off. Since at $\overline{\pi }$ coalition H is unanimously best for the members of H, for all ${\pi }\in \varphi (N,\mathbin {\succeq })$, $H\in {\pi }$. $\square$

The next result shows that a result corresponding to Toda (2006, Lemma 3.3) and Klaus (2011, Lemma 6) holds for hedonic games.

Lemma 3

• (a) On the domain of solvable hedonic games, if a solution $\varphi$ is coalitionally unanimous and Maskin monotonic, then it is a subsolution of the Core.

• (b) On the domain of all hedonic games, no solution $\varphi$ is coalitionally unanimous and Maskin monotonic.

In particular, Lemma 3(a) implies that on the domain of solvable hedonic games, if a solution $\varphi$ is coalitionally unanimous and Maskin monotonic, then it is individually rational and Pareto optimal.

Proof

Let $\varphi$ be a solution on the domain of all (solvable) hedonic games that satisfies coalitional unanimity and Maskin monotonicity.

To prove Part (a), let $(N,\succeq )$ be a solvable hedonic game such that $\varphi (N,\succeq )\nsubseteq Core(N,\succeq )$. To prove Part (b), let $(N,\succeq )$ be an unsolvable hedonic game. In both cases there exists a partition $\pi \in \varphi (N,\succeq )$ with a blocking coalition $H\subseteq N$ for $\pi$. We now define $\mathbin {\widetilde{\succeq }}\in \mathcal {R}^{N}$ as follows:

• For any agent $i\in H$, (if $Ch_{i}(N, \mathbin {\succeq }_{i}) \ne H$) we first move coalition H to the top of agent i’s preferences $\mathbin {\succeq }_{i}$ and then we move coalition $\pi (i)$ just below coalition H, i.e., for all $i\in H$, $Ch_{i}(N,\mathbin {\widetilde{\succeq }}_{i})=H$, there is no $S\in \Sigma ^{N}_{i}$ such that $H\mathbin {\widetilde{\succ }}_{i}S\mathbin {\widetilde{\succ }}_{i}\pi (i)$, and for any $S,T\in \left( \Sigma ^{N}_{i}\setminus \{H,\pi (i)\}\right)$, $S\mathbin {\widetilde{\succeq }}_{i}T$ if and only if $S\mathbin {\succeq }_{i}T$.

• For any agent $j\in N\setminus H$, (if $Ch_{j}(N, \mathbin {\succeq }_{j}) \ne \pi (j)$) we first move coalition $\pi (j)$ to the top of agent j’s preferences $\mathbin {\succeq }_{j}$ and (if $\pi (j)\ne \{j\}$) then we move coalition $\{j\}$ just below $\pi (j)$, i.e., for all $j\in N\setminus H$, $Ch_{j}(N,\mathbin {\widetilde{\succeq }}_{j})=\pi (j)$, there is no $S\in \Sigma ^{N}_{j}$ such that $\pi (j)\mathbin {\widetilde{\succ }}_{j}S\mathbin {\widetilde{\succ }}_{j}\{j\}$, and for any $S,T\in \left( \Sigma ^{N}_{j}\setminus \{\pi (j),\{j\}\}\right)$, $S\mathbin {\widetilde{\succeq }}_{j}T$ if and only if $S\mathbin {\succeq }_{j}T$.

Note that $(N,\widetilde{\succeq })$ is solvable¹⁶ and that $\widetilde{\succeq }$ is a Maskin monotonic transformation of $\succeq$ at $\pi$. Hence, by Maskin monotonicity, $\pi \in \varphi (N,\widetilde{\succeq })$. By coalitional unanimity, for all $\widetilde{\pi }\in \varphi (N,\widetilde{\succeq })$, $H\in \widetilde{\pi }$. Since $H\notin \pi$ this is a contradiction to $\pi \in \varphi (N,\widetilde{\succeq })$.

For Part (a) this proves that $\varphi (N,\succeq )\subseteq Core(N,\succeq )$ and for Part (b) this proves that coalitional unanimity and Maskin monotonicity are not compatible on the domain of all hedonic games. $\square$

The proof of Lemma 3(b) can be used to show that adding an unsolvable hedonic game to the domain of solvable hedonic games will lead to an impossibility result. Hence, Lemma 3 implies the following corollary.

Corollary 1

(A maximal domain result) The domain of solvable hedonic games is a maximal domain for the existence of a coalitionally unanimous and Maskin monotonic solution.

Since Maskin monotonicity (Maskin 1977, 1999) is a key property for Nash implementability of social choice rules (see Jackson 2001), some of our results using Maskin monotonicity have implications for the Nash implementability of solutions in hedonic games. When there are at least three agents, Takamiya (2010, Theorem 2) shows that, on the domain of solvable hedonic games, the Core is Nash implementable.¹⁷ Furthermore, Takamiya (2010, Corollary 1) shows that a solution satisfies coalitional unanimity and is Nash implementable if and only if it is the Core. This result and Corollary 1 imply that the domain of solvable hedonic games is a maximal domain for the existence of a coalitionally unanimous and Nash implementable solution when there are at least three agents.

Toda (2006, Lemma 3.4) (for marriage markets) proved a similar result to Lemma 3 using consistency instead of Maskin monotonicity. The following example shows that Toda’s result does not extend to hedonic games¹⁸; the recursive coalitional unanimity solution $\overline{\varphi }$ described in the following example satisfies coalitional unanimity and consistency on the domain of solvable hedonic games and on the domain of all hedonic games.

Example 1

(The recursive coalitional unanimity solution)¹⁹

The recursive coalitional unanimity solution $\overline{\varphi }$ on $\mathfrak {D}$ is defined as follows. For each hedonic game $(N,\succeq )$, $\overline{\varphi }(N,\succeq )=\{\overline{\pi }\}$ where partition $\overline{\pi }$ is determined as follows:

Step 1. If there exist unanimously best coalitions for hedonic game $(N,\succeq )$, then they are part of the final partition and we continue with Step 2. More specifically, let $H^{1}_{1},\ldots ,H^{l(1)}_{1}$ denote all unanimously best coalitions for hedonic game $(N,\succeq )$, i.e., for all $1\le r \le l(1)$, and all $i\in H^{r}_{1}$, $Ch_{i}(N,\succeq )=H^{r}_{1}$. Then, for all $1\le r \le l(1)$, $H^{r}_{1}\in \overline{\pi }$.

If there exists no unanimously best coalition for hedonic game $(N,\succeq )$, then $\overline{\pi }=\{N\}$ and we are done.

Step 2. Let $N^{2}=N\setminus (\cup _{r=1}^{l(1)}H^{r}_{1})$ and consider the reduced hedonic game $(N^{2},\succeq _{N^{2}})$. If there exist unanimously best coalitions for hedonic game $(N^{2},\succeq _{N^{2}})$, then they are part of the final partition and we continue with Step 3. More specifically, let $H^{1}_{2},\ldots ,H^{l(2)}_{2}$ denote all unanimously best coalitions for hedonic game $(N^{2},\succeq _{N^{2}})$, i.e., for all $1\le r \le l(2)$, and all $i\in H^{r}_{2}$, $Ch_{i}(N^{2},\succeq _{N^{2}})=H^{r}_{2}$. Then, for all $1\le r \le l(2)$, $H^{r}_{2}\in \overline{\pi }$.

If there exists no unanimously best coalition for hedonic game $(N^{2},\succeq _{N^{2}})$, then $\overline{\pi }=\{H^{1}_{1},\ldots ,H^{l(1)}_{1},N^{2}\}$ and we are done.

Generally, at Step k, let $N^{k}=N\setminus (\cup _{t=1}^{k-1}\cup _{r=1}^{l(t)}H^{r}_{t})$ and consider the reduced hedonic game $(N^{k},\succeq _{N^{k}})$. If there exist unanimously best coalitions for hedonic game $(N^{k},\succeq _{N^{k}})$, then they are part of the final partition and we continue with the next step. Let $H^{1}_{k},\ldots ,H^{l(k)}_{k}$ denote all unanimously best coalitions for hedonic game $(N^{k},\succeq _{N^{k}})$, i.e., for all $1\le r \le l(k)$, and all $i\in H^{r}_{k}$, $Ch_{i}(N^{k},\succeq _{N^{k}})=H^{r}_{k}$. Then, for all $1\le r \le l(k)$, $H^{r}_{k}\in \overline{\pi }$.

If there exists no unanimously best coalition for hedonic game $(N^{k},\succeq _{N^{k}})$, then $\overline{\pi } = \{H^{1}_{1}, \ldots ,H^{l(1)}_{1}, \ldots ,H^{1}_{k-1}, \ldots ,H^{l(k-1)}_{k-1},N^{k}\}$. $\square$

The recursive coalitional unanimity solution satisfies neither competition sensitivity nor resource sensitivity.

4.2 The core: characterizations and (im)possibilities

The following result corresponds to a result by Sönmez (1996, Theorem 1) for generalized one-to-one matching markets.

Lemma 4

On the domain of solvable hedonic games, if a solution $\varphi$ is Pareto optimal, individually rational, and Maskin monotonic, then it is a supersolution of the Core, i.e., for all solvable hedonic games $(N,\succeq )$, $\varphi (N,\succeq )\supseteq Core(N,\succeq )$.

Proof

Let $\varphi$ be a solution on the domain of solvable hedonic games that satisfies Pareto optimality, individual rationality, and Maskin monotonicity. Let $(N,\succeq )$ be a solvable hedonic game and $\pi \in \Pi (N,\succeq )$ be such that $\pi \in Core(N,\succeq )$. We will show that $\pi \in \varphi (N,\succeq )$.

Let $H=\{i\in N \mid \pi (i)=\{i\}\}$ and $\widetilde{H}=\{j\in N \mid \pi (j)\ne \{j\}\}$. We define $\widetilde{\succeq }\in \mathcal {R}^{N}$ as follows:

• For any agent $i\in H$, we leave preferences as they are, i.e., for all $i\in H$, $\widetilde{\succeq }_{i}=\succeq _{i}$.

• For any $j\in \widetilde{H}$, we have that $\pi (j)\succ _j\{j\}$ and we move coalition $\{j\}$ just below $\pi (j)$, i.e., for all $j\in \widetilde{H}$, there is no $S\in \Sigma ^{N}_{j}$ such that $\pi (j)\mathbin {\widetilde{\succ }}_{j}S\mathbin {\widetilde{\succ }}_{j}\{j\}$ and for any $S,T\in \left( \Sigma ^{N}_{j}\setminus \{j\}\right)$, $S\mathbin {\widetilde{\succeq }}_{j}T$ if and only if $S\mathbin {\succeq }_{j}T$.

Note that $(N,\widetilde{\succeq })$ is solvable and that $\widetilde{\succeq }$ is a Maskin monotonic transformation of $\succeq$ at $\pi$. Hence, since the Core satisfies Maskin monotonicity (by Proposition 1), $\pi \in Core(N,\widetilde{\succeq })$. Since for all $i\in N$, $L_{i}(\succeq _{i},\pi )= L_{i}(\widetilde{\succeq }_{i},\pi )$, we also have that $\succeq$ is a Maskin monotonic transformation of $\widetilde{\succeq }$ at $\pi$.

First we show that $PO(N,\widetilde{\succeq })\cap IR(N,\widetilde{\succeq })=\{\pi \}$. Assume, by contradiction, that there exists a partition $\widetilde{\pi }\in PO(N,\widetilde{\succeq })\cap IR(N,\widetilde{\succeq })$ such that $\widetilde{\pi }\ne \pi$.

Assume that for some $i\in N$, $\widetilde{\pi }(i)\mathbin {\widetilde{\succ }_{i}}\pi (i)$. By the construction of $\widetilde{\succeq }$, $\widetilde{\pi }(i)\ne \{i\}$, and hence for all $j\in \widetilde{\pi }(i)$, $\widetilde{\pi }(j)\ne \{j\}$. Now, together with $\widetilde{\pi }\in IR(N,\widetilde{\succeq })$, we have that for all $j\in \widetilde{\pi }(i)$, $\widetilde{\pi }(j)\mathbin {\widetilde{\succ }_{j}}\pi (j)$. Hence, coalition $\widetilde{\pi }(i)$ blocks partition $\pi$, contradicting $\pi \in Core(N,\widetilde{\succeq })$. Thus, for all $i\in N$, $\pi (i)\mathbin {\widetilde{\succeq }_{i}}\widetilde{\pi }(i)$. Since $\widetilde{\pi }\ne \pi$, for some $j\in N$, $\pi (j)\mathbin {\widetilde{\succ }_{j}}\widetilde{\pi }(j)$. But then, $\widetilde{\pi }\not \in PO(N,\widetilde{\succeq })$, a contradiction.

Hence, since $\varphi$ is Pareto optimal and individually rational, $\varphi (N,\widetilde{\succeq })=\{\pi \}$. Then, since $\succeq$ is a Maskin monotonic transformation of $\widetilde{\succeq }$ at $\pi$ and $\varphi$ is Maskin monotonic, we have $\pi \in \varphi (N,\succeq )$. $\square$

The next result shows that a result corresponding to Toda (2006, Lemma 3.5) and Klaus (2011, Lemma 7) holds for hedonic games.

Lemma 5

On the domain of solvable hedonic games, there exists no Maskin monotonic proper subsolution of the Core.

Proof

On the domain of solvable hedonic games, by Lemma 4, if a solution $\varphi$ is Pareto optimal, individually rational, and Maskin monotonic, then it is a supersolution of the Core, i.e., for all solvable hedonic games $(N,\succeq )$, $\varphi (N,\succeq )\supseteq Core(N,\succeq )$.

Thus, since any subsolution of the Core satisfies Pareto optimality and individual rationality, there exists no Maskin monotonic proper subsolution of the Core on the domain of solvable hedonic games. $\square$

The next result shows that a result corresponding to Toda (2006, Lemma 3.6) and Can and Klaus (2013, Lemma 1) holds for hedonic games.

Lemma 6

On the domain of solvable hedonic games, there exists no consistent proper subsolution of the Core.

Before proving Lemma 6, we state and prove a so-called Bracing Lemma (which is a typical consistency result for many economic models; see Thomson 2013).

Lemma 7

(Bracing lemma) Let $(N,\succeq )$ be a solvable hedonic game. For each $\pi \in Core(N,\succeq )$, there exists a solvable hedonic game $(N',\succeq ')$, such that $N\subseteq N'$, $\succeq '_{N}=\succeq$, $Core(N',\succeq ')=\{\pi '\}$, and $\pi '_{N}=\pi$.

Proof

Let $(N,\succeq )$ be a solvable hedonic game. If $|Core(N,\succeq )|=1$, then there is nothing to prove. Let $Core(N,\succeq )=\{\pi ,\pi _{1},\ldots ,\pi _{k}\}$ for some $k\ge 1$. Since the Core is Pareto optimal, there exists $i^*\in N$ such that $\pi (i^*)\mathbin {\succ _{i^*}}\pi _{1}(i^*)$.

First, consider the extension $(N^*,\succeq ^*)$ of $(N,\succeq )$ that is obtained by adding a newcomer $n^*\in (\mathbb {N}\setminus N)$ such that $N^*=N\cup \{n^*\}$ and $\succeq ^*\in \mathcal {R}^{N^*}$ is such that

• $\succeq ^*_{N}=\succeq$,

• for any agent $i\in \left( N\setminus \{i^*\}\right)$, all coalitions containing agent $n^*$ are unacceptable, i.e., for all $i\in \left( N\setminus \{i^*\}\right)$ and all $S\in \Sigma ^{N^*}_{i}$ with $n^*\in S$, $\{i\}\mathbin {\succ ^*_i}S$,

• for agent $i^*$, we move coalition $\{i^*,n^*\}$ just below $\pi (i^*)$, i.e., we have $\pi (i^*)\mathbin {\succ ^*_{i^*}} \{i^*,n^*\}$ and there exists no $S\in \Sigma ^{N^*}_{i^*}\setminus \left\{ \pi (i^*), \{i^*,n^*\}\right\}$ such that $\pi (i^*)\mathbin {\succ ^*_{i^*}}S\mathbin {\succ ^*_{i^*}} \{i^*,n^*\}$, since $\succeq ^*_{N}=\succeq$, preferences $\mathbin {\succeq ^*_{i^*}}$ are such that $\pi (i^*)\mathbin {\succ ^*_{i^*}} \{i^*,n^*\} \mathbin {\succ ^*_{i^*}} \pi _{1}(i^*)$,

• for agent $n^*$, her choice set from $N^*$ is $\{i^*,n^*\}$, and she finds only coalition $\{i^*,n^*\}$ acceptable, i.e., $Ch_{n^*}(N^*,\mathbin {\succeq ^*}_{n^*})=\{i^*,n^*\}$, and for all $S\in \left( \Sigma ^{N^*}_{n^*}\setminus \left\{ \{i^*,n^*\},\{n^*\}\right\} \right)$, $\{i^*,n^*\}\mathbin {\succ ^*_{n^*}} \{n^*\} \mathbin {\succ ^*_{n^*}}S$.

Note that by construction $\left( \pi \cup \{n^*\}\right) \in Core(N^*,\succeq ^*)$. Thus $(N^*,\succeq ^*)$ is solvable. We now show that $(N^*,\succeq ^*)$ has fewer core stable partitions than $(N,\succeq )$. By construction, only partitions of the form $\left( \pi ^*\cup \{n^*\}\right)$, $\pi ^*\in \Pi (N,\succeq )$, can be core stable for hedonic game $(N^*,\succeq ^*)$. Furthermore, since the Core is consistent (Proposition 3), if for any $\widetilde{\pi }\in \Pi (N,\succeq )$, $\left( \widetilde{\pi }\cup \{n^*\}\right) \in Core(N^*,\succeq ^*)$, then $\widetilde{\pi }\in Core(N,\succeq )$. Hence, $|Core(N^*,\succeq ^*)|\le |Core(N,\succeq )|$.

Moreover, the coalition $\{i^*,n^*\}$ blocks the partition $\left( \pi _{1} \cup \{n^*\}\right)$ since, by construction, $\{i^*,n^*\} \mathbin {\succ ^*_{i^*}} \pi _{1}(i^*)$, and $Ch_{n^*}(N^*,\mathbin {\succeq ^*}_{n^*})=\{i^*,n^*\}$. So, $\left( \pi _{1} \cup \{n^*\}\right) \notin Core(N^*,\succeq ^*)$. We conclude that $|Core(N^*,\succeq ^*)|< |Core(N,\succeq )|$ and $\left( \pi \cup \{n^*\}\right) \in Core(N^*,\succeq ^*)$.

Repeating this process of adding a newcomer to reduce the number of core stable partitions at most k times results in a solvable hedonic game $(N',\succeq ')$, such that $N\subseteq N'$, $\succeq '_{N}=\succeq$, $Core(N',\succeq ')=\{\pi '\}$, and $\pi '_{N}=\pi$. $\square$

The Bracing lemma (Lemma 7) is a key element in the proof of Lemma 6.

Proof of Lemma 6

Let $\varphi$ be a solution on the domain of solvable hedonic games that is a consistent subsolution of the Core. Let $(N,\succeq )$ be a solvable hedonic game and ${\pi \in Core(N,\succeq )}$. Then, by the Bracing lemma (Lemma 7), there exists a solvable hedonic game $(N^*,\succeq ^*)$ with $Core(N^*,\succeq ^*)=\{\pi ^*\}$ such that $(N,\succeq )$ is a reduced hedonic game of $(N^*,\succeq ^*)$ at $\pi ^*$ and $\pi ^*_{N}=\pi$. Since $\varphi$ is a subsolution of the Core, $\varphi (N^*,\succeq ^*)=\{\pi ^*\}$. As $\varphi$ is consistent, $\pi \in \varphi (N,\succeq )$. So, $Core(N,\succeq )\subseteq \varphi (N,\succeq )$. Since $\varphi$ is a subsolution of the Core, $\varphi (N,\succeq )\subseteq Core(N,\succeq )$. Hence, $\varphi (N,\succeq )=Core(N,\succeq )$. $\square$

Our first characterization result corresponds to a similar result for hedonic games by Takamiya (2010, Theorem 1).

Theorem 1

(A basic characterization of the core) On the domain of solvable hedonic games, a solution $\varphi$ satisfies coalitional unanimity and Maskin monotonicity if and only if it equals the Core.

Proof

Let $\varphi$ be a solution on the domain of solvable hedonic games. By Proposition 1, the Core satisfies coalitional unanimity and Maskin monotonicity.

Let $\varphi$ satisfy coalitional unanimity and Maskin monotonicity. Hence, by Lemma 3 (a), $\varphi$ is a subsolution of the Core. Then, by Lemma 5, $\varphi =Core$. $\square$

Recall that the recursive coalitional unanimity solution $\overline{\varphi }$ (defined in Example 1) satisfies coalitional unanimity and consistency on the domain of solvable hedonic games and on the domain of all hedonic games. However, the recursive coalitional unanimity solution $\overline{\varphi }$ does not equal the Core on the domain of solvable hedonic games.²⁰ Hence, Theorem 1 does not hold if we replace Maskin monotonicity with consistency, i.e., a solution defined on the domain of solvable hedonic games satisfying coalitional unanimity and consistency need not be the Core.

The following are two new characterizations of the Core for solvable hedonic games. This result corresponds to Klaus (2011, Theorem 1) (only the first characterization corresponds to Toda 2006, Theorem 3.1).

Corollary 2

(Two new characterizations of the core)

• (1) On the domain of solvable hedonic games, a solution $\varphi$ satisfies competition sensitivity, unanimity, and Maskin monotonicity if and only if it equals the Core.

• (2) On the domain of solvable hedonic games, a solution $\varphi$ satisfies resource sensitivity, unanimity, and Maskin monotonicity if and only if it equals the Core.

Proof

Let $\varphi$ be a solution on the domain of solvable hedonic games. By Propositions 1 and 2, the Core satisfies all properties listed in the corollary.

Let $\varphi$ satisfy unanimity, Maskin monotonicity, and (1) competition sensitivity. Then, by Lemma 1, $\varphi$ satisfies coalitional unanimity. Let $\varphi$ satisfy unanimity, Maskin monotonicity, and (2) resource sensitivity. Then, by Lemma 2, $\varphi$ satisfies coalitional unanimity.

Thus, $\varphi$ satisfies Maskin monotonicity and coalitional unanimity. Hence, by Theorem 1, $\varphi =Core$. $\square$

We next show the independence of properties in Theorem 1 and Corollary 2.

Let $\varphi ^s$ be the solution that always assigns the partition at which all agents are single. On the domain of solvable hedonic games, solution $\varphi ^s$ satisfies Maskin monotonicity, competition and resource sensitivity, but not unanimity—and hence not coalitional unanimity.

On the domain of solvable hedonic games any proper subsolution of the Core satisfies coalitional unanimity—and hence unanimity (Proposition 1), competition and resource sensitivity (Proposition 2), but not Maskin monotonicity (Lemma 5).

On the domain of solvable hedonic games, the Pareto solution PO satisfies unanimity, Maskin monotonicity, but neither competition sensitivity nor resource sensitivity. We show in Appendix A.1 (Examples 3 and 4) that solution PO is neither competition sensitive nor resource sensitive.

The next two impossibility results on the domain of all hedonic games correspond to Klaus (2011, Theorem 2).

Theorem 2

(Two impossibility results)

• (1) On the domain of all hedonic games, no solution $\varphi$ satisfies competition sensitivity, unanimity, and Maskin monotonicity.

• (2) On the domain of all hedonic games, no solution $\varphi$ satisfies resource sensitivity, unanimity, and Maskin monotonicity.

Proof

Let $\varphi$ be a solution on the domain of all hedonic games.

Let $\varphi$ satisfy unanimity, Maskin monotonicity, and (1) competition sensitivity. Then, by Lemma 1, $\varphi$ satisfies coalitional unanimity. Let $\varphi$ satisfy unanimity, Maskin monotonicity, and (2) resource sensitivity. Then, by Lemma 2, $\varphi$ satisfies coalitional unanimity.

Thus, $\varphi$ satisfies Maskin monotonicity and coalitional unanimity; contradicting Lemma 3(b). $\square$

In the proofs of Corollary 2 and Theorem 2 it is shown how coalitional unanimity is derived. Then, the proof of Lemma 3 can again be used to show the following corollary.

Corollary 3

(Two maximal domain results)

• (1) The domain of solvable hedonic games is a maximal domain for the existence of a competition sensitive, unanimous, and Maskin monotonic solution.

• (2) The domain of solvable hedonic games is a maximal domain for the existence of a resource sensitive, unanimous, and Maskin monotonic solution.

This corollary, together with Takamiya (2010, Corollary 1), implies that the domain of solvable hedonic games is a maximal domain for the existence of a unanimous, Nash implementable, and either competition sensitive or resource sensitive solution when there are at least three agents.

Can and Klaus (2013) shows that on the domain of solvable roommate markets the Core is characterized by (weak) unanimity, consistency, and either competition sensitivity or resource sensitivity. However, these results cannot be extended to hedonic games. With the following example, we show that on the domain of solvable hedonic games, there exists a solution not equal to the Core that satisfies coalitional unanimity, consistency, competition sensitivity, and resource sensitivity.

We prove in Appendix A.2 (Proposition 4) that solution $\widetilde{\varphi }$ as defined in the following example satisfies coalitional unanimity, consistency, competition sensitivity, and resource sensitivity.

Example 2

We define solution $\widetilde{\varphi }$ using the following hedonic game and partitions. Define the solvable hedonic game $(\widetilde{N},\widetilde{\succeq })$ by $\widetilde{N}=\{1,2,3\}$ and agents’ preferences $\widetilde{\succeq }$ as given on the left side of Table 1. Note that $Core(\widetilde{N},\widetilde{\succeq })=\{\widetilde{\pi }^{1}\}$, where $\widetilde{\pi }^{1}=\{\widetilde{N}\}$.

Table 1 Preferences of agents

We define a subdomain of solvable hedonic games, $\widetilde{\mathfrak {D}}$, as follows. A solvable hedonic game $(N,\succeq )$ is an element of $\widetilde{\mathfrak {D}}$ if $\widetilde{N}\subseteq N$ and $(\widetilde{N},\succeq _{\widetilde{N}}) =(\widetilde{N},\widetilde{\succeq })$, i.e., $(N,\succeq )$ is an extension of $(\widetilde{N},\succeq _{\widetilde{N}})$. Furthermore, for any hedonic game $(N,\succeq )\in \widetilde{\mathfrak {D}}$, we define the following associated preferences $\succeq ^a$ obtained from $\succeq$ by moving coalition $\widetilde{N}$ just below $\{i\}$ for agents $i\in \widetilde{N}$ (see the right side of Table 1):

• For any agent $i\in \widetilde{N}$, we move coalition $\widetilde{N}$ just below $\{i\}$, i.e., for all $i\in \widetilde{N}$, $\{i\}\succ ^a_{i}\widetilde{N}$, there is no $H\in \Sigma ^{N}_{i}$ such that $\{i\}\succ ^a_{i}H\succ ^a_{i}\widetilde{N}$, and for any $S,T\in (\Sigma ^{N}_{i}\setminus \{\widetilde{N}\})$, $S\succeq ^a_{i}T$ if and only if $S\succeq _{i}T$.

• For any agent $j\in (N\setminus \widetilde{N})$, $\succeq ^a_{j}=\succeq _{j}$.

Table 2 Preferences of agents

Define solution $\widetilde{\varphi }$ as follows. For all solvable hedonic games $(N,\succeq )$,

$$\begin{aligned} \widetilde{\varphi }(N,\succeq )=\left\{ \begin{array}{cl} Core(N,\succeq )\cup Core(N,\succeq ^a) &{}\quad \text {if } (N,\succeq )\in \widetilde{\mathfrak {D}}, \\ Core(N,\succeq ) &{}\quad \text {otherwise}. \\ \end{array} \right. \end{aligned}$$

In other words, for a hedonic game $(N,\succeq )\in \widetilde{\mathfrak {D}}$, solution $\widetilde{\varphi }$ might expand the Core by adding $Core(N,\succeq ^a)$ to $Core(N,\succeq )$.

Table 3 Preferences of agents

Let $\widetilde{\pi }^{2}=\{\{1\},\{2\},\{3\}\}$. Partition $\widetilde{\pi }^{2}$ is not core stable for hedonic game $(\widetilde{N},\widetilde{\succeq })$ because coalition $\widetilde{N}$ blocks $\widetilde{\pi }^{2}$. For hedonic game $(\widetilde{N},\widetilde{\succeq })$, we have that $\widetilde{\varphi }(\widetilde{N},\widetilde{\succeq }) =\left\{ \widetilde{\pi }^{1}, \widetilde{\pi }^{2}\right\}$ because $Core(\widetilde{N},\widetilde{\succeq }^a)=\{\widetilde{\pi }^{2}\}$. $\square$

Appendix A

1.1 A.1 PO is neither competition sensitive nor resource sensitive

Example 3

(The Pareto solution is not competition sensitive) Consider solvable hedonic games $(N,\succeq )$ and $(N',\succeq ')$ such that $N=\{1,2\}\varsubsetneq \{1,2,3\}=N'$ and agents’ preferences $\succeq$ and $\succeq '$ are as given in Table 2. Note that $(N',\succeq ')$ is an extension of $(N,\succeq )$.

The Pareto optimal partitions for hedonic game $(N,\succeq )$ are $\pi ^{1}=\{\{1,2\}\}$ and $\pi ^{2}=\{\{1\},\{2\}\}$, i.e., $PO(N,\succeq )=\{\pi ^{1},\pi ^{2}\}$. The unique Pareto optimal partition for hedonic game $(N',\succeq ')$ is $\pi '=\{\{1,3\},\{2\}\}$, i.e., $PO(N',\succeq ')=\{\pi '\}$.

For partition $\pi ^{1}\in PO(N,\succeq )$, we have $\{2\}\varsubsetneq N$, $\{2\}\notin \pi ^{1}$, and $\{2\}\in \pi '$, i.e., coalition $\{2\}$ is newly formed at the unique Pareto optimal partition $\pi '$. However, $\pi '(2)=\{2\}\succ '_{2}N=\pi ^{1}(2)$, i.e., agent 2 is better off at partition $\pi '$; a contradiction of competition sensitivity. $\square$

Example 4

(The Pareto solution is not resource sensitive) Consider solvable hedonic games $(N,\succeq )$ and $(N',\succeq ')$ such that $N=\{1,2\}\varsubsetneq \{1,2,3\}=N'$ and agents’ preferences $\succeq$ and $\succeq '$ are as given in Table 3. Note that $(N',\succeq ')$ is an extension of $(N,\succeq )$.

The unique Pareto optimal partition for hedonic game $(N,\mathbin {\succeq })$ is $\pi =\{\{1,2\}\}$, i.e., $PO(N,\mathbin {\succeq })=\{\pi \}$. Pareto optimal partitions for hedonic game $(N',\succeq ')$ are $\pi '^{1}=\{\{1,2,3\}\}$ and $\pi '^{2}=\{\{1,2\},\{3\}\}$, i.e., $PO(N',\succeq ')=\{\pi '^{1},\pi '^{2}\}$.

For partition $\pi '^{1}\in PO(N',\succeq ')$, we have, $\{1,2\}=N$, $\{1,2\}\in \pi$, and $\{1,2\}\notin \pi '^{1}$, i.e., coalition $\{1,2\}$ is not formed at partition $\pi '^{1}$ anymore. However, for all $i\in \{1,2\}$, $\pi (i)=N\succ '_{i}N'=\pi '^{1}(i)$, i.e., all agents in $\{1,2\}$ are worse off at partition $\pi '^{1}$; a contradiction of resource sensitivity. $\square$

1.2 A.2 Properties of solution $\widetilde{\varphi }$ (Example 2)

Proposition 4

On the domain of solvable hedonic games, solution $\widetilde{\varphi }$ defined in Example 2 satisfies coalitional unanimity, consistency, competition sensitivity, and resource sensitivity.

Proof

Coalitional unanimity. Consider a solvable hedonic game $(N,\succeq )$.

The Core satisfies coalitional unanimity (Proposition 1). Hence, for any partition $\pi \in Core(N,\succeq )\subseteq \widetilde{\varphi }(N,\succeq )$ all unanimously best coalitions with respect to preferences $\succeq$ form.

If $\pi \in \widetilde{\varphi }(N,\succeq ) \setminus Core(N,\succeq )$, then $(N,\succeq )\in \widetilde{\mathfrak {D}}$ and $\pi \in Core(N,\succeq ^a)$. By the coalitional unanimity of the Core, for partition $\pi$ all unanimously best coalitions with respect to preferences $\succeq ^a$ form. To complete the proof, we show that for partition $\pi$ all unanimously best coalitions with respect to preferences $\succeq$ form.

Note that coalition $\widetilde{N}$ is neither unanimously best for agents in $\widetilde{N}$ at preferences $\succeq$ nor is it unanimously best for agents in $\widetilde{N}$ at preferences $\succeq ^a$. The only differences between preferences $\succeq$ and preferences $\succeq ^a$ lies in the position of coalition $\widetilde{N}$ in the preferences of agents in $\widetilde{N}$ and any coalition H that is unanimously best for agents at preferences $\succeq$ is unanimously best for agents at preferences $\succeq ^a$ (and vice versa). Hence, for partition $\pi \in Core(N,\succeq ^a)$ all unanimously best coalitions with respect to preferences $\succeq$ form.

Consistency. Consider a solvable hedonic game $(N,\succeq )$, a partition $\pi \in \widetilde{\varphi }(N,\succeq )$, and a solvable reduced hedonic game $(N',\succeq _{N'})$ of $(N,\succeq )$ at $\pi$ to $N'\varsubsetneq N$ (i.e., $\pi (N')=N'$).

The Core satisfies consistency (Proposition 3). Hence, for partition $\pi \in Core(N,\succeq )\subseteq \widetilde{\varphi }(N,\succeq )$, $\pi _{N'}\in Core(N',\succeq _{N'}) \subseteq \widetilde{\varphi }(N',\succeq _{N'})$.

If $\pi \in \widetilde{\varphi }(N,\succeq ) \setminus Core(N,\succeq )$, then $(N,\succeq )\in \widetilde{\mathfrak {D}}$ and $\pi \in Core(N,\succeq ^a)$. To complete the proof, we show that $\pi _{N'}\in \widetilde{\varphi }(N',\succeq _{N'})$.

If $\widetilde{N}\subseteq N'$, then $\widetilde{\varphi }(N',\succeq _{N'}) = Core(N',\succeq _{N'})\cup Core(N',\succeq _{N'}^a)$. By consistency, $\pi \in Core(N,\mathbin {\succeq }^a)$ implies $\pi _{N'}\in Core(N',\succeq _{N'}^a) \subseteq \widetilde{\varphi }(N',\succeq _{N'})$.

If $\widetilde{N}\nsubseteq N'$, then $\widetilde{\varphi }(N',\succeq _{N'}) = Core(N',\succeq _{N'})$. It now suffices to prove that $\pi _{N'}\in {Core(N',\succeq _{N'})}$. Suppose, by contradiction, that $\pi _{N'}\not \in Core(N',\succeq _{N'})$. Then, there exists a blocking coalition $T\subseteq N'$ for $\pi _{N'}$ at preferences $\succeq _{N'}$. Recall that the only differences between preferences $\succeq$ and preferences $\succeq ^a$ lies in the position of coalition $\widetilde{N}$ in the preferences of agents in $\widetilde{N}$. Hence, since $\widetilde{N}\nsubseteq N'$, we have that $\succeq _{N'}=\succeq ^a_{N'}$. Thus, $T\subseteq N$ is also a blocking coalition for partition $\pi$ at preferences $\succeq ^a$. This contradicts $\pi \in Core(N,\mathbin {\succeq }^a)$.

Competition sensitivity. Consider a solvable hedonic game $(N,\succeq )$ and a solvable extension $(N',\succeq ')$ with $N'=N\cup \widehat{N}$.

The Core satisfies competition sensitivity (Proposition 2). Hence, for all partitions $\pi \in Core(N,\succeq )\subseteq \widetilde{\varphi }(N,\succeq )$ there exists a partition $\pi '\in Core(N',\succeq ')\subseteq \widetilde{\varphi }(N',\succeq ')$ such that for all coalitions $H\subseteq N$, $H\notin \pi$, and $H\in \pi '$, there exists at least an agent $i\in H$ such that $\pi (i)\succ '_{i}\pi '(i)$.

If $\pi \in \widetilde{\varphi }(N,\succeq ) \setminus Core(N,\succeq )$, then $(N,\succeq )\in \widetilde{\mathfrak {D}}$ and $\pi \in Core(N,\succeq ^a)$. By the competition sensitivity of the Core, for partition $\pi \in Core(N,\mathbin {\succeq }^a)$ there exists a partition $\pi '\in Core(N',\succeq '^a)\subseteq \widetilde{\varphi }(N',\succeq ')$ such that for all coalitions $H\subseteq N$, $H\notin \pi$, and $H\in \pi '$, there exists at least an agent $i\in H$ such that $\pi (i)\succ '^a_{i}\pi '(i)$. We complete our proof by showing that for the same agent $i\in H$, $\pi (i)\succ '_{i}\pi '(i)$.

If $i\notin \widetilde{N}$, then $\succ '_{i}=\succ '^a_{i}$ and we are done. Let $i\in \widetilde{N}$. Since $\pi \in Core(N,\succeq ^a)$ and $\pi '\in Core(N',\succeq '^a)$, by individual rationality, coalition $\widetilde{N}$ can neither be part of partition $\pi$ nor can it be part of partition $\pi '$, i.e., $\widetilde{N}\ne \pi (i)$ and $\widetilde{N}\ne \pi '(i)$. Recall that the only differences between preferences $\succeq _i$ and preferences $\succeq ^a_i$ lies in the position of coalition $\widetilde{N}$. Hence, $\pi (i)\succ '_{i}\pi '(i)$.

Resource sensitivity. Consider a solvable hedonic game $(N,\succeq )$ and a solvable extension $(N',\succeq ')$ with $N'=N\cup \widehat{N}$.

The Core satisfies resource sensitivity (Proposition 2). Hence, for all partitions $\pi '\in Core(N',\succeq ')\subseteq \widetilde{\varphi }(N',\succeq ')$ there exists a partition $\pi \in Core(N,\succeq )\subseteq \widetilde{\varphi }(N,\succeq )$ such that for all coalitions $H\subseteq N$, $H\in \pi$, and $H\notin \pi '$, there exists at least an agent $i\in H$ such that $\pi '(i)\succ '_{i}\pi (i)$.

If $\pi '\in \widetilde{\varphi }(N',\succeq ') \setminus Core(N',\succeq ')$, then $(N',\succeq ')\in \widetilde{\mathfrak {D}}$ and $\pi '\in Core(N',\succeq '^a)$. Note that if $(N,\succeq )\in \widetilde{\mathfrak {D}}$, then $\succeq '^a_N=\succeq ^a$ and if $(N,\succeq )\not \in \widetilde{\mathfrak {D}}$, then $\succeq '^a_N=\succeq '_N$. In both cases, ${Core(N,\succeq '^a_N)}\subseteq \widetilde{\varphi }(N,\succeq )$. By the resource sensitivity of the Core, for partition $\pi '\in Core(N',\mathbin {\succeq }'^a)$ there exists a partition $\pi \in Core(N,\succeq '^a_N)\subseteq \widetilde{\varphi }(N,\succeq )$ such that for all coalitions $H\subseteq N$, $H\in \pi$, and $H\notin \pi '$, there exists at least an agent $i\in H$ such that $\pi '(i)\succ '^a_{i}\pi (i)$. We complete our proof by showing that for the same agent $i\in H$, $\pi '(i)\succ '_{i}\pi (i)$.

If $(N,\succeq )\not \in \widetilde{\mathfrak {D}}$, then $\succeq '^a_N=\succeq '_N$ and we are done. Let $(N,\succeq )\in \widetilde{\mathfrak {D}}$ and $\succeq '^a_N=\succeq ^a$. If $i\notin \widetilde{N}$, then $\succ '_{i}=\succ '^a_{i}$ and we are done. Let $i\in \widetilde{N}$. Since $\pi \in Core(N,\succeq '^a_N)=Core(N,\succeq ^a)$ and $\pi '\in Core(N',\succeq '^a)$, by individual rationality, coalition $\widetilde{N}$ can neither be part of partition $\pi$ nor can it be part of partition $\pi '$, i.e., $\widetilde{N}\ne \pi (i)$ and $\widetilde{N}\ne \pi '(i)$. Recall that the only differences between preferences $\succeq _i$ and preferences $\succeq ^a_i$ lies in the position of coalition $\widetilde{N}$. Hence, $\pi '(i)\succ '_{i}\pi (i)$. $\square$