Coalitional unanimity versus strategy-proofness in coalition
formation problems
Koji TAKAMIYA∗
Economics, Niigata University
April 24, 2012

Abstract
This paper examines coalition formation problems from the viewpoint of
mechanism design. We consider the case where (i) the list of feasible coalitions(those coalitions which are permitted to form) is given in advance; and (ii) eachindividual’s preference is a ranking over those feasible coalitions which include
this individual. We are interested in requiring the mechanism to guarantee eachcoalition the “right” of forming that coalition at least when every member ofthe coalition ranks the coalition at the top. We name this property coalitional
unanimity. We examine the compatibility between coalitional unanimity andincentive requirements, and prove that if the mechanism is strategy-proof andrespects coalitional unanimity, then for each preference profile, there exists at
most one strictly core stable partition, and the mechanism chooses such a partition whenever available. Further, the mechanism is coalition strategy-proof andrespects coalitional unanimity if, and only if, the strictly core stable partition
uniquely exists for every preference profile.
JEL Classification— C71, C72, C78, D02, D71, D78.
Keywords— coalition formation problems, strict core stability, strategy-proofness,coalitional unanimity.

1

Introduction

1.1

Motivation

This paper examines coalition formation problems from the viewpoint of mechanism
design. In our version of coalition formation problems, the list of the coalitions which
are permitted to form are given a priori. These coalitions are called feasible coalitions. And each individual is assumed to have a preference ranking over those feasible
coalitions which contain this individual. To our knowledge, our model of coalition formation described above was introduced by Pápai (2004). Our model is general enoughto include several important models such as the marriage problem and the roommate∗

Contact. Faculty of Economics, Niigata University, 8050 2-no-cho Ikarashi Nishi-ku Niigata
JAPAN, 950-2181, tel: +81-25-262-6498, E-mail: takamiya@econ.niigata-u.ac.jp.

1

problem (Gale and Shapley, 1962), and the model of hedonic coalition formation introduced independently by Banerjee, Konishi and Sönmez (2001), Bogomolnaia andJackson (2002) and Cechlárová and Romero-Medina (2001).
Our theme is to identify conclusions from requiring mechanisms to guarantee grouprights. This embodies the idea that each group of people can make a decision on theirown at least when the decision is an internal concern of the group. This idea is annatural extension of the idea of “property right” from the individual level to the grouplevel. This study considers a specific form of group right requirement in the following
sense: We search for those mechanisms which guarantee that each feasible coalition canform that coalition at least when every member of the coalition ranks the coalition at the
top. We name this property of mechanisms coalitional unanimity. This property has
been studied in the context of the marriage problem by Takagi and Serizawa (2010).
We recognized the importance of this property from an ethical viewpoint and were
motivated to extend this property to a general coalition formation setting.1
From the viewpoint of mechanism design, those mechanisms not only satisfy thegroup right requirement described above but also have to be incentive compatible.
Thus our concern is the compatibility between these two kinds of requirements, namelygroup rights and incentive. In this paper, we concentrate on direct mechanisms. Thatis, a mechanism is a single-valued function which specifies a feasible partition of the
grand coalition for each profile of preferences. Further, we adopt strategy-proofness
and coalition strategy-proofness as the relevant incentive requirements. In summingup, our problem is to see what mechanisms are (coalition) strategy-proof and respects
coalitional unanimity at the same time.

1.2

Results

We postulate a class of preference domains which generalizes the strict preference domain. We prove that (i) if the mechanism is strategy-proof and respects coalitional
unanimity, then for each preference profile the mechanism chooses a strictly core stablepartition whenever available, and there exists at most one strictly core stable partition.
And we show that (ii) if the requirement of strategy-proofness in the above result isstrengthened to that of coalition strategy-proofness, then for every preference profile
there exists only one strictly core stable partition, and the mechanism chooses this partition. Further, the converse of the second result holds true: (iii) if for each preference
profile, there exists only one strictly core stable partition, and the mechanism chooses
this partition, then the mechanism is coalition strategy-proof and respects coalitional
unanimity.
Although our results are not impossibility results, they yield impossibility in many
special cases because the requirement that there exists only one (or at most one) strictly1

