Soc Choice Welfare (2003) 20: 77–83

On strategy-proofness and essentially single-valued
cores: A converse result
Koji Takamiya
Graduate School of Economics and Business Administration, Hokkaido University,
Kita9 Nishi7 Sapporo 060-0809 Japan (e-mail: kt073@pop.sys.hokudai.ac.jp)
Received: 22 February 2000/Accepted: 22 January 2002

Abstract. In a general model of indivisible good allocation, Sönmez (1999)
established that, whenever the core is nonempty for each preference proﬁle, if
an allocation rule is strategy-proof, individually rational and Pareto optimal,
then the rule is a selection from the core correspondence, and the core correspondence must be essentially single-valued. This paper studies the converse
claim of this result. I demonstrate that whenever the preference domain satisﬁesa certain condition of ‘richness’, if the core correspondence is essentially singlevalued, then any selection from the core correspondence is strategy-proof (evenweakly coalition strategy-proof, in fact). In particular, on the domain of preferences in which each individual has strict preferences over his own assignments
and there is no consumption externality, such an allocation rule is coalition
strategy-proof. And on this domain, coalition strategy-proofness is equivalent
to Maskin monotonicity, an important property in implementation theory.

1 Introduction
In a large class of allocation problems with indivisibilities, the concepts ofthe core and strategy-proofness of allocation rules are closely related. In hisI am grateful to Ryo-ichi Nagahisa, Shinji Ohseto, Hiroshi Ono, Tomoichi Shinotsuka
and Shigehiro Serizawa for valuable comments. And I am indebted to two anonymousreferees for useful suggestions. Especially, I owe the present proof of Lemma 2 to one
referee. I also thank Yukihiko Funaki, Atsushi Kajii, Mamoru Kaneko, Eiichi Miyagawa, Tatsuyoshi Saijo, Manimay Sengupta, Yves Sprumont, Yoshikatsu Tatamitani,Manabu Toda, Takashi Ui, Takehiko Yamato, Naoki Yoshihara and the participantsof the seminars in Hokkaido University, Kansai University, ISER (Osaka University),Otaru University of Commerce and Tsukuba University. All errors are my own
responsiblity.

78K. Takamiya

recent paper, Sönmez (1999) established that in a general model of indivisible
good allocation, whenever the core is nonempty for each preference proﬁle,
if an allocation rule is strategy-proof, individually rational and Pareto optimal, then the rule is a selection from the core correspondence, and the core
correspondence must be essentially single-valued. (The preference domain isassumed to satisfy some minor conditions.) Here essential single-valuedness
means that the correspondence is nonempty-valued and Pareto indi¤erent(i.e., any two elements of an image of the correspondence are indi¤erent to
all the individuals). Given this sharp conclusion, it is naturally questioned
if the converse of this result holds true: Suppose that the core correspondence
is essentially single-valued. Then is every selection from the core correspondence strategy-proof ? (Individual rationality and Pareto optimality are satisﬁed automatically.) The objective of this paper is to study this question.
In fact, Sönmez (1999) himself gave a conditional converse of his conclusion: If the core correspondence is essentially single-valued, and the core isexternally stable for each preference proﬁle, then any selection from the core
correspondence is weakly coalition strategy-proof. Here the external stabilityof the core means that any (feasible) allocation outside the core is dominatedby some allocation in the core. Although the conclusion of weak coalition
strategy-proofness is stronger than strategy-proofness, this result needs the‘additional’ assumption of external stability. This fact motivates to look for amore direct converse claim. However, a simple counterexample shows that theunconditional converse claim does not hold true. That is, with an appropriate
choice of the initial endowments and the set of feasible allocations, there is adomain of preferences on which a selection from the essentially single-valued
core correspondence is not strategy-proof. Thus to obtain a direct-type converse of Sönmez’s result, it is necessary to impose some conditions on the preference domain.
In this paper, I demonstrate that whenever the preference domain satisﬁes
a certain condition of ‘richness’, if the core correspondence is essentially singlevalued, then any selection from the core correspondence is strategy-proof.
In fact, such an allocation rule is even weakly coalition strategy-proof. Intuitively, the ‘richness’ condition requires that for any pair of admissible preferences of any individual, a ‘mixture’ of these preferences be also admissible.
In the ‘mixture’ preference, two allocations (to be speciﬁed in advance) keep
or improve their relative rankings compared with one of the two ‘original’
preferences.
In particular, on the domain of preferences in which each individual has strict
preferences over his own assignments and there is no consumption externality,
the unique selection from the single-valued core correspondence is coalition
strategy-proof. (Essential single-valuedness is nothing but single-valuedness inthis case.) I prove this result by showing that on this particular domain, coalition strategy-proofness is equivalent to well-known ‘Maskin monotonicity’,
which plays important roles in implementation theory. This is a generalizationof a similar equivalence theorem by Takamiya (2001), proved in the context ofhousing markets (Shapley and Scarf 1974), a special case of the present model.

Strategy-proof core-selection

79

2 Deﬁnitions
The following model is due to Sönmez (1999). This class of allocation
problems is a comprehensive economic model with indivisibilities. It includes
some well-known classes of problems as subclasses, such as marriage problems (Gale and Shapley 1962) and housing markets (Shapley and Scarf 1974),and other models.1 A generalized indivisible good allocation problem is a list
ðN; o; A f ; RÞ. Here N is the (nonempty) ﬁnite set of individuals. A coalition is a nonempty subset of N. For i A N, oðiÞ denotes the initial endowment of individual i. Assume that oðiÞ is a ﬁnite set. For S H N, denote byoðSÞ the set 6foðiÞ j i A Sg.2 A f is the set of feasible allocations. A f is anonempty subset of the set of all allocations fx : N !! oðNÞ j Ea A oðNÞ:afi A N j a A xðiÞg ¼ 1g. Assume o A A f . R ¼ ðR i Þi A N is a preference proﬁle.
Here for each i A N, R i is assumed to be a weak order3 on A f . xR i y reads
that to individual i, x is at least as good as y. As usual, I i and P i respectively
denote the symmetric (‘indi¤erent’) and asymmetric (‘strictly prefers’) parts of
R i . For each individual i, D i denotes the (nonempty) set of admissible
preferQ
ences of i. For a coalition S, D S denotes the Cartesian product i A S D i . Then
D N represents the domain of preferences.
Let R i be a preference relation and x A A f . Then Lðx; R i Þ denotes
the lower contour set of x relative to R i , i.e., Lðx; R i Þ :¼ f y A A f j xR i yg.
And L  ðx; R i Þ denotes the strict lower contour set of x relative to R i , i.e.,L  ðx; R i Þ :¼ fy A A f j xP i yg.
Let a list ðN; o; A f Þ be given. Fix a preference proﬁle R. Let x; y A A fand S be a coalition. Say that x dominates y via S under R if ½xðSÞ H oðSÞ &½Ei A S: xR i y & ½bj A S: xP j y . The core is the set of all allocations which are
not dominated by any other allocation. The core correspondence on D N is
the set-valued function C : D N !! A f such that for each R A D N , CðRÞ isthe core of the problem ðN; o; A f ; RÞ. Call C essentially single-valued if Cis nonempty-valued, and Pareto indi¤erent, i.e. ER A D N : Ex; y A CðRÞ:Ei A N: xI i y. An allocation x is Pareto optimal under R if no other allocation
dominates x via N under R.
An allocation rule is a function j : D N ! A f . Let i A N, and R A D N .
Then say that individual i manipulates the outcome at preference proﬁle R if
bR 0i A D i : jðR i ; R 0i ÞP i jðRÞ:ð1Þ

Call j strategy-proof if no individual manipulates the outcome at any preference proﬁle. Let S be a coalition. Then say that S manipulates the outcome atpreference proﬁle R if
bR 0S A D S : ½Ei A S: jðR S ; R 0S ÞP i jðRÞ :ð2Þ

1 Indeed, in Sönmez (1999), it is discussed that six preceding models are included assubclasses.
2 Throughout the paper, inclusion ‘H’ is weak.
3 A weak order is a complete (thus reﬂexive) and transitive binary relation.

80

K. Takamiya

Call j weakly coalition strategy-proof if no coalition manipulates the outcome
at any preference proﬁle. This is stronger a form of nonmanipulability thanstrategy-proofness. Further, if the concept of coalitional manipulation (2) is
weakened tobR 0S A D S : ½Ei A S: jðR S ; R 0S ÞR i jðRÞ & ½bj A S: jðR S ; R 0S ÞP j jðRÞ ;ð3Þthen the corresponding nonmanipulability concept becomes even stronger one
called coalition strategy-proofness.
Say j is Pareto optimal if for any R A D N , the allocation jðRÞ is Pareto
optimal under R.

3 Main results
Let a list ðN; o; A f Þ be given. I impose the following condition on the domainof preferences D N .
Condition A. Let i A N, R i A D i , and x; y A A f be such that yP i x. Then for all
R 0i A D i , there exists some R i A D i such that(i) L  ðx; R i Þ H L  ðx; R i Þ, and Lðx; R i Þ H Lðx; R i Þ; and(ii) L  ðy; R 0i Þ H L  ð y; R i Þ and Lðy; R 0i Þ H Lðy; R i Þ.
Note that in the above, for any combination of fðR i ; R 0i Þ; ðx; yÞg, such R ialways exists (though not necessarily unique). Thus this condition basicallyrequires that the preference domain be su‰ciently ‘large’.
Note that given R i , it is essential to choose x and y so as to satisfy yP i x.
Because otherwise such R i might not exist. As an intuitive meaning of Condition A, (i) says that x keeps or improves its relative ranking from R i to R i ,and (ii) says that so does y from R 0i to R i . So to speak, R i is a ‘mixture’ of
R i and R 0i from the viewpoint of desirability of x and y. For example, foreach i A N, let Rsi denote the set of all preference relations in which individuali has strict preferences over his own assignments (i.e. xI i y ) xðiÞ ¼ yðiÞ) andthere is no consumption(i.e. xðiÞ ¼ yðiÞ ) xI i y). Denote by Rs
Q externality
ithe Cartesian product i A N Rs . Then the domain Rs satisﬁes Condition A. I
will concentrate on this domain in Sect. 4 below.
The following is the main theorem.
Theorem 1. Assume that the domain D N satisﬁes Condition A. Then if thecore correspondence C is essentially single-valued, then any selection from C isweakly coalition strategy-proof.
Theorem 1 is an immediate consequence of the two lemmas below.
Lemma 2. Assume that the core correspondence C is essentially single-valued.
Let j be a selection from C. Then j satisﬁes the property (B) in the following.

Strategy-proof core-selection

81ER; R  A D N :½x ¼ jðRÞ & ðEi A N: L  ðx; R i Þ H L  ðx; R i Þ & Lðx; R i Þ H Lðx; R i ÞÞ) ½Ei A N: jðR  ÞI i x :ðBÞProof. Let R A D N and x ¼ jðRÞ. And let R  A D N satisfy
Ei A N: Lðx; R i Þ H Lðx; R i Þ & L  ðx; R i Þ H L  ðx; R i Þ:

ð4Þ

Since j is a core-selection, x A CðRÞ. This and (4) imply x A CðR  Þ. Then since
C is essentially single-valued, it follows Ei A N: jðR  ÞI i x.
8Lemma 3. Let j be an allocation rule. Assume that the domain D N satisﬁes
Condition A. Then j is weakly coalition strategy-proof if j is Pareto optimal,and satisﬁes the property (B).
Proof. Let j be Pareto optimal and satisfy the property (B). Suppose that jis not weakly coalition strategy-proof. Then there is some coalition S which
manipulates the outcome (in the sense of the formula (2) in Sect. 2) at a proﬁleR by reporting R 0S . Denote x ¼ jðRÞ and y ¼ jðR S ; R 0S Þ. Then for any i A S,yP i x. For each i A S, choose a preference relation R i such thatL  ðx; R i Þ H L  ðx; R i Þ;
0i

iL ð y; R Þ H L ðy; R ÞandandLðx; R i Þ H Lðx; R i Þ;
0iiLðy; R Þ H Lðy; R Þ:andð5Þð6ÞCondition A assures that D i includes such R i . By the property(B), the construction (5) of R S implies Ei A S: jðR S ; R S ÞI i x andEi A N S: jðR S ; R S ÞI i x. Similarly, by the construction (6), I have Ei A S:
jðR S ; R S ÞI i y and Ei A N S: jðR S ; R S ÞI i y. Then it follows Ei A S: xI i yand Ei A N S: xI i y. Now recall that for any i A S, yP i x. Thus under R, ydominates x via N. But x ¼ jðRÞ. This contradicts the Pareto optimalityof j. 84 Further results
Now I restrict my attention to the preference domain Rs deﬁned above.
This domain is remarked in Sönmez (1999) as an important example of thedomains compatible with the conditions he imposed on the admissible preferences (which are di¤erent from Condition A). By choosing this speciﬁcdomain, some sharper conclusions become additionally available. First of all,
I point out that the property (B) is the same as the following property (C) on
the domain Rs .
ER; R  A D N : ½x ¼ jðRÞ & ðEi A N: Lðx; R i Þ H Lðx; R i ÞÞ ) jðR  Þ ¼ x:
ðCÞThe property (C) is well known as Maskin monotonicity, which plays very
important roles in implementation theory (see e.g., Maskin 1985). Note that

82

K. Takamiya

in general, this property is stronger than the property (B). On the domain Rs ,this property is the same as coalition strategy-proofness.4
Theorem 4. Assume that the domain D N equals Rs . Let j be an allocation rule.
Then j is coalition strategy-proof if and only if j satisﬁes the property (C).
Proof. (If ): Assume j satisﬁes the property (C). Suppose that j is manipulated by some coalition S (in the sense of the formula (3)) at a proﬁle R byreporting R 0S . Denote x ¼ jðRÞ and y ¼ jðR S ; R 0S Þ. Then for each i A S,
choose a preference R i in Rsi for which(i) no allocation is strictly preferred to y; and(ii) if an allocation z is strictly preferred to x, then yðiÞ ¼ zðiÞ.
Note that Ei A S: Lðx; R i Þ H Lðx; R i Þ and Lð y; R 0i Þ H Lðy; R i Þ.
Then by the property (C), I have jðR S ; R S Þ ¼ x and jðR S ; R S Þ ¼ y at
the same time. Then I get x ¼ y, a contradiction.
(Only If ): Assume that j does not satisfy the property (C). Then I havebR A D N : bi A N: bR i A D i :½x ¼ jðRÞ & Lðx; R i Þ H Lðx; R i Þ & ½bj A N: jðR i ; R i Þð jÞ 0 xð jÞ :Note that since D N ¼ Rs , jðR i ; R i Þð jÞ 0 xð jÞ implies that the twoallocations jðR i ; R i Þ and x are never indi¤erent to j at any proﬁle. Suppose that j is coalition strategy-proof. Now if j ¼ i, then j would be manipulated by i. Because, when jðR i ; R i ÞP i jðRÞ ð¼ xÞ, i manipulates at R sincejðR i ; R i ÞP i jðRÞ by the property (C); when jðRÞP i jðR i ; R i Þ, i manipulates at ðR i ; R i Þ. Thus I have jðR i ; R i ÞðiÞ ¼ jðRÞðiÞ. After all, there must
be j 0 i such that jðRÞð jÞ 0 jðR i ; R i Þð jÞ. But if jðR i ; R i ÞP j jðRÞ holds,then (since jðR i ; R i ÞI i jðRÞ) fi; jg manipulates at ðR fi; jg ; R j ; R i Þ. Similarly,jðRÞP j jðR i ; R i Þ also implies a manipulation by fi; jg. This is a contradiction. 8Takamiya (2001) proved the same equivalence in the context of housingmarkets (Shapley and Scarf 1974), a special case of the present model. Theorem 4 generalizes this result. Also Theorem 4 is reminiscent of the famous
theorem by Muller and Satterthwaite (1977), which states the equivalence ofstrategy-proofness and Maskin monotonicity for any social choice function
deﬁned on the linear (i.e., no indi¤erences allowed) unrestricted domain ofpreferences. Readers might ﬁnd an independent interest in Theorem 4.
From Theorem 4 (together with Lemma 2), I conclude the following.
Note that on the domain Rs , essentially single-valuedness is nothing but singlevaluedness.
Corollary 5. Assume that the domain D N equals Rs . Then if the core correspondence C is single-valued, then the unique selection from C is coalition
strategy-proof.
4 The following two results have already been reported in Takamiya (1999) in a different context.

Strategy-proof core-selection

83

5 Example
Finally, to see Condition A is not superﬂuous to my results, I present
an example in which the selection from the essentially single-valued (singlevalued, in fact) core correspondence is not strategy-proof. Needless to say,
Condition A is violated.
Example 6. Assume N ¼ f1; 2; 3g:
oð2Þ ¼ fcg;

oð3Þ ¼ fdg: A f ¼ fx; y; z; og;xð1Þ ¼ fc; dg;

xð2Þ ¼ fag;xð3Þ ¼ fbg;

yð1Þ ¼ fc; dg;

yð2Þ ¼ fbg;

yð3Þ ¼ fag;zð1Þ ¼ fcg;

zð2Þ ¼ fa; bg;

zð3Þ ¼ fdg:

oð1Þ ¼ fa; bg;
where

D 1 ¼ fR 1 ; R 1 g;

andwhere; R 1 : ðz P 1 y P 1 x P 1 oÞ;R 1 : ð y P 1 z P 1 o P 1 xÞ;D 2 ¼ fR 2 g;

where R 2 : ðx P 2 z P 2 y P 2 oÞ;

D 3 ¼ fR 3 g;

where R 3 : ðx P 3 y P 3 o P 3 zÞ:andThen CðR 1 ; R 2 ; R 3 Þ ¼ fxg, and CðR 1 ; R 2 ; R 3 Þ ¼ fyg.
Denote by j the unique selection from C. Then it is clear thatjðR 1 ; R 2 ; R 3 Þ ¼ yP 1 x ¼ jðR 1 ; R 2 ; R 3 Þ. Thus j is not strategy-proof.

References
Gale D, Shapley L (1962) College admissions and the stability of marriage. Am Math
Monthly 69: 9–15
Ma J (1994) Strategy-proofness and the strict core in a market with indivisibilities. Int J
Game Theory 23: 75–83
Maskin E (1985) The theory of implementation in Nash equilibrium: A survey. In:Hurwicz L, Schmeidler D, Sonnenschein H (eds) Social goals and social organization. Cambridge University Press, Cambridge, pp 173–204
Muller E, Satterthwaite M (1977) The equivalence of strong positive association andstrategy-proofness. J Econ Theory 14: 412–418
Shapley L, Scarf H (1974) On cores and indivisibility. J Math Econ 1: 23–37
Sönmez T (1999) Strategy-proofness and essentially single-valued cores. Econometrica
67: 677–689
Takamiya K (2001) Coalition strategy-proofness and monotonicity in Shapley-Scarf
housing markets. Math Soc Sciences 41: 201–213
Takamiya K (1999) Coalition strategy-proofness and monotonicity: A generalizationof the Muller-Satterthwaite Theorem with an application to indivisible good allocation problems. Mimeo, Hokkaido University