Maskin monotonic coalition formation rules
respecting group rights
Koji TAKAMIYA∗
Economics, Niigata University
January 7, 2010

Abstract
This paper examines a class of coalition formation problems where (i) the listof feasible coalitions (those coalitions which are permitted to form) is given inadvance; and (ii) each individual’s preference depends only on which coalition
this individual belongs to. We are interested in searching for coalition formation
rules which are Maskin monotonic and respect coalitional unanimity. Here arule is said to respect coalitional unanimity if the rule ensures each coalition
the “right” of forming that coalition whenever all the members of the coalition
rank the coalition at the top. We prove that a rule is Maskin monotonic andrespects coalitional unanimity if, and only if, the rule coincides with the strict
core stable correspondence. We also consider the implications of this result toNash implementation and coalition strategy-proofness.
JEL Classification— C71, C72, C78, D02, D71, D78.
Keywords— coalition formation problems, coalitional unanimity, implementation, Maskin monotonicity, strict core stability.

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 arepermitted to form are given a priori. These coalitions are called feasible coalitions. Eachindividual is assumed to have a preference ranking over those feasible coalitions whichcontain this individual. Thus we are ruling out “externalities” in the sense that thepeople outside the coalition influence the welfare level of the members of the coalition.
To our knowledge, our model of coalition formation described above was introduced∗

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

by Pápai (2004). Our model is general enough to include several important models
such as the marriage problem and the roommate problem (Gale and Shapley, 1962),
and the model of hedonic coalition formation introduced independently by Banerjee,
Konishi and Sönmez (2001), Bogomolnaia and Jackson (2002), and Cechlárová andRomero-Medina (2001).
In this study, we consider coalition formation rules, which deterministically specify,
for each profile of preferences, a nonempty set of outcomes (formations of coalitions)desirable from the viewpoint of the mechanism designer. Our theme is to identify conclusions from imposing on coalition formation rules the guarantee of group rights. This
embodies the idea that each group of people can make a decision on their own at least
when the decision is an internal concern of the group. This idea is a natural extension of the idea of “property right” from the individual level to the group level. This
study considers a specific form of group right requirement in the following sense: We
search for those coalition formation rules which ensure each feasible coalition the rightof forming that coalition at least when all the members of the coalition rank the coalitionat the top. We name this property of coalition formation rules coalitional unanimity.
Evidently, this is a natural requirement in the context of coalition formation without
externalities. This property has been studied in the context of the marriage problem
by Takagi and Serizawa (2006) and Toda (2006). We find this property favorable froman ethical viewpoint and were motivated to extend this property to a general coalition
formation setting.
From the viewpoint of mechanism design, coalition formation rules have to be incentive compatible. We require that coalition formation rules be Maskin monotonic.
Although Maskin monotonicity itself is not an “incentive property,” it is deeply related to various concepts of implementation. For example, as well-known, Maskin
monotonicity is a necessary condition for Nash implementation (Maskin, 1985, 1999).
When the rule is single-valued, on some preferences domains, the property is equivalent to strategy-proofness or coalition strategy-proofness (Muller and Satterthwaite,
1977; Takamiya, 2007; Bochet and Klaus, 2008). Also it is a necessary and sufficientcondition for Nash implementation when mechanisms are allowed to utilize randomization (Bochet, 2007; Benoit and Ok, 2008). Further, recent considerations on therobustness of implementation to incomplete information have found their relationships
with Maskin monotonicity. For instance, some forms of robust implementation in undominated Nash equilibrium require social choice rules to be Maskin monotonic whereas
under complete information the implementation is possible for non-Maskin monotonic
rules. (Chung and Ely, 2003; Kunimoto, 2007).1 For these known facts, it is highly
important to consider Maskin monotonic rules.
1

In all the results listed above, deterministic social choice rules are postulated. However, Maskin
monotonicity is also relevant to the nondeterministic case: Bochet and Sakai (2005) shows that Maskin
monotonicity is a necessary and sufficient condition for the Nash implementation of stochastic social
choice rules.

2

1.2

Results