After the first version of this paper was submitted to this journal, we were pointed out that anaxiom essentially similar to our coalitional unanimity had been independently introduced in Rodrı́guezÁlvarez (2009). There the similar axiom was called top coalition and formulated as an auxiliary axiom
to be used in the proofs of his results, not as one of his main axioms. We will mention the paperof Rodrı́guez-Álvarez in Sec.4. His axiom is named after the concept of “top coalitions” of Banerjee,
Konishi and Sönmez (2001). We will mention the relationship between coalitional unanimity and their
top coalition concept after the axiom is formally defined. (See Sec.2.2.)

2

core stable partition for every preference profile is very strong. An example where theimpossibility obtains is the marriage problem (Takagi and Serizawa, 2010). So our
results reveal a severe limitation on the possibility of strategy-proof mechanisms which
respect coalitional unanimity.
In a broader perspective, our results exhibit the conflict between strategy-proofness
and the guarantee of group rights. The conclusions of our results are very similar
to that of the well-known result by Sönmez (1999): In a general model of discrete
allocations which contains the present class of problems as a special case, strategyproofness, Pareto efficiency and individual rationality together imply that any twostrict core allocations are Pareto indifferent (which means the strict core is regarded as
unique in terms of welfare) for those preference profiles for which the strict core is not
empty, and that the mechanism chooses a strict core allocation for those profiles. Thusin the context of coalition formation, the conflict between strategy-proofness and grouprights shows a similar quality as the well-known conflict between strategy-proofness andPareto efficiency (plus individual rationality), which has been central to the study ofstrategy-proof mechanisms.

1.3

Related works

We note three papers highly related to the present work. Pápai (2004) introduces
the coalition formation model which we study in this paper, and also studies uniquestrict cores for the case of strict preferences. She provides a necessary and sufficientcondition, called the single-lapping condition, that the set of feasible coalitions is tosatisfy for the coalition formation problem to have a unique core stable partition for all
the preference profiles.2 Further, she shows that under this condition, the mechanism
which chooses the strict core stable partition for every preference profile is the uniquemechanism which is strategy-proof, individually rational and Pareto efficient.
Takagi and Serizawa (2010) study strategy-proof mechanisms for marriage problems(Gale and Shapley, 1962). They introduce a property called “pairwise unanimity,”
which is the version of coalitional unanimity in the context of the marriage problem.
They prove that there does not exist any mechanism which is strategy-proof and respects pairwise unanimity. This result can be derived from the first one of our three
results. Their work has directly motivated the present work.
Toda (2006) studies set-valued rules for marriage problems, and independently introduces a set-valued version of the pairwise unanimity of Takagi and Serizawa (2010).3
He proves that any rule which is Maskin monotonic and respects coalitional unanimity
is a subcorrespondence of the stable correspondence. He also obtains characterizationsof the stable correspondence using Maskin monotonicity and additional properties.
2

Pápai (2004) actually deals with the core stability rather than strict core stability. But these twoconcepts are equivalent when preferences are strict, as is assumed in her paper.
3
Toda (2006) calls this property mutually best.

3

2

Preliminaries

2.1

Model of coalition formation

Let N = {1, 2, · · · , n} with n ≥ 2 be the set of individuals. A coalition is anonempty subset of N . A coalition formation problem is a list (N, F , ). Here F
is the set of feasible coalitions. F is a nonempty subset of the set of all coalitions,{S | ∅ =6 S ⊂ N }. For each i ∈ N , F (i) denotes the set of feasible coalitions that
contain i, that is, {S | i ∈ S ∈ F }. We assume for any i ∈ N , {i} ∈ F .
A partition of N is called a feasible partition if the partition consists only offeasible coalitions. Let x be a feasible partition, and let i ∈ N . Then x(i) denotes thecoalition in x which contains i. Let us denote by X(F ) the set of feasible partitions.
In the following, as long as there is no ambiguity, we refer to them simply “partitions.”
And we also call them “outcomes” depending on the context.
= (i )i∈N is a preference profile. For each i ∈ N , i is a weak ordering (complete and transitive binary relation) over F (i). As usual, i denotes the asymmetricpart, and ∼i denotes the symmetric part of i .
Note that we are assuming that preferences are hedonic, that is, for any individual,
preferences depend only on the composition of the coalition of which that individual
is a member.4 Let x, y ∈ X(F ). Then abusing notation, let us denotex i y(1)x(i) i y(i).

(2)

if and only if

