Discussion Paper No. 651

PREFERENCE REVELATION GAMESAND STRONG CORESOF ALLOCATION PROBLEMSWITH INDIVISIBILITIESKoji Takamiya

March 2006

The Institute of Social and Economic Research
Osaka University
6-1 Mihogaoka, Ibaraki, Osaka 567-0047, Japan

Preference revelation games and strong cores ofallocation problems with indivisibilities∗
Koji TAKAMIYA†
Institute of Social and Economic Research,
Osaka University
This version, Oct 11 2005

Abstract
This paper studies the incentive compatibility of solutions to generalized indivisible good allocation problems introduced by Sönmez(1999), which contain the well-known marriage problems (Gale and Shapley, 1962) and the housing markets (Shapley and Scarf, 1974) as special
cases. In particular, I consider the vulnerability to manipulation of solutions
that are individually rational and Pareto optimal. By the results of Sönmez(1999) and Takamiya (2003), any individually rational and Pareto optimal
solution is strategy-proof if and only if the strong core correspondence isessentially single-valued, and the solution is a strong core selection. Given
this fact, this paper examines the equilibrium outcomes of the preference
revelation games when the strong core correspondence is not necessarily
essentially single-valued. I show that for the preference revelation games
induced by any solution which is individually rational and Pareto optimal,
the set of strict strong Nash equilibrium outcomes coincides with the strong
core. This generalizes one of the results by Shin and Suh (1996) obtained in
the context of the marriage probelms. Further, I examine the other preceding results proved for the marriage problems (Alcalde, 1996; Shin and Suh,
1996; Sönmez, 1997) to find that none of those results are generalized to thegeneral model.
JEL Classification— C71, C72, C78, D71, D78.
Keywords— generalized indivisible good allocation problem, preference
revelation game, strict strong Nash equilibrium, strong core.

∗ This paper is based on Chapter 4 of my dissertation submitted to Hokkaido University. I
am grateful to Tayfun Sönmez for introducing some of his works related to this paper. Also I
am indebted to Takuma Wakayama, Eiichi Miyagawa, Ken-ichi Shimomura, Ryo-ichi Nagahisa,
Takashi Shimizu for comments, and in particular to Tomoichi Shinotsuka for detailed comments
and discussion. And I thank seminar participants at Otaru University of Commerce, RIEB (Kobe
University) and Kansai University. All errors are my own responsibility.
† Institute of Social and Economic Research, Osaka University. 6-1 Mihogaoka Ibaraki Osaka
567-0047 JAPAN. tel: +81-6-6879-8556. E-mail: takamiya@iser.osaka-u.ac.jp.

0Introduction

0.1

Motivation and method

This paper studies the vulnerability to manipulation of solutions to generalized
indivisible good allocation problems introduced by Sönmez (1999). Specifically, I am interested in the manipulability of solutions which are individually
rational and Pareto optimal. Generalized indivisible good allocation problems
are a comprehensive economic model with indivisibilities. This class of allocation problems includes some well-known classes of problems as subclasses, such as
the marriage problems (Gale and Shapley, 1962) and the housing markets(Shapley and Scarf, 1974).
When one examines the incentive compatibilty of solutions, it first comes to
ask if they are strategy-proof or not.1 Sönmez (1999) and Takamiya (2003)
characterized strategy-proof solutions in this environment: Sönmez showed thatwhenever the strong core is nonempty for any admissible preference profile, if
a solution is strategy-proof, individually rational and Pareto optimal, then thestrong core correspondence must be essentially single-valued, and the solution
is a selection from the strong core correspondence. (Here that the strong core
correspondence is essentially single-valued means that for any preference profile
any two strong core allocations are indifferent to all individuals.) Conversely,
Takamiya showed that if the strong core correspondence is essentially single-valued,
then any selection from the correspondence is strategy-proof (weakly coalition
strategy-proof, in fact). These results shows that the possibility for reasonablestrategy-proof solutions are very limited.
Given the above fact, this paper studies the incentive compatibility of solutions
that are individually rational and Pareto optimal when the strong core correspondence is not necessarily essentially single-valued. In this case, such solutions neednot be strategy-proof. This means that individuals are open to strategic behavior
by misrepresenting their preferences. Thus it is expected that the resulting outcomes would be different from the ones arising from the true preferences. Now therelevant question of incentive compatibility is “where does the strategic behavior
leads to?”Given strategic behavior of individuals, the solution is regarded as a game inwhich each individual reports a preference relation as a strategy, and evaluates
the outcome chosen by the solution fed with the reported preference profile. This
game is called preference revelation game. (Thus, given a solution, one true
preference profile defines one preference revelation game.) To study the above
question, we analyze the equilibrium outcomes of the preference revelation games
induced by the solution.2 Here the choice of equilibrium concept represents theway the individuals are assumed to behave.
To be more specific, in this paper two questions are asked. (1) We have alreadyknown that any selections from the strong core correspondence is strategy-proof
if and only if the correspondence is essentially single-valued. Then if it is not so,
1 Strategy-proofness is one of the most stringent criteria of nonmanipulability. An solution iscalled strategy-proof if no individual can be better off by misrepresenting his preference.
2 This type of analysis was initiated by, among others, Hurwicz (1978), Otani and Sicilian(1982) and Thomson (1984, 1988) mainly for the Walrasian exchange economies.