All of our results are proved under some domain assumptions, which generalize thestrict preference domain, which is commonly assumed in the literature of matchingproblems. As stated above, our problem is to see what coalition formation rules are
Maskin monotonic and respect coalitional unanimity at the same time. Answering
this question, we prove that (i) a rule is Maskin monotonic and respects coalitional
unanimity if, and only if, the rule coincides with the strict core stable correspondence.
Further, we proceed to studying the implications of the above result to Nash implementation and coalition strategy-proofness: We prove that (ii) the strict core stablecorrespondence is Nash implementable if the correspondence is nonempty-valued andthere are at least three individuals. Since Maskin monotonicity is a necessary condition
for Nash implementability, we conclude from the two results in the above that (iii) when
there are at least three individuals, a rule is Nash implementable and respects coalitional
unanimity if, and only if, the rule coincides with the strict core stable correspondence.
Interestingly, it follows from these results that the Nash implementability problem of
the rule which respects coalitional unanimity is reformulated as the existence problem
of strict core stable partitions.
Regarding coalition strategy-proofness, from (i) of our results, we derive the following: (iv) Given that a rule is single-valued, the rule is coalition strategy-proof andrespects coalitional unanimity if, and only if, the rule coincides with the strict corestable correspondence (thus the strict core stable partition must exist and be unique forall the preference profiles). This result follows from the conditions for the equivalenceof Maskin monotonicity and coalition strategy-proofness given by Takamiya (2007).

1.3

Related works

In the following, we note five papers closely related to our paper. Pápai (2004a)
introduces the coalition formation model which we study in this paper, and studies
singleton cores under strict preferences. (We note that core stability, which is definedby strong blocking, and strict core stability, which is defined by weak blocking, areequivalent to each other when preferences are strict.) She provides a necessary andsufficient condition, called the single-lapping condition, that the set of feasible coalitions
is to satisfy for that the set of core stable partitions is a singleton for every profile ofstrict preferences. Further, she shows that under this condition, the core stable rule isthe unique rule which is strategy-proof, individually rational and Pareto efficient.
Pápai’s another work (Pápai, 2004b) deals with the existence problem of core stablepartitions. It gives a necessary and sufficient condition that the set of feasible coalitions
is to satisfy for that the set of core stable partitions is nonempty for every profile ofstrict preferences.
Takagi and Serizawa (2006) study the marriage problem and introduce a property
called “pairwise unanimity,” which coincides with coalitional unanimity in the context
3

of the marriage problem.2 They consider single-valued rules and prove that there does
not exist any matching rule which is strategy-proof and respects pairwise unanimity.
Toda (2006) also studies marriage problems, and independently introduces a property similar to the pairwise unanimity of Takagi and Serizawa (2006).3 He proves thatany rule which is Maskin monotonic and respects coalitional unanimity is a subcorrespondence of the stable correspondence (which is equivalent to the strict core stablecorrespondence under strict preferences). This result is generalized in our Theorem
1. Further, Toda obtains characterizations of the stable correspondence using Maskin
monotonicity and additional properties.
Takamiya (2008) studies single-valued rules for the same coalition formation model
as in the present paper. He proves that if a single-valued rule is strategy-proof andrespects coalitional unanimity, then for each preference profile, the set of strict corestable partitions is a singleton or empty and the rule chooses the strict core stablepartition whenever available. This result generalizes the above-mentioned impossibility
theorem in the marriage problem by Takagi and Serizawa (2006).

2

Preliminaries

2.1

Model of coalition formation