Likewise, we often regard preference relations i defined on F (i) as if they are definedon X(F ).
As far as we know, the present model was first studied by Pápai (2004). Thismodel generalizes the model of hedonic coalition formation independently introduced by
Banerjee, Konishi and Sönmez (2001), Bogomolnaia and Jackson (2002), and Cechlárová
and Romero-Medina (2001), where all coalitions are assumed to be feasible. Also ourmodel includes as a special case the well-known marriage problems (two-sided oneto-one matching problems) and roommate problems (one-sided one-to-one matchingproblems) as in Gale and Shapley (1962). On the other hand, although our model
also includes college admission problems (two-sided many-to-one matchings), our results are not applicable to those problems. This is because in those matching problems,
preferences are assumed to have some special structures (such as “responsiveness” or“separability” (see Roth and Sotomayor (1990) for their definitions)), which are notcompatible with our domain assumptions to be stated later.

2.2

Properties of mechanisms

For each i ∈ N , Di is the (nonempty) set of the preferences relations admissible to i.
Denote D := D1 × D2 × · · · × Dn .
4

The term “hedonic” in this context was coined by Dréze and Greenberg (1980).

4

Let a list (N, F , D) be given. A mechanism f is a single-valued function f :D → X(F ).5 Let i ∈ N , and let i ∈ Di , −i ∈ D−i and ˜i ∈ Di . We say that imanipulates f at (−i , i ) by ˜i if
˜ i ) i f (−i , i ).
f (−i , (3)We say that f is strategy-proof if there exists no i who manipulates f at any (−i , i )by any ˜i .
Let S be a coalition, and let S ∈ DS , −S ∈ D−S and ˜S ∈ DS . We say that S
manipulates f at (−S , S ) by ˜S if
˜ S ) i f (−S , S ), and∀i ∈ S, f (−S , ˜ S ) i f (−S , S ).
∃i ∈ S, f (−S , 

(4)
(5)

We say that f is coalition strategy-proof if there exists no S who manipulates f atany (−S , S ) by any ˜S .
We say that f is individually rational if for any i ∈ N , and any ∈ D,
f ()(i) i {i}.

(6)We introduce our main axiom. A mechanism is said to respect coalitional unanimity if it satisfies the property described as follows: For any feasible coalition, if thecoalition is top-ranked for every member of this coalition, then the mechanism recommends the formation of this coalition. The formal description is as follows: We saythat f respects coalitional unanimity if the following is satisfied: For any ∈ D,
and any S ∈ F , if∀i ∈ S, (∀T ∈ F (i), S i T ),(7)

S ∈ f ()

(8)

then

Note that coalitional unanimity may not be well-defined when preferences include
indifferences. Because with indifferences it may be the case that two coalitions which
are both top-ranked by their members have a nonempty intersection. In this case, it
is obviously impossible that these two coalitions present themselves in one partition sothis axiom is contradictory. We will impose an assumption (Assumption 2 in Sec.3.1)
on the preference domain to exclude such cases and make the axiom well-defined.
Coalitional unanimity is a generalization of the axiom “pairwise unanimity” introduced by Takagi and Serizawa (2010) in the context of marriage problems (two-sided
one-to-one matching problems), a special case of the present model. Pairwise unanimity
is identical with coalitional unanimity in this class of problems.6
5

In this paper, we consider direct mechanisms only.
Takagi and Serizawa (2010) defines an analogous axiom in the context of college admission problems (many-to-one matching problems) under the same name “pairwise unanimity.” This axiom
requires that the mechanism respects the unanimity by a college-student pair. We note that thisaxiom is not a special case of our coalitional unanimity. Because a college-student pair does notnecessarily form a coalition by themselves since one college can be matched with many students.
65

It is worth mentioning that the concept of “top coalitions” of Banerjee, Konishiand Sönmez (2001) is related to coalitional unanimity. Let ∅ 6= S ⊂ V ⊂ N . Then
S is said to be a top coalition of V if for any i ∈ S and any T ⊂ V with T ∈ F (i),S i T .7 Given this definition, f satisfies coalitional unanimity if and only if for any
S ∈ F and any ∈ D, if S is a top coalition of N , then S ∈ f ().

2.3

Strict core stability

Let a problem (N, F , ) be given. And let x ∈ X(F ), and S ∈ F . Then we say that
S blocks x if 
∀i ∈ S, S i x(i) & ∃j ∈ S : S j x(j) .
(9)
A partition x is said to be strictly core stable if no feasible coalition blocks x.
The concept of strict core stability is a refinement of core stability which is definedby a weaker notion of blocking obtained by replacing the formula (9) in the above withthe following:∀i ∈ S, S i x(i).

(10)

Note that these two core concepts are equivalent if preferences are all strict, i.e. S ∼i T
implies S = T .
The strict core stable correspondence is the set-valued function which specifies
the set of strict core stable partitions for each preference profile. Let us denote thestrict core stable correspondence by C .

3Results

3.1

Domain assumptions

We define a class of domains by two assumptions. In the following, we fix the elements(N, F , D). Correspondingly, let us abbreviate X(F ) to X.
In the definitions in the sequel, we consider for each i ∈ N , a partition Pi of theset X. For any x ∈ X, let Pi (x) denote the cell of the partition Pi which contains x.
Assumption 1 D is defined such that for any i ∈ N , there exists a partition Pi of
X such thatnoDi = i | ∀x, y ∈ X, x ∈ Pi (y) ⇔ x(i) ∼i y(i) ,(11)
and∀x, y ∈ X, ∃i ∈ N : x 6∈ Pi (y).
7(12)

Here we are giving one of possible definitions of top coalitions extended to the present setting.
The original definition by Banerjee et al. is provided for the coalition formation model where any
coalitions are feasible. Our definition reduces to theirs if we assume F = 2N \ {∅}.

6

Note that by Assumption 1, for each individual i, the partition Pi constitutes theindifference class. That is, in any of his admissible preferences, any two outcomes are
indifferent for individual i if, and only if, these two outcomes belong to the same cellof the partition Pi .
Assumption 1 means that indifferences are incorporated in the domain D in thefollowing way: For each individual i, the indifference class Pi is given a priori, andthis individual ranks the outcomes as if he strictly ranks these indifference sets, i.e. thecells of Pi . And the set of admissible preferences Di for individual i exactly consists ofall such rankings. Additionally, the profile of indifference classes (Pi )i∈N is required
to be such that for any two distinct outcomes, there is at least one individual who is
not indifferent between the two outcomes.
Obviously, the indifference class Pi of X uniquely corresponds to the indifferenceclass P̃i of F (i) in the way that x ∈ Pi (y) if and only if x(i) ∈ P̃i (y(i)). Thus in thefollowing, as long as no ambiguity arises, let us equate these two indifference classes
and denote them by the same “Pi .”The same domain condition as Assumption 1 is found in Takamiya (2007), whichcalls a domain satisfying this assumption an “essentially strict preference domain.”Preferences which satisfy Assumption 1 naturally arise when some individual cares
only about a part of the composition of the coalition which this individual belongs to.
Let a profile of indifference classes (Pi )i∈N of X be given, and let D satisfy Assumption 1 with this (Pi )i∈N . Then we impose on (Pi )i∈N the following assumption.
This assumption is in order to make coalitional unanimity well-defined.
Assumption 2 For any i ∈ N and any S, T ∈ F with S 6= T ,S ∈ Pi (T ) ⇒ ∃j ∈ S ∩ T : S 6∈ Pj (T ) .

(13)

Note that Assumption 2 implies the following fact which will be used in the proofsof our theorems.
∀i ∈ N, {i} ∈ Pi .
(14)
This means that no singleton is indifferent to any other coalition.
Example 1 We present examples for which Assumptions 1 and 2 are both satisfied.
(1) The strict preference domain is the domain such that each Di consists exactlyof those preferences which satisfy∀i ∈ N, ∀S, T ∈ F (i), S ∼i T ⇒ S = T.

(15)

If the domain is the strict preference domain, then Assumption 1 and 2 are satisfied:
In this case, for each individual i, the indifference class Pi is set to be the finest
partition {{S} | S ∈ F (i)}. Then the two assumptions are satisfied trivially. The strict
preference domain is common in the literature of matching and coalition formation.
(2) Since the strict preference domain rules out indifferences in preferences, it isworthwhile to have a natural example which incorporates indifferences. We give thefollowing one.
7• The set of individuals N is such that N = N1 ∪ N2 ∪ · · · ∪ Nm , where (i) m ≥ 1,(ii) for any t = 1, 2, · · · m, Nt 6= ∅, and (iii) for any t, s = 1, 2, · · · m with t 6= s,
Nt ∩ Ns = ∅. That is, N is partitioned into m subgroups.
• The set of feasible coalitions F is such thatno noF = S ⊂ N | ∀t, |Nt ∩ S| = 1 ∪ {i} | i ∈ N .

(16)

That is, each feasible coalition is (i) a coalition consisting of m components, andeach t-th component is an individual from the set Nt , or (ii) a singleton.
• For each t and each i ∈ Nt , the indifference class Pi is set as follows:∀S, T ∈ F (i), S ∈ Pi (T ) ⇔ S ∩ Nt+1 = T ∩ Nt+1 ,(17)

where Nm+1 = N1 . That is, an individual in the t-th group Nt has “strict
preferences” over the (t + 1)-th group Nt+1 .
It is easy to check that Assumptions 1 and 2 are satisfied. This example is interpreted as m-sided one-to-one matching problems with “circular” preferences (in thesense that individuals in Nt have preferences over Nt+1 ). In the case m = 2 these
problems are two-sided matching problems, i.e. well-known marriage problems (Galeand Shapley, 1962). And the case m = 3 has been raised by Knuth (1976) and studiedin Ng and Hirschberg (1991) and subsequent literature.

3.2

Statements of results

In all of our results and proofs in the sequel, it is postulated that the domain D satisfies
Assumptions 1 and 2.
Theorem 1 If the mechanism f is strategy-proof and respects coalitional unanimity,
then for any ∈ D, either C () = {f ()} or C () = ∅.
Remark 1 From Theorem 1, an impossibility result follows: If for some preference
profile there are two or more strictly core stable partitions, then there is no mechanism
which is strategy-proof and respects coalitional unanimity. The case of the marriage
problem (Gale and Shapley, 1962), which is dealt with by Takagi and Serizawa (2010), is
one of such cases. Two other examples are the roommate problem (Gale and Shapley,1962) and the hedonic coalition formation problem (Banerjee, Konishi and Sönmez
2001, Bogomolnaia and Jackson 2002, and Cechlárová and Romero-Medina 2001).
Next, we strengthen the requirement of strategy-proofness in the above theorem tothat of coalition strategy-proofness. Then the nonemptiness of the strict core follows.
Theorem 2 If the mechanism f is coalition strategy-proof and respects coalitional unanimity, then for any ∈ D, C () = {f ()}.
The converse of Theorem 2 also holds true.
8

Theorem 3 If for any ∈ D, C () = {f ()}, then the mechanism f is coalition
strategy-proof and respects coalitional unanimity.
Remark 2 Pápai (2004) gives a necessary and sufficient condition which the set of
feasible coalitions is to satisfy for the strictly core stable partition to be unique for all
strict preference profiles. This condition is called the “single-lapping property.” Pápai
also proves that if the set of feasible coalitions satisfies the single-lapping property,
then the mechanism which chooses strictly core stable partitions is the only mechanism
which is strategy-proof, individually rational and Pareto efficient. The significance of
our Theorems 2 and 3 is that they provide another characterization of the single-valued
strict core.

3.3

ProofsFirst of all, we confirm that coalitional unanimity is well-defined.
Lemma 1 For any ∈ D, and any S 1 , S 2 ∈ F , if for each k = 1, 2, and any i ∈ S k ,
∀T ∈ F (i), S k i T , then S 1 ∩ S 2 = ∅.
Proof. Suppose the contrary, that is, there are some S 1 , S 2 ∈ F for which every
member of each coalition ranks that coalition at the top, and S 1 ∩ S 2 6= ∅. Then foreach i ∈ S 1 ∩ S 2 , S 1 ∼i S 2 . This clearly contradicts Assumption 2. 2
To proceed further, we need to introduce some notations.
• Let  be a preference profile. Let x ∈ X and i ∈ N . Then let us define thepreference relation “ xi ” as follows: If x(i) = {i}, then xi =i ; otherwise, xi
is such that it satisfies the following three conditions:(i) x(i) xi {i},(ii) 6 ∃S ∈ F (i) \ {{i}}, x(i) xi S xi {i},(iii) ∀S, T ∈ F (i) \ {{i}}, (S i T ) ⇔ (S xi T ).
That is, xi is the preference ranking which is obtained from i by moving {i}to the position immediately below x(i) and leaving other positions the same.
↑(x)• Further, let us define the preference relation “ itwo conditions:↑(x)(i) ∀S ∈ F (i) \ Pi (x(i)), x(i)i” so as to satisfy the following

S,
↑(x)

(ii) ∀S, T ∈ F (i) \ Pi (x(i)), (S i T ) ⇔ (S i

T ).

↑(x)

That is, iis the preference ranking which is obtained from i by moving
up the indifference set including x(i) to the top and leaving other positions thesame.
x ↑(x)• Finally, let “ x↑. That is, x↑i ” be a shorthand for (i )i is obtained by
performing the first and the second operations defined above sequentially on i .

9

3.3.1

Proof of Theorem 1

Our proof starts with picking up x ∈ C () for an arbitrary ∈ D such that C () is
not empty, and ends with establishing x = f (). This is done by induction in the two
steps described as follows:
Step 1. Prove (i) and (ii).
(i) f (x↑ ) = x.
(ii) for any i ∈ N , f (x↑−i , i ) = x.
Step 2. Prove that (iii) implies (iv) for any given m such that 0 < m < n.
(iii) for any T ⊂ N with |T | = m, f (x↑−T , T ) = x.
(iv) for any T ⊂ N with |T | = m + 1, f (x↑−T , T ) = x.
In the following, we complete Step 1 via a sequence of lemmas. In the sequel, until
the end of the proof of this theorem, we assume that f is strategy-proof and respects
coalitional unanimity.
Lemma 2 f is individually rational.
Proof. Suppose f is strategy-proof and respects coalitional unanimity, but is notindividually rational. Then there are some ∈ D and i ∈ N for which{i} i f ()(i)(18)

Let ?i be a preference relation of i such that∀S ∈ F (i) \ {{i}}, {i} ?i S.

(19)

Then the coalitional unanimity of f impliesf (−i , ?i )(i) = {i}.

(20)f (−i , ?i ) i f (),(21)This implies

which means the violation of strategy-proofness. 2

Lemma 3 For any x ∈ X and any ∈ D, f (x↑ ) = x.
Proof. Immediate from the coalitional unanimity of f . 2
Lemma 4 For any ∈ D, if x ∈ C (), then for any i ∈ N , f (x↑−i , i ) ∼i x.

10

Proof. Let us denote f (x↑−i , i )(i) by S. Suppose the conclusion of the lemma does
not hold, i.e., x(i) 6∼i S. Then either x(i) i S or S i x(i) is true.
Case 1. Suppose x(i) i S. That is,x↑x↑
f (x↑−i , i ) i f (−i , i ),(22)

which violates strategy-proofness, a contradiction.
Case 2. Suppose S i x(i). Note that x(i) i {i} since x ∈ C (). Then S i x(i)implies S i {i}. Thus S 6= {i}.
Pick up j ∈ S with j 6= i. Then by Lemma 2 and the fact (14), we have S x↑j {j}.
x↑
Then this and the way  is defined together imply
S j x(j).

(23)(Because if x(j) j S on the contrary, then the definition of xj implies {j} xj S. Andx ↑(x)
since x↑
, this implies also {j} x↑j means (j )j S. This is a contradiction.) Notethat this holds true for all j ∈ S \ {i}. Thus S blocks x under , which contradicts
our supposition x ∈ C (). 2
Lemma 5 For any ∈ D and any T ⊂ N with T 6= ∅, if x ∈ C () and for any i ∈ T ,x↑
f (x↑−T , T ) ∼i x, then f (−T , T ) = x.
Proof. Let x ∈ C () and y = f (x↑−T , T ). And assume∀i ∈ T, y(i) ∼i x(i).

(24)

Suppose that for some i? ∈ N \ T,?
y(i? ) 6∼x↑
i? x(i ).

(25)

Note that x(i? ) ∩ T 6= ∅ because otherwise by the coalitional unanimity of f we would
have y(i? ) = x(i? ). Then since f is individually rational (Lemma 2),∀i ∈ x(i? ) \ T, y(i) x↑i {i}.

(26)

This and the way x↑ is constructed together imply∀i ∈ x(i? ) \ T, y(i) i x(i).

(27)

y(i? ) i? x(i? ).

(28)

Then (25) and (27) imply(24), (27) and (28) together imply that y(i? ) blocks x under . But this contradicts
our supposition x ∈ C (). Therefore we have ∀i ∈ N \ T, y(i) ∼x↑
i x(i). This and(24) imply ∀i ∈ N, y(i) ∼i x(i). Further, this and Assumption 1 imply that y = x, thedesired conclusion. 2

11

By Lemmas 4 and 5, we conclude that for any ∈ D, any i ∈ N and any x ∈ C (),f (x↑−i , i ) = x.

(29)This completes Step 1.
Now we proceed to Step 2, which as we have stated is to be done by induction. Letx ∈ C (). Our induction hypothesis is in the below.
Induction Hypothesis (IH) Let m be a natural number such that 0 < m < n. Thenfor any T ⊂ N with |T | = m,f (x↑−T , T ) = x.

(30)

Now under (IH), we prove that for any T ⊂ N with |T | = m + 1, (30) is true.
Let T ⊂ N with |T | = m + 1. Let j ∈ T . Then by (IH),x↑
f (x↑−T , T \{j} , j ) = x.

(31)

f (x↑−T , T \{j} , j ) = y.

(32)

Let us denoteIn the following, we prove that x(j) ∼j y(j).
Case 1. First, note that x(j) 6j y(j). Because otherwise j manipulates the outcome
by reporting x↑
j under the true preference j , which violates the strategy-proofnessof f .
Case 2. Next, supposey(j) j x(j).

(33)

Then since x ∈ C (), x(j) j {j}. This implies y(j) j {j}. Thus y(j) contains somemember other than j.
Now we prove that the above supposition y(j) j x(j) implies that there is somek ∈ (y(j) \ {j}) ∩ T for which x(k) k y(j). Suppose the contrary. That is,∀k ∈ (y(j) \ {j}) ∩ T, y(j) k x(k).

(34)

Then the individual rationality of f (Lemma 2) implies for any l ∈ (y(j)\{j})∩(N \T ),we havey(j) x↑l {l}.

(35)

This and the construction of x↑ together imply∀l ∈ (y(j) \ {j}) ∩ (N \ T ), y(j) l x(l).

(36)

Then (33), (34) and (36) imply that y(j) blocks x under . But this contradictsx ∈ C (). Thus we conclude that for some k ∈ (y(j) \ {j}) ∩ T ,x(k) k y(j).
12

(37)

However, (IH) impliesx↑
f (x↑−T , T \{j,k} , j , k ) = x.

(38)

Recall that we have definedf (x↑−T , T \{j,k} , j , k ) = y.

(39)

Thus (37), (38) and (39) together imply that k manipulates the outcome by reportingx↑
k under the true preference k , which violates the strategy-proof of f . Thus weconclude y(j) 6j x(j). This completes Case 2.
By the above arguments (Case 1 and Case 2) we have x(j) ∼j y(j). And since j
has been taken arbitrarily from T , we have∀j ∈ T, f (x↑−T , T ) ∼j x.

(40)

Then by (40) and Lemma 5 together imply
f (x↑−T , T ) = x.

(41)This completes Step 2. 2

3.3.2

Proof of Theorem 2

By Theorem 1, for any ∈ D, if C () 6= ∅, then C () = {f ()}. Thus to prove
Theorem 2, it suffices to prove that for any ∈ D, C () 6= ∅ if f is coalition strategyproof and respects coalitional unanimity.
Suppose that for some ∈ D, C () = ∅. Let us denote f () = x. Then there issome S ∈ F which blocks x. That is, 
∀i ∈ S, S i x(i) & ∃j ∈ S, S j x(j)(42)
For each i ∈ S, let ?i be a preference relation of i such that∀T ∈ F (i), S ?i T.

(43)

Then the coalitional unanimity of f implies for any i ∈ S
f (−S , ?S )(i) = S.
Then (42) and (44) together imply

 

?
?
∀i ∈ S, f (−S , S ) i f () & ∃j ∈ S, f (−S , S ) j f ()which means the violation of coalition strategy-proofness. 2

13

(44)

(45)

3.3.3

Proof of Theorem 3

Let f be such that for any ∈ D, {f ()} = C (). It is immediate that such f
respects coalitional unanimity. We prove such f is coalition strategy-proof. Suppose
the contrary. Then for some S ⊂ N with S 6= ∅, some ∈ D and some ?S ∈ DS ,

 

?
?
∀i ∈ S, f (−S , S ) i f () & ∃j ∈ S, f (−S , S ) j f ()(46)
Denote x = f () and y = f (−S , ?S ).
↑(y)
By assumption (i.e. {f } = C ), we have {x} = C (). Let us consider S . Then↑(y)clearly the change of preferences from S to S does not alter the strict core stablepartition because the relative position of x to y does not alter in this preference change.
Thus we have↑(y){x} = C (−S , S ).

(47)

Similarly by assumption, we have {y} = C (−S , ?S ). Then again evidently the change↑(y)of preferences ?S to S does not alter the strict core, that is,↑(y){y} = C (−S , S ).

(48)(47) and (48) imply x = y, which contradicts our supposition (46). 2

4

Concluding Remarks

Here we conclude our paper mentioning two directions of extension or variation. The
first direction is as follows. Our results have been proved under some domain assumptions which are not compatible with special preference structures commonly assumed in two-sided many-to-one matching problems (college admission problems) suchas “responsiveness” and “separability.” (See Roth and Sotomayor (1990) for theirdefinitions.) So one of our interests in the future research is to see whether similar results hold for some domains which permit such preference structures. Takagi
and Serizawa (2010) have already shown that in the context of many-to-one matchingproblems an impossibility theorem similar to that in the marriage problem holds true.
Rodrı́guez-Álvarez (2009) considers a coalition formation model on the separable preference domain and other domains, and characterizes a certain coalition formation ruleby strategy-proofness and additional properties other than coalitional unanimity. His
coalition formation model is different from ours in the point that it does not explicitly incorporate feasibility constraints on coalitions. However, the characterized rule isdefined using the single-lapping property (Pápai, 2004) and closely related to the corestability in the presence of feasibility constraints.
The second direction is to consider the weakening of incentive requirements. In
this direction, we announce that Takamiya (2008) deals with the case of Nash implementation. There a version of coalitional unanimity for social choice correspondences(i.e. multi-valued rule) is defined, and the following result is shown: Under some regular assumptions, a social choice correspondence is Nash implementable and respects
14coalitional unanimity if and only if the correspondence is the strictly core stable correspondence.
Acknowledgments I am very thankful to the editors in charge and two anonymousreferees for their various suggestions which have improved this paper. I thank Nobuo
Akai, Yuji Fujinaka, Junichiro Ishida, Kazuhiko Hashimoto, Kentaro Hatsumi, Yoshio
Kamijo, Kazuharu Kiyono, Takumi Kongo, Koichi Suga, Shohei Takagi, Katsuya Takii,
Shiro Yabushita and other participants in the seminars at Waseda University and Osaka
University for various comments and discussions. This research is partially supported
by Grant-in-Aid for Scientific Research of the Ministry of Education, Culture, Sports,
Science and Technology of Japan, No.21730155 and No.23730188. All errors are myown responsibility.

References[1] Banerjee S, Konishi H, and Sönmez T (2001) Core in a simple coalition formation
game. Social Choice and Welfare 18: 135–53.
[2] Bogomolnaia A and Jackson MO (2002) The stability of hedonic coalition structures. Games and Economic Behavior 38: 201–30.
[3] Cechlárová K and Romero-Medina A (2001) Stability in coalition formation games.
International Journal of Game Theory 29: 487–94.
[4] Dréze J and Greenberg J (1980) Hedonic coalitions: optimality and stability.
Econometrica 48: 987–1003.
[5] Gale D and Shapley L (1962) College admissions and the stability of marriage.
American Mathematical Monthly 69: 9–15.
[6] Knuth D (1976) Mariages stables et leurs relations avec d’autre problèmes combinatoires, Les Presses de l’université de Montréal.
[7] Ng C and Hirschberg D (1991) Three-dimensional stable matching problems.
SIAM Journal of Discrete Mathematics 4: 245–52.
[8] Pápai S (2004) Unique stability in simple coalition formation games. Games andEconomic Behavior 48: 337–54.
[9] Rodrı́guez-Álvarez C (2009) Strategy-proof coalition formation. International
Journal of Game Theory 38: 431–52.
[10] Roth A and Sotomayor M (1990) Two-Sided Matching: A Study in Game Theoretic
Modeling and Analysis, Econometric Society Monograph, vol. 18, Cambridge Univ
Press.
[11] Sönmez T (1999) Strategy-proofness and essentially single-valued cores. Econometrica 67: 677–89.
15[12] Takagi S and Serizawa S (2010) An impossibility theorem in matching problems.
Social Choice and Welfare 35: 245–66.
[13] Takamiya K (2007) Domains of social choice functions on which coalition strategyproofness and Maskin monotonicity are equivalent. Economics Letters 95: 348–54.
[14] Takamiya K (2008) Maskin monotonic coalition formation rules respecting grouprights. Mimeo. Niigata University.
[15] Toda M (2006) Monotonicity and consistency in matching markets, International
Journal of Game Theory 34: 13–31.

16