1how much are these selections manipulable? Namely, in what equilibrium concept
are the strong core outcomes played in the preference revelation games induced
by strong core selections? (2) The analysis of preference revelation games has
already been carried out by several authors for the marriage problems (Galeand Shapley, 1964), a special case of the present model. Then what part of thisprevious analysis can be extended to the present general model? Answers to theboth questions (needless to say about the second question, but also about thefirst question) are to be found in generalizing the previous analysis to the present
generalized model. I will review those previous results in Section 0.2.
The analysis in the sequel, I employ the concepts of G-proof Nash equilibirum and strict G-proof Nash equilibirum.3 Here G-proof Nash equilibrium
is a similar concept to strong Nash equilibrium except that the ”deviation power”
is limited to the coalitions belonging to the prescribed class of coalitions G. Thus
depending on how G is set beforehand, it reduces to Nash equilibrium or strong
Nash equilibrium. And strict G-proof Nash equilibrium is a similar concept exceptthat group deviations with weak improvement are also ruled out. It also reduces
to Nash equilibrium or strict strong Nash equilibrium.
To describe the outcomes corresponding to these equilibrium concepts, I deal
with the concepts of G-weak core and the G-strong core. Just like (strict)
G-proof Nash equilibrium, these core concepts are defined in the way that only
the coalitions in G have the blocking power. The G-weak core is defined by theblockings with strict improvement. This reduces to the weak core if G equals tothe set of all coalitions. Also the G-strong core is defined by the blockings withweak improvement. This reduces to the strong core similarly.

0.2

Previous and present results

The following looks back the analysis done in the context of the marriage problems (Gale and Shapley, 1964), a special case of the present model. Several
authors have obtained ”implementability” (i.e. ”full conincidence”) results.
Ma (1995) introduced the notion of rematching-proof equilibrium. A
rematching-proof equilibrium is a Nash equilibrium in which no pair of ”man”
and ”woman” can jointly deviate so that each of them be better off. He showed
the following: Consider the preference revelation games induced by any stable
solution (i.e. a selection from the stable matching correspondence).4 Then ineach game, the set of rematching-proof equilibrium outcomes coincides with thethe set of stable matchings.
Shin and Suh (1996) pointed out that Ma’s above result would still hold true
if one uses the notions of strong Nash equilibrium or strict strong Nashequilibrium instead of rematching-proof equilibrium.
On the other hand, Alcalde (1996) studied Nash equilibrium. He showedthat in the preference revelation games induced by any stable solution, the set ofNash equilibirum outcomes equals to the set of individually rational matchings.
3 The concept of G-proof Nash equilibrium was introduced in Kalai, Postlewaite and Roberts(1979).
4 For the case of the marriage problems, both the strong core and the weak core always coincidewith the set of stable matchings. For a proof, refer to Roth and Sotomayor (1990).

2

Finally, Sönmez (1997) adopted the concept of G-proof Nash equilibrium.
Sönmez proved the following: Let a solution be individually rational and Pareto
optimal. (This is weaker than requiring the solution to be a stable solution.) Thenthe set of G-proof Nash equilibrium coincides with the G-weak core in eachof the induced preference revelation games. The above-mentioned results concerning Nash equilibrium by Alcalde, rematching-proof equilibrium by Ma, and strong
Nash equilibrium by Shin and Suh are all corollaries to Sönmez’s result. However,note that the result concerning strict strong Nash equilibrium by Shin and Suhdoes not follow from Sönmez’s result.
Given these existing results for the marriage problems, turning to the generalized model, this paper proves the following: For the preference revelation games
induced by any solution which is individually rational and Pareto optimal, theset of strict G-proof Nash equilibrium outcomes coincides with the G-strong
core for any ”monotonic” class of coalitions G. Here G is said to be monotonic
if a coalition S belongs to G, then any supercoalition of S also belongs to G. By
setting G equal to the set of all coalitions, this result implies the coincidence between the set of strict strong Nash equilibrium outcomes and the strong
core. This generalizes one of the two results by Shin and Suh (1996) in the marriage problems (since the strong core equals to the set of stable matchings in themarriage problems). On the other hand, by means of counter-examples, I showthat neither the outcomes of Nash equilibrium nor strong Nash equilibrium are noteven included in the strong core outcomes. These results anwser the first question
I asked in Section 0.1.
In the above result, the monotonicity assumption of G is essential. In particular
for the marriage problems, on the analogy of Sönmez’s results, one may suspectthat the above result still holds true without the monotonicity of G. But there isa counter-example.
Next, to answer the second question I asked in Section 0.1, I examine what partof the rest of the previous results stated above are to be extended to the generalmodel. I find that none of the other results are to be extended to the generalmodel. Interestingly, although one does not obtain ”full coincidence” any more,
one direction of inclusion still preserves in general: For any class of coalitions G,
the set of G-proof Nash equilibrium outcomes is included in the G-weak core.
This paper is organized as follows: Section 1 introduces the basic concepts.
Section 2 presents the main theorems which answer the first question of this paper.
And Section 3 examines the generalizations of the preceding results. This answers
the second question.

1

Definitions

1.1

Model

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-knownclasses of problems, such as the marriage problems (Gale and Shapley, 1962) and3

the housing markets (Shapley and Scarf, 1974), and other models as subclasses.5
A generalized indivisible good allocation problem is a list (N, ω, Af , R).
Here N is the (nonempty) finite set of individuals. A coalition is a nonempty
subset of N . For i ∈ N , ω(i) denotes the initial endowment S
of individual i.
Assume that ω(i) is a finite set. For S ⊂ N , denote by ω(S) the set {ω(i)|i ∈ S}.6
Af is the set of feasible allocations. Af is a nonempty subset of the set of all
allocations A0 := {x : N →→ ω(N ) | ∀a ∈ ω(N ) : #{i ∈ N |a ∈ x(i)} = 1}.
Assume ω ∈ Af . R = (Ri )i∈N is a preference profile. Here for each i ∈ N , Ri
is assumed to be a weak order on Af .7
xRi 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 (’indifferent’) and asymmetric (’strictlyprefers’) parts of Ri . For each individual i, Di denotes the (nonempty) set ofadmissible preferences of i. For a coalition S, DS denotes the Cartesian productQiN
represents the domain of preferences. One importanti∈S D . Then D
example of preference domains is the domain P defined as follows: For each i ∈ N ,let P i denote the set of all preference relations in which individual i has strict
preferences over his own assignments (i.e. xI i y ⇒ x(i) = y(i)) and there is no
consumption(i.e. x(i) = y(i) ⇒ xI i y). Denote by P the Cartesian
Q externalityiproduct i∈N P . In this paper, whenever I refer to the marriage problems or
the housing markets, the domain P is assumed.
Let a list (N, ω, Af ) be given. Let G be a (nonempty) class of coalitions. Fix
a preference profile R. Let x, y ∈ Af and S be a coalition. Say that x weakly
dominates y via S under R if
x(S) = ω(S)&[∀i ∈ S : xRi y]&[∃j ∈ S : xP j y].
The G-strong core is the set of allocations which are not weakly dominatedby any other allocation via any coalition belonging to G. The G-strong core
correspondence on DN is the correspondence C G : DN →→ Af such that foreach R ∈ DN , C G (R) is the G-strong core of the problem (N, ω, Af , R). Say thatx strongly dominates y via S under R if
x(S) = ω(S)&[∀i ∈ S : xP i y].
The G-weak core is the set of allocations which are not strongly dominated byany other allocation via any coalition belonging to G. Denote the G-weak core
correspondence by C W G .8 If G = 2N \ {∅}, then the G-strong core (G-weak core,respectively) is simply called the strong core (weak core, respectively). Denotethe strong core correspondence by C, and the weak core correspondence by C W .
An allocation x is Pareto optimal under R if there is no allocation which
weakly dominates x via N . And an allocation x is individually rational under
R if ∀i ∈ N : xRi ω. Denote by I the correspondence that chooses the set of individually rational allocations for every preference profile. Any allocation belonging
5 Sönmez (1999) discussed that six preceding models are included as subclasses.
6 Throughout the paper, inclusion ”⊂” is weak.
7 A weak order is a complete and transitive binary relation.
8 In some literature, weak core is simply called ”core.” And in others, strong core is referred
to as ”core.” To avoid unnecessary confusion, here I do not use the term ”core.”4

to the strong core is both individually rational and Pareto optimal. Note that aweak core allocation is individually rational but not necessarily Pareto optimal.
A solution is a function ϕ : DN −→ Af . Say ϕ is Pareto optimal if for any
R ∈ DN , the allocation ϕ(R) is Pareto optimal under R. Call ϕ individually
rational if for any R ∈ DN , the allocation ϕ(R) is individually rational under R.

1.2

Preference revelation games

I introduce preference revelation games and some related concepts. Let a list(N, ω, Af , DN ) be given. Let ϕ be a solution with the preference domain DN . A
direct mechanism induced by ϕ is a pair (DN , ϕ), where each Di is interpreted
as the strategy space of individual i, and ϕ : DN −→ Af as the outcome
function. Given a direct mechanism (DN , ϕ), a preference profile R ∈ DN defines
the strategic game (DN , ϕ, R). This game is called a preference revelation
game induced by ϕ.
Let (DN , ϕ, R) be a preference revelation game. Then a strategy profile R? ∈DN is a G-proof Nash equilibrium if ∀S ∈ G : ∀R0S ∈ DS :[∀i ∈ S : ϕ(R?−S , R0S )Ri ϕ(R? )] ⇒ [∃j ∈ S : ϕ(R?−S , R0S )I j ϕ(R? )].
Denote by N G (DN , ϕ, R) the set of G-proof Nash equilibria. And call R? ∈ DN astrict G-proof Nash equilibrium if ∀S ∈ G : ∀R0S ∈ DS :[∀i ∈ S : ϕ(R?−S , R0S )Ri ϕ(R? )] ⇒ [∀i ∈ S : ϕ(R?−S , R0S )I i ϕ(R? )].
Denote by sN G (DN , ϕ, R) the set of strict G-proof Nash equilibria. If G = 2N \{∅},
then a G-proof Nash equilibrium (strict G-proof Nash equilibirum, respectively) is
called a strong Nash equilibrium (strict strong Nash equilibrium, respectively). Denote the set of strong Nash equilibrium by SN (DN , ϕ, R), and the setof strict strong Nash equilibrium by SSN (DN , ϕ, R). If G = {{i} | i ∈ N }, then a(strict) G-proof Nash equilibirum is called a Nash equilibrium. Denote the setof Nash equilibrium by N ash(DN , ϕ, R).
Let a direct mechanism (DN , ϕ) be given. An equilibrium concept is acorrespondence Eq which chooses a subset of the set of strategy profiles DN foreach strategic game (DN , ϕ, R) with R ∈ DN , i.e. Eq(DN , ϕ, R) ⊂ DN . For
example, Nash equilibrium is an equilibrium concept. Let Φ : DN →→ Af be anonempty-valued correspondence. Then say that the direct mechanism (DN , ϕ)weakly implements the correspondence Φ in an equilibrium concept Eq if ∀R ∈DN : ϕ(Eq(DN , ϕ, R)) ⊂ Φ(R) and Eq(DN , ϕ, R) 6= ∅. And say that the direct
mechanism (DN , ϕ) fully implements (or implements) the correspondence Φin an equilibrium concept Eq if ∀R ∈ DN : Φ(R) = ϕ(Eq(DN , ϕ, R)).

2

Main results

In the following, let the list (N, ω, Af , DN ) be given. I require that in all the
results which follow, Conditions A and B in the below are satisfied.
Let A ⊂ Af and Ri ∈ Di . Let top Ri (A) denote the set {x ∈ A | ∀y ∈ A :xRi y}.

5

Condition A: For each i ∈ N , Di satisfies the following:(i) There is no consumption externality, i.e. ∀Ri ∈ Di : ∀x, y ∈ Af : x(i) =y(i) ⇒ xI i y.
(ii) For any x ∈ Af , there is some Ri ∈ Di for which top Ri (Af ) = {z | z(i) =x(i)}, and ω(i) 6= x(i) ⇒ top Ri (Af \ top Ri (Af )) = {z | z(i) = ω(i)}.
Condition B: The set Af satisfies the following: Let S be a coalition, andx, y ∈ Af . Then if x(S) = ω(S) = y(S) (which implies x(N \ S) = ω(N \ S) =y(N \ S)), then Af contains the allocation v such that [∀i ∈ S : v(i) = x(i)] and[∀i ∈ N \ S : v(i) = y(i)].
Condition A requires some ”regularity” of the domain. And Condition B requires some ”richness” of the feasible allocations. Note that the domain P definedin Section 1.1 satisfies Condition A. Also Condition B is satisfied in the marriage
problems (Gale and Shapley, 1964) and the housing markets (Shapley and
Scarf, 1974)
I present the main results. Firstly, I provide a lemma which asserts that,roughly speaking, the ’blocking power’ of a coalition in the allocation problem
implies their ’deviation power’ in the induced preference revelation game.
Lemma 2.1: Let ϕ be a solution that is individually rational and Pareto optimal. Let S be a coalition, x ∈ Af , and R, R0 ∈ DN . Then if x weakly dominates
the allocation ϕ(R0 ) via S under R, then there is some R?S ∈ DS such that[∀i ∈ S : ϕ(R0−S , R?S )Ri ϕ(R0 )]&[∃j ∈ S : ϕ(R0−S , R?S )P j ϕ(R0 )].
Proof: Let S be a coalition, x ∈ Af , and R, R0 ∈ DN . Assume x weakly dominates
the allocation ϕ(R0 ) via S under R. Then choose R?S ∈ DS satisfying for each i ∈S, top R?i (Af ) = {z | z(i) = x(i)}, and ω(i) 6= x(i) ⇒ top R?i (Af \top R?i (Af )) ={z | z(i) = ω(i)}. Such R?i exists in Di by Condition A. Since ϕ is individually rational, for each i ∈ S, ϕ(R0−S , R?S )(i) equals x(i) or ω(i). Denote ϕ(R0−S , R?S ) byy. Now I will show ∀i ∈ S : x(i) = y(i). Suppose that for some i ∈ S, x(i) 6= y(i)(which implies y(i) = ω(i) 6= x(i)). Since x weakly dominates ϕ(R0 ) via S, it holds
x(S) = ω(S). Then consider an allocation v which satisfies [∀i ∈ S : v(i) = x(i)]and [∀i ∈ N \ S : v(i) = y(i)]. Condition B ensures Af contains this allocationv. Then v Pareto-dominates y. But this contradicts the Pareto optimality of ϕ.
Therefore, I have ∀i ∈ S : x(i) = y(i). Recall that x weakly dominates ϕ(R0 ) via
S under R. Then it follows [∀i ∈ S : yRi ϕ(R0 )]&[∃j ∈ S : yP j ϕ(R0 )]. 2
The following is immediate from Lemma 2.1.
Corollary 2.2: Let ϕ be a solution that is individually rational and Pareto optimal. Then ∀R ∈ DN : ϕ(sN G (DN , ϕ, R)) ⊂ C G (R).
Proof: Let R ∈ DN . Assume x 6∈ C G (R). Then there is some y ∈ Af which
weakly dominates x via some coalition S ∈ G under R. Pick up R0 ∈ DN besuch that ϕ(R0 ) = x. (If the image of ϕ does not contain x, then immediately6x 6∈ ϕ(sN G (DN , ϕ, R)).) Then Lemma 2.1 implies that there is some R?S ∈ DS
such that [∀i ∈ S : ϕ(R0−S , R?S )Ri ϕ(R0 )]&[∃j ∈ S : ϕ(R0−S , R?S )P j ϕ(R0 )]. Since
this is true for any R0 ∈ DN with ϕ(R0 ) = x, I have x 6∈ ϕ(sN G (DN , ϕ, R)). 2
Next I turn to the reverse direction of inclusion. Let us call G monotonic if[S ∈ G, S ⊂ T ] ⇒ T ∈ G.
Lemma 2.3: Let ϕ be a solution that is individually rational and Pareto optimal. Let G be a monotonic class of coalitions. Then ∀R ∈ DN : C G (R) ⊂ϕ(sN G (DN , ϕ, R)).
Proof: Let R ∈ DN . And let x ∈ C G (R). Choose R0 ∈ DN such that for any i ∈N , top R0i (Af ) = {z | z(i) = x(i)}, and ω(i) 6= x(i) ⇒ top R0i (Af \ top R0i (Af )) ={z | z(i) = ω(i)}. Then since ϕ is Pareto optimal, ϕ(R0 ) = x. Now I will show
R0 ∈ sN G (DN , ϕ, R)) (thus x ∈ ϕ(sN G (DN , ϕ, R))). Suppose not. Then there aresome coalition S ∈ G and R?S ∈ DS such that[∀i ∈ S : ϕ(R0−S , R?S )Ri ϕ(R0 )]&[∃j ∈ S : ϕ(R0−S , R?S )P j ϕ(R0 )].

(1)

Denote ϕ(R0−S , R?S ) by y. Then if y(S) = ω(S), then (1) implies y weakly dominates x via S under R, which says x 6∈ C G (R), a contradiction. Thus it must bey(S) 6= ω(S). Now let T denote an ⊂-minimal element of the class of coalitions{G ⊂ N | S ⊂ G&y(G) = ω(G)}. Thus for any i ∈ T \ S, y(i) 6= ω(i). (Otherwise,
T is not ⊂-minimal.) Then since ϕ is individually rational, the construction of R0
implies ∀i ∈ T \ S : x(i) = y(i), which implies xI i y. This and (1) together say[∀i ∈ T : yRi x] and [∃j ∈ S ⊂ T : yP j x], and by assumption y(T ) = ω(T ), i.e.
y weakly dominates x via S under R. Since G is monotonic, T ∈ G. Thus I havex 6∈ C G (R), a contradiction. This concludes R0 ∈ sN G (DN , ϕ, R). 2
In Lemma 2.3 above, the monotonicity assumption of G is essential. Whenone considers the marriage problems only, on the analogy of the result of Sönmez(1997) (mentioned in Introdcution, also stated formally in Section 3), one may
suspect that the above result still holds true without the monotonicity of G. But
this is not the case. One has the following counter-example.
Example 2.4: Let M = {1, 2} and W = {3, 4}. Consider the case where N =M ∪ W ; ∀i ∈ N, ω(i) = {i}; andAf = {x ∈ A0 | ∀i ∈ N, ]x(i) = 1; ∀m ∈ M, x(m) ⊂ W ∪ {m};∀w ∈ W ; x(w) ⊂ M ∪ {w}; ∀i, j ∈ N, x(i) = j ⇔ x(j) = i}.
This is the marriage problem (Gale and Shapley, 1962) with two men and two
women. Assume the domain DN equals P.9 Let ϕ be a stable solution. Let G be{{i} | i ∈ N } ∪ {{1, 2, 3}}. Note that G is not monotonic. The following gives one
example of R ∈ P such that C G (R) 6⊂ ϕ(sN G (P, ϕ, R)).
9 In this case, a preference relation on the feasible allocations (matchings) is identified withthe corresponding relation on men (or women) plus herself (or himself).

7Let R ∈ P be the profile such that3P 1 1P 1 4,
4P 2 2P 2 3,
1P 5 3P 3 2,
2P 4 4P 4 1.
Consider the matching x ∈ Af such thatx(1) = 1,
x(2) = 4,
x(3) = 3.
It is easy to check x ∈ C G (R). But x 6∈ ϕ(sN G (P, ϕ, R)), which is proved as follows:
Suppose that there is some R0 ∈ P such that x = ϕ(R0 ) and R0 ∈ sN G (P, ϕ, R).
Consider the profile (R{1,2,3} , R04 ). Under this profile, there is the unique stablematching y such thaty(1) = 3,y(2) = 4.
(This is because: (1) It is clear that 1 and 3 have to be matched each other under(R{1,2,3} , R04 ). (2) If 4 were not matched with 2 under (R{1,2,3} , R04 ), then 4 would
have to be matched with himself. But this implies that 4 would have been matchedwith himself under R0 . ) Then y = ϕ(R{1,2,3} , R04 ). Note that yP 1 x, yP 3 x andyI 2 x. Thus R0 6∈ sN G (P, ϕ, R). This completes the proof.
Now it follows C G (R) 6⊂ ϕ(sN G (P, ϕ, R)). 2
From Corollary 2.2 and Lemma 2.3, I conclude the following.
Theorem 2.5: Let ϕ be a solution that is individually rational and Pareto optimal. Let G be a monotonic class of coalitions. Then ∀R ∈ DN : C G (R) =ϕ(sN G (DN , ϕ, R)).
Under the additional assumption of the nonempty-valuedness of C G , this theorem says that the direct mechanism (DN , ϕ) implements the correspondence C G
in strict G-proof Nash equilibrium.
In considering G, in view of decentralized behavior of individuals, it should beassumed that ∀i ∈ N, {i} ∈ G. This and the monotonicty of G together imply that
G equals the set of all coalitions. Then Theorem 2.4 reduces to the following result.
Corollary 2.6: Let ϕ be a solution that is individually rational and Pareto optimal. Then ∀R ∈ DN : C(R) = ϕ(SSN (DN , ϕ, R)).
Under the additional assumption of the nonempty-valuedness of C, this corollary says that the direct mechanism (DN , ϕ) implements the correspondence C instrict strong Nash equilibrium.
8

Shin and Suh (1996) proved that in the context of the marriage problems,
the direct mechanism induced by any stable solution implements the strong core
correspondence in strict strong Nash equilibrium. Corollary 2.6 strengthens thisresult by extending it to the general setting, and enlarging the set of solutions
inducing the mechanism.
Shin and Suh (1996) also pointed out that in the above result of the marriage
problems, strict strong Nash equilibrium can be replaced with strong Nash equilibrium. Does the same thing hold true in the present general model? The answer
is negative. There is a counter-example: In the case of the ”housing market”(Shapley and Scarf, 1974) with three traders, the direct mechanism induced bya strong core selection (that is trivially individually rational and Pareto optimal)
does not even weakly implement the strong core correspondence in strong Nashequilibrium. Of course, neither does in Nash equilibirum since any strong Nashequilibrium is a Nash equilibrium.
Example 2.7: Consider the case where N = {1, 2, 3}; ∀i ∈ N : #ω(i) = 1; andAf = {z ∈ A0 | ∀i ∈ N : #z(i) = 1}. This is the housing market (Shapley and
Scarf, 1974) with three traders. Assume the domain DN equals P.10 In this case,the strong core correspondence is single-valued on the domain P by the result ofRoth and Postlewaite (1977). Denote ω(i) simply by i. Let ϕ be the strong coresolution.11 I give one example of R ∈ P such that ϕ(SN (P, ϕ, R)) 6⊂ C(R): Let
R ∈ P be the profile such that2P 1 1P 1 3,
3P 2 1P 2 2,
1P 3 3P 3 2.
Note that ϕ(R) = (2, 3, 1). Say x = (2, 1, 3)(6= ϕ(R)). And choose another profile
R0 ∈ P such that
3P 01 2P 01 1,
1P 02 2P 02 3,
3P 03 1P 03 2.
Then ϕ(R0 ) = x. And it is easy to check R0 ∈ SN (P, ϕ, R). Thus I havex ∈ ϕ(SN (P, ϕ, R)) and x 6∈ C(R), i.e. ϕ(SN (P, ϕ, R)) 6⊂ C(R). (Also, this
implies ϕ(N ash(P, ϕ, R)) 6⊂ C(R).) 2

3

Additional results

Given the implementability results obtained in the previous section, this section
examines which part of the preceding results in the context of the marriage prob10 In this case, a preference relation on Af is identified with the corresponding relation definedon ω(N ).
11 Here and in the sequel, abusing notation, for an allocation x, x denotes the triple(x(1), x(2), x(3)).

9lems are to be extended to the present model. Recall those results I have discussed
in Introduction (Alcalde, 1996; Shin and Suh, 1996, Sönmez, 1997).12(1) Alcalde: If ϕ is a stable solution, then ∀R ∈ P : I(R) = ϕ(N ash(P, ϕ, R)).
(2) Shin and Suh: If ϕ is a stable solution, then ∀R ∈ P : C W (R) = ϕ(SN (P, ϕ, R)).
(3) Sönmez: If ϕ is individually rational and Pareto optimal, then ∀R ∈ P :C W G (R) = ϕ(N G (P, ϕ, R)).
(4) Shin and Suh: If ϕ is a stable solution, then ∀R ∈ P : C(R) = ϕ(SSN (P, ϕ, R)).
Note that (3) implies (1) and (2). However, (3) does not imply (4). As I haveshown in the previous section, (4) is generalized to the general model. Then what
about the other three results?
In the following, I show that only a ’half’ of (4) (thus (1) and (2), too) is extended to the general model. That is, it holds true that ∀R ∈ P : ϕ(N G (P, ϕ, R)) ⊂C W G (R). However, none of these results is generalized fully.
The following is a lemma analogous to Lemma 2.1 above.
Lemma 3.8: Let ϕ be a solution that is individually rational and Pareto optimal.
Let S be a coalition, x ∈ Af , and R, R0 ∈ DN . Then if x strongly dominates
the allocation ϕ(R0 ) via S under R, then there is some R?S ∈ DS such that∀i ∈ S : ϕ(R0−S , R?S )P i ϕ(R0 ).
Lemma 3.8 will be proved along the same line to Lemma 2.1. So I omit theproof. Just like Corollary 2.2 follows from Lemma 2.1, one obtains the following
Corollary 3.9 from Lemma 3.8
Corollary 3.9: Let ϕ be a solution that is individually rational and Pareto optimal. Then ∀R ∈ DN : ϕ(N G (DN , ϕ, R)) ⊂ C W G (R).
Turning to the reverse inclusion, I argue by the counter-example in the below(Example 3.10) that not only (3) but neither (1) nor (2) is to be fully generalized.
That is,Example 3.10: Consider the housing market with three traders as defined in
Example 2.6. Let ϕ be the strong core solution. I give one example of R ∈ P suchthat C W (R) 6⊂ ϕ(N ash(P, ϕ, R)): Choose R ∈ P such that2P 1 1P 1 3,
1P 2 3P 2 2,
1P 3 3P 3 2.
Pick up x = (2, 3, 1) ∈ C W (R). Let R0 ∈ P be any profile such that x =ϕ(R0 ). Then it is easy to see that such R0 satisfies ∀i ∈ N : x(i) ranks top
12 Here I have dropped the result by Ma (1995). This employs rematching-proof equilibrium,
which requires the ”two-sided” structure that is specific to the marriage problems, and is notapplicable to the general setting.

10

in R0i . Now choose any R?2 ∈ P 2 which ranks the good 1 as the best. Thenϕ(R0−2 , R?2 ) = (2, 1, 3). Now clearly, ϕ(R0−2 , R?2 )(2)P 2 ϕ(R0 )(2). This says thatany such R0 cannot be a Nash equilibrium of the game (P, ϕ, R). Thus I havex ∈ C W (R) and x 6∈ ϕ(N ash(P, ϕ, R)), i.e. C W (R) 6⊂ ϕ(N ash(P, ϕ, R)). Thisimplies I(R) 6⊂ ϕ(N ash(P, ϕ, R)) and C W (R) 6⊂ ϕ(SN (P, ϕ, R)). 2

References[1] Alcalde J (1996): Implementation of stable solutions to the marriage problem. J
Econ Theory 69: pp1–18.
[2] Gale D and Shapley L(1962): College admissions and the stability of marriage.
Amer Math Monthly 69: pp9–15[3] Hurwicz L (1978): On the interaction between information and incentives in organizations In: Krippendorff K (ed): Communication and Control in Society. Scientific
Publishers. New York. pp123–47.
[4] Kalai E, Postlewaite A and Roberts J (1979): A group incentive compatible mechanism yielding core allocations. J Econ Theory 20: pp13–22[5] Ma J (1995): Stable matchings and rematching-proof equilibria in a two-sided
matching market. J Econ Theory 66: pp352–69.
[6] Otani Y and Sicilian (1982):
Theory 27: pp47–68.

Equilibrium of Warlas preference games. J Econ

[7] Roth A and Sotomayor M (1990): Two-Sided Matching: A Study in Game Theoretic
Modeling and Analysis. Cambridge University Press. London/New York.
[8] Roth A and Postlewaite A (1977): Weak versus strong domination in a market withindivisible goods. J Math Econ 4: pp131–37.
[9] Shapley L and Scarf H (1974): On cores and indivisibility. J Math Econ 1: pp23–37.
[10] Shin S and Suh S-C (1996): A Mechanism implementing the stable rule in marriage
problems. Econ Letters 51: pp185–9.
[11] Sönmez T (1999): Strategy-proofness and essentially single-valued cores. Econometrica 67: pp677–89.
[12] Sönmez T (1997): Games of manipulation in marriage problems. Games Econ
Behavior 20: pp169–76.
[13] Takamiya K (2003) On strategy-proofness and essentially single-valued cores: A
converse result. Soc Choice Welfare 20: pp77–83.
[14] Thomson W (1984): The manipulability of resource allocation mechanisms. Rev
Econ Studies 51: pp447–60.
[15] Thomson W (1988): The manipulability of the Shapley value. Int J Game Theory
17: pp101–27.

11