Let N = {1, 2, · · · , n} with n ≥ 2 be the set of individuals. A coalition is a nonempty
subset of N . A coalition formation problem is a list (N, F , ). Here F is theset of feasible coalitions. F is a nonempty subset of the set of all coalitions, i.e.
∅=
6 F ⊂ {S | ∅ =6 S ⊂ N }. For each i ∈ N , F (i) denotes the set of feasible coalitions
that contain i, i.e. F (i) = {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.”
= (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 . Let x, y ∈ X(F ). Then abusing
notation, let us denotex i y(1)x(i) i y(i)(2)

if and only if

2Takagi and Serizawa (2006) also study the college admission problem. Refer to Concluding remarksof the present paper.
3
Toda (2006) calls this property mutually best.

4Note that we are assuming that preferences are hedonic, that is, preferences depend
only on the composition of the coalition of which the individual is a member.4
As far as we are aware, the present model was introduced 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 special cases the well-known marriage problems (two-sided one-to-one
matching problems) and roommate problems (one-sided one-to-one matching problems)
as in Gale and Shapley (1962).
On the other hand, although our model also includes college admission problems(two-sided many-to-one matching problems), our results are not applicable to those
problems. This is because in those matching problems, usually preferences are assumed
to have some special structures (such as “responsiveness” or “separability”), which are
not compatible with the domain assumptions which we will impose later.

2.2

Coalition formation rules

For i ∈ N , Di denotes the nonempty set of preference relations admissible to individual
i. And D denotes the domain of preferences, i.e. D = D1 × D2 × . . . × Dn . Given(N, F , D), a coalition formation rule f is a nonempty set-valued function f : D →→X(F ).
We say that f respects coalitional unanimity if for any ∈ D and any S ∈ F ,∀i ∈ S, ∀T ∈ F (i), S i T ⇒ ∀x ∈ f (), S ∈ x .

(3)Note that coalitional unanimity may not be well-defined when preferences permit
indifference. This is because in such cases, two coalitions which are both unanimously
ranked at the top by their members may have a nonempty intersection. In this case,the definition of the property becomes contradictory. We will impose an assumption(Assumption 2 in Sec.3.1) on the preference domain to exclude such cases and makethe condition well-defined.

2.3

Strict core stability

The axiom of coalitional unanimity is closely related to the concept of strict corestability. 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) .
A partition x is said to be strictly core stable if no feasible coalition blocks x.
4

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

5(4)

The concept of strict core stability is a refinement of core stability. It is definedby the stronger notion of blocking which is obtained by replacing the formulae (4) inthe above with the following:∀i ∈ S, S i x(i).

(5)

These two core stability concepts are equivalent to each other if preferences are allstrict, 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 .

2.4

Concepts from mechanism design

Consider a social choice problem. The problem consists of (i) the set of individuals
N = {1, · · · , n} with n ≥ 1, (ii) the (nonempty) set of outcomes A, and (iii) for eachi ∈ N , the set of admissible preferences over A, which is denoted by Di . Denote
D = D1 × · · · × Dn .
Given a social choice problem, a social choice rule (a SCR, for short) is anonempty set-valued function from D to A. A game form (or a mechanism) is alist (M, g), where M = M1 × · · · × Mn and Mi is the message space of individual
i, and g : M → A is an outcome function. Given a preference profile ∈ D,(M, g, ) constitutes a strategic game. Let us denote by Nash(M, g, ) the set ofNash equilibria of the game (M, g, ). Let a SCR f be given. We say that a gameform (M, g) implements the SCR f in Nash equilibrium if for each ∈ D,
g(Nash(M, g, )) = f (). In this paper, we consider the implementation of coalition
formation rules as SCRs.
Let a preference relation i and an outcome a be given. Then let MT(i , a) denotethe set{0i ∈ Di | ∀b ∈ A, (a i b) ⇒ (a 0i b)}.

(6)MT(, a) = { 0 ∈ D | ∀i ∈ N, 0i ∈ MT(i , a)}.

(7)

For ∈ D, denoteWe say that a SCR f is Maskin monotonic if for any , 0 ∈ D and any x ∈ f (),
0 ∈ MT(, x) ⇒ x ∈ f (0 ).

(8)

It is well-known that Maskin monotonicity is a necessary condition for Nash implementation (Maskin 1985, 1999).

6

Consider a SCR f . Let us assume f is singleton-valued and regard f as a singlevalued function. Then the rule f is coalition strategy-proof if for any ∈ D, any
˜ S ∈ DS ,S ⊂ N , and any ˜ S ) i f () ⇒ ∀i ∈ S, f (−S , ˜ S ) ∼i f () .
∀i ∈ S, f (−S , (9)There is a strong connection between Maskin monotonicity and coalition strategyproofness: These two properties are equivalent on the domains considered in the present
paper. (See. Sec.3.1.)

3

Results

3.1

Domain assumptions

We define a class of domains by two assumptions. These domains generalize the strict
preference domain, i.e. the domain such that each Di consists exactly of those preferences which satisfy∀i ∈ N, ∀S, T ∈ F (i), S ∼i T ⇒ S = T.

(10)

The strict preference domain is common in the literature of matching and coalition
formation. In the following, we fix the elements (N, F , D). Correspondingly, let us
abbreviate X(F ) to X.
Let Q be a partition of a set Q. Then for any x ∈ Q, let us denote by Q(x) thecell of Q that contains x.
Assumption 1 D is such that for any i ∈ N , there exists a partition Pi of X such
that
n
o
Di = i | ∀x, y ∈ X, x ∈ Pi (y) ⇔ x(i) ∼i y(i) ,(11)
and∀x, y ∈ X, ∃i ∈ N : x 6∈ Pi (y).

(12)

Under Assumption 1, indifferences are permitted; but for each individual i, theindifference class has to be fixed throughout Di .
The same domain condition as Assumption 1 is found in Takamiya (2007), whichcalls a domain satisfying this assumption an essentially strict preference domain.
He has shown that on an essentially strict preference domain, a single-valued rule is
Maskin monotonic if, and only if, it is coalition strategy-proof. This result will beapplied to obtain our Corollary 2 (Sec.3.2).
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.
7Note that the indifference class Pi of X in Assumption 1 uniquely corresponds
to the indifference class P̃i of F (i) in the way that x ∈ Pi (y) if and only if x(i) ∈P̃i (y(i)). Thus in the following, as long as no ambiguity arises, let us equate these twoclasses and denote them by the same “Pi .”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 (i) 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)

That is, no singleton is indifferent to other coalitions.

3.2

Statements of results

All of the following results postulate Assumptions 1 and 2. The following is our main
theorem.
Theorem 1 A coalition formation rule f is Maskin monotonic and respects coalitional
unanimity if, and only if, for any ∈ D, f () = C ().
In the following we apply Theorem 1 to Nash implementability and coalition strategyproofness.
Theorem 2 If |N | ≥ 3 and the strict core stable correspondence C is nonempty-valued,
then C is Nash implementable.
For the case where |N | = 2 and F = {{1}, {2}, {1, 2}}, the strict core stablecorrespondence C is not Nash implementable. This case of the problem is identicalwith the marriage problem (Gale and Shapley, 1962) with one man and one woman.
Kara and Sönmez (1996) proves the impossibility of the Nash implementation for thisparticular case.
Since Maskin monotonicity is necessary for Nash implementation, Theorems 1 and2 together yield the following result.
Corollary 1 Let |N | ≥ 3. A coalition formation rule f is Nash implementable andrespects coalitional unanimity if, and only if, for any ∈ D, f () = C ().
8Note that since f is assumed to be nonempty-valued, Corollary 1 implies the existence problem of Nash implementable rules which respect coalitional unanimity isequivalent to the problem of whether strict core stable partitions exist for all preference profiles in the domain. The existence problem of strict core stable partitions
has been solved for the case of the strict preference domain: Pápai (2004b) gives anecessary and sufficient condition that the set of feasible coalitions is to satisfy forthe existence. However, as far as we know, the problem is open for the larger class of
domains considered in the present work.
Coalition strategy-proofness is a stringent incentive property for single-valued rules.
Under Assumption 1, for single-valued rules, Maskin monotonicity is equivalent tocoalition strategy-proofness by the result of Takamiya (2007). (See Sec.3.1.) This
yields the following result.5
Corollary 2 Let a coalition formation rule f be single-valued. Then f is coalition
strategy-proof and respects coalitional unanimity if, and only if, for any ∈ D, f () = C ().
Note that Corollary 2 says that C must be single-valued. A necessary and sufficientcondition that the set of feasible coalitions is to satisfy for the single-valuedness of C
on the strict preference domain has been obtained by Pápai (2004a). However, to ourknowledge, the problem is also open for the larger class of domains considered in thepresent work.
In our setting, a coalition formation rule f is defined to be a non-empty correspondence. However, since in many cases (such as the roommate problem and the hedonic
coalition formation model) the strict core stable correspondence C takes empty values. Theorem 1 does not provide any characterization of the correspondence C in suchcases. In order to obtain the characterization of C regardless of whether it is nonemptyvalued or not, we drop the nonempty-valuedness assumption of f and impose on f the“restricted nonemptiness” property defined as follows:∀ ∈ D, C () 6= ∅ ⇒ f () 6= ∅.

(15)

Theorem 3 A correspondence f from D to X is Maskin monotonic, respects coalitional unanimity and satisfies restricted nonemptiness if, and only if, for any ∈ D,
f () = C ().
The proof of Theorem 3 is essentially the same as that of Theorem 1 so we will notpresent it separately.
Remarks(1) Theorems 1 and 3 are tight, that is, the three properties, Maskin monotonicity,
coalitional unanimity and restricted nonemptiness are independent to each other:5

This result appears also in Takamiya (2008) with a different derivation.

9(i) The Pareto correspondence is Maskin monotonic and satisfies restricted nonemptiness (actually it is nonempty-valued) but does not respect coalitional unanimity.6(ii) Consider the rule f satisfying the following two conditions: (a) for any ∈ D
and any S ∈ F , if S is top-ranked for all the members of S in , then S ∈ f (); and (b) for any ∈ D and any i ∈ N , if for any S ∈ F (i) there is some j ∈ S(where it can be j = i) for whom S is not top-ranked in j , then {i} ∈ f ().
Then f respects coalitional unanimity and satisfies restricted nonemptiness (f isnonempty-valued) but is not Maskin monotonic.
(iii) Consider the correspondence f which assigns the empty set for all preference
profiles. Then f is Maskin monotonic and respects coalitional unanimity but
does not satisfy restricted nonemptiness.
(2) As noted, the core stability is equivalent to the strict core stability on strict
preference domains. But on some domains which permit indifference, the core stablecorrespondence is Maskin monotonic but does not respect coalitional unanimity.
(3) Toda (2006) proves that in the context of the marriage problem, a special caseof the present model, Maskin monotonicity and coalitional unanimity imply f ⊂ C , apart of our Theorem 1.
(4) Kara and Sönmez (1996) proves the Nash implementability of C with |N | ≥ 3
in the context of the marriage problem. Our Theorem 2 is a straightforward extensionof their result.

4

Proofs

To state our proofs, 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 issuch that it satisfies the following three conditions:(i) x(i) xi {i},(ii) 6 ∃S ∈ F (i), x(i) xi S xi {i},(iii) ∀S, T ∈ F (i) \ {{i}}, (S i T ) ⇔ (S xi T ).
Note that the fact (14), which follows from Assumption 2, makes this construction
feasible.
6

The Pareto correspondence is the rule f such that for any ∈ D,
f () = {x ∈ X | ∀y ∈ X, (∀i ∈ N, y i x) ⇒ (∀i ∈ N, y ∼i x)}.

10

↑(x)

• Further, let us define the preference relation i
two 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 ↑(x)• Finally, let x↑.
i be a shorthand for (i )The following Lemma 1 ensures coalitional unanimity is well-defined under ourassumptions.
Lemma 1 Let ∈ D and S 1 , S 2 ∈ F . Then if for each k = 1, 2,∀i ∈ S k , ∀T ∈ F (i), S k i T ,(16)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 ∈ Pi (S 2 ). This clearly contradicts Assumption 2. 2
Proof of Theorem 1. “If ” part. Omitted.
“Only if ” part. (i) We prove that f is Maskin monotonic and respects coalitional
unanimity ⇒ f () ⊂ C () . Suppose the contrary, that is, there exist some ∈ D
and x ∈ X such that x 6∈ C () and x ∈ f (). Then there exists some S ∈ Fsuch that S blocks x. Let y be any partition such that S ∈ y. Consider the profile
˜ = (−S , ↑(y)˜S ). Then the coalitional unanimity of f implies ∀z ∈ f (), S ∈ z. On˜ ∈ MT(, x), the Maskin monotonicity of f implies x ∈ f ().
˜
the other hand, since 
But obviously S 6∈ x, a contradiction.
(ii) We prove that f is Maskin monotonic and respects coalitional unanimity ⇒f () ⊃ C () . Let f be Maskin monotonic and respect coalitional unanimity. Thenf is individually rational, that is, ∀ ∈ D, ∀x ∈ f (), ∀i ∈ N, x(i) i {i}. This
directly follows from the result (i) in the above.
Let ∈ D and x ∈ C (). In the following, we show x ∈ f (). Let y ∈ X with
y 6= x. And let us classify the coalitions in y into two classes: S 0 = {S ∈ y | ∀i ∈S, y ∼i x} and S + = {S ∈ y | ∃i ∈ S, x i y}. Then by the fact that no coalition
blocks x under  and the latter half of Assumption 1, S 0 ∪ S + = y and S + isnonempty.
Consider the profile x . We show y 6∈ f (x ): Suppose y ∈ f (x ). Let T ∈ S + .
If |T | ≥ 2, then the way that x is defined implies ∃j ∈ T : {j} xj y(j). Since f
is individually rational, y 6∈ f (x ) follows, a contradiction. Thus it must be |T | = 1,
that is, for any j ∈ T ∈ S + we have y(j) = {j}. This implies ∀i ∈ N, x xi y,
11which implies x↑ ∈ MT(x , y). By Maskin monotonicity, y ∈ f (x↑ ). But coalitional
unanimity implies {x} = f (x↑ ), a contradiction. Thus we have y 6∈ f (x ).
Now we have ∀y ∈ X \ {x}, y 6∈ f (x ). Since f is nonempty-valued, {x} = f (x ).7
Note that ∈ MT(x, x ). Maskin monotonicity implies x ∈ f (), the desired conclusion. 2
Proof of Theorem 2. Our proof is done by checking that C satisfies the condition of
essential monotonicity by Yamato (1992). For a ∈ X and i ∈ Di , let L(a, i ) denotethe set {b ∈ X | a i b}. Let Y ⊂ X, y ∈ Y and i ∈ N . And let a rule f be given.
Then call y essential to i in Y with respect to the rule f if
∃ ∈ D : L(y, i ) ⊂ Y & y ∈ f ().

(17)

Denote these essential elements by E(f, i, Y ). f is essentially monotonic if for any
˜ ∈ D, and any x ∈ f (),, ˜ i ) ⇒ x ∈ f ().
˜∀i ∈ N, E(f, i, L(x, i )) ⊂ L(x, (18)
Yamato (1992) shows that given |N | ≥ 3, f is Nash implementable if f is essentiallymonotonic.8
We show that ∀ ∈ D, ∀x ∈ C (), ∀i ∈ N , E(C , i, L(x, i )) = L(x, i ). If
this is true, then the Maskin monotonicity of C implies its essential monotonicity.
Then since C is Maskin monotonic, it is essentially monotonic. Let ∈ D, i ∈ N
and x ∈ C (). And let y ∈ L(x, i ). Then consider a profile 0 such that (i)∀S ∈ F (i) \ Pi (y(i)), S i x(i) ⇒ S 0i y(i) & x(i) i S ⇒ y(i) 0i S , (ii)y(i) 0i x(i), and (iii) ∀j ∈ N \ {i}, ∀S ∈ F (j), y(j) 0j S. Then L(y, 0i ) = L(x, i )and y ∈ C (0 ). Thus y is essential to i in L(x, i ) w.r.t. C . Since y is arbitrarily
taken from L(x, i ), we have E(C , i, L(x, i )) = L(x, i ). 2

5

Concluding remarks

Here we mention some directions of the further research. (1) Our results have been
proved under some domain assumptions, which do not permit special preference structures commonly assumed in many-to-one matching problems. Takagi and Serizawa(2006) studies single-valued rules in the context of many-to-one matching problems,and shows an impossibility theorem similar to the one in the marriage problem mentioned in Sec.1. They assume responsive preferences, and they note that the definition
7

Actually the restricted nonemptiness of f suffices to obtain {x} = f (x ). Because it is truethat x ∈ C () and x ∈ MT(x, ), and these imply C (x ) contains x thus it is nonempty since C
is Maskin monotonic. Therefore, f (x ) is nonempty by restricted nonemptiness. This is the only
modification we have to make to prove Theorem 3.
8
Yamato (1992) also shows the converse of this result under an additional domain assumption.

12

of coalitional unanimity has to be modified to accommodate this domain. It is a themeof the future research to device some domain assumptions to include such domains,
and to generalize or modify the definition of coalitional unanimity so that we are able
to perform analysis similar to the one done in this paper.9(2) We have proved that the existence problem of the Nash implementable rules
which respect coalitional unanimity is paraphrased by the problem of the nonemptyvaluedness of the strict core stable correspondence. As mentioned in Sec.3.2, thenonempty-valuedness problem is solved for the strict preference domain (Pápai, 2004b)
but not for the larger class of domains considered in this paper. We consider thisproblem worth investigation.
(3) Although it has been proved that the strict core stable correspondence is Nash
implementable, no concrete mechanisms have been shown. Our proof of implementability uses the condition developed by Yamato (1992). His proof is based on the construction of an all-purpose mechanism but this mechanism is too complex to be applicable toany practical purposes. It is a problem worth investigation to search for some “simple”
mechanisms tailor-made for the present setting. We note that by the result of Tatamitani (2002), no self-relevant mechanisms can accomplish this task. Here a mechanism
is self-relevant if each individual’s message space consists only of this individual’s own
preferences and outcomes.
Acknowledgments I am grateful to Yuji Fujinaka, Ryuichiro Ishikawa, Yoshio Kamijo,
Takashi Kunimoto, Ryo Nakajima, Toyotaka Sakai, Ryusuke Shinohara, Tomoichi
Shinotsuka, Koichi Suga, Shohei Takagi, Takuma Wakayama, Noaki Watanabe forvarious comments, discussion and conversation. I also thank the participants of the
21COE-GLOPE Workshop on Social Choice and Game Theory at Waseda University
in March 2008 and the seminars at Tsukuba University and Shinshu University. Allerrors are my own responsibility.

References[1] Banerjee S, Konishi H, and Sönmez T (2001) Core in a simple coalition formation
game, Soc Choice Welfare 18: 135–53.
[2] Benoit J-P and Ok EA (2008) Nash implementation without no-veto power, Games
Econ Behavior 64: 51–67.
[3] Bochet O (2007) Nash implementation with lottery mechanisms, Soc Choice Welfare 28: 111–125.
[4] Bochet O and Klaus B (2008) The relation between monotonicity and strategyproofness, Working paper. Maastricht University.
9

I thank Shohei Takagi for his comments regarding these points.

13

[5] Bochet O and Sakai T (2005) Nash implementation in stochastic social choice,
Working paper. Maastricht University and Yokohama National University.
[6] Bogomolnaia A and Jackson MO (2002) The stability of hedonic coalition structures, Games Econ Behavior 38: 201–30.
[7] Cechlárová K and Romero-Medina A (2001) Stability in coalition formation games,
Int J Game Theory 29: 487–94.
[8] Chung KS and Ely J (2003) Implementation with near-complete information,
Econometrica 71: 857-871.
[9] Gale D and Shapley L (1962) College admissions and the stability of marriage,
Amer Math Monthly 69: 9–15.
[10] Dréze J and Greenberg J (1980) Hedonic coalitions: optimality and stability,
Econometrica 48: 987–1003.
[11] Kara T and Sönmez T (1996) Nash implementation of matching rules, J Econ
Theory 68: 425–39.
[12] Kunimoto T (2007) How robust is undominated Nash implementation? Working
paper. McGill University.
[13] Maskin E (1985) The theory of implementation in Nash equilibrium: A survey,
Hurwicz L, Schmeidler D and Sonnenschein H (eds) Social Goals and Social Organization. Cambridge University Press, Cambridge, pp 173–204[14] Maskin E (1999) Nash equilibrium and welfare optimality, Rev Econ Stud 66:
pp23–38.
[15] Pápai S (2004a) Unique stability in simple coalition formation games, Games Econ
Behavior 48: 337–54.
[16] Pápai S (2004b) The existence of stable hedonic coalitions, Working paper. University of Notre Dame.
[17] Roth AE and Sotomayor M (1990) Two-Sided Matching: A Study in Game Theoretic Modeling and Analysis, Econometric Society Monograph, vol. 18, Cambridge
Univ Press.
[18] Shapley L and Scarf H (1974) On cores and indivisibilities, J Math Econ 1: pp23–
27.
[19] Sönmez T (1999) Strategy-proofness and essentially single-valued cores, Econometrica 67: 677–89.

14[20] Takagi S and Serizawa S (2006) An impossibility theorem in matching problems,
ISER Discussion Paper Series, No.667.
[21] Takamiya K (2007) Domains of social choice functions on which Maskin monotonicity and coalition strategy-proofness are equivalent, Econ Letters 95: 348–54.
[22] Takamiya K (2008) Coalitional unanimity versus strategy-proofness in coalition
formation problems, Working paper. Niigata University.
[23] Tatamitani Y (2002) Implementation by self-relevant mechanisms: applications,
Math Soc Sciences 44: 253–76.
[24] Toda M (2006) Monotonicity and consistency in matching markets, Int J Game
Theory 34: 13–31.
[25] Yamato (1992) On Nash implementation of social choice correspondences, Games
Econ Behavior 4: 484-92.

15