On the equivalence of G-weak and -strong cores in themarriage problem
Koji Takamiya
Institute of Social and Economic ResearchAbstract
In the marriage problem (two-sided one-to-one matching problem), it is well-known that theweak core, the strong core and the set of stable matchings are all equivalent. This paper
generalizes the above observation considering the G-weak core and the G-strong core. These
are core concepts in which blocking power is restricted to the coalitions belonging to theprescribed class of coalitions G. I give a necessary and sufficient condition that G shouldsatisfy for the equivalence of the G-weak core and the G-strong core.

I am grateful to Eiichi Miyagawa for motivating this research. All errors are my own responsibility.
Citation: Takamiya, Koji, (2006) "On the equivalence of G-weak and -strong cores in the marriage problem." Economics
Bulletin, Vol. 3, No. 19 pp. 1-8
Submitted: July 5, 2006. Accepted: August 31, 2006.
URL: http://economicsbulletin.vanderbilt.edu/2006/volume3/EB-06C70009A.pdf

0Introduction

In the marriage problem (Gale and Shapley, 1964), it is well-known that theweak core, the strong core and the set of stable matchings are all equivalent (Roth and Sotomayor, 1990). This paper generalizes this observationconsidering the “G-weak core” and the “G-strong core.” These are core concepts in which blocking power is restricted to the coalitions belonging to theprescribed class of coalitions G. I give a theorem from which one obtains anecessary and sufficient condition that G should satisfy for the equivalence of
the G-weak core and the G-strong core.

0.1

Preliminary definitions

A marriage problem is a list (M, W, (Ri )i∈M ∪W ). Here M is the set of“men,” and W is the set of “women.” Assume that M and W are both
nonempty and finite. (Ri )i∈M ∪W is a preference profile. For i ∈ M (W ,resp.), Ri is assumed to be a linear ordering (i.e. complete, transitive andanti-symmetric binary relation) over W ∪{i} (M ∪{i}, resp.). As usual, P i (I i ,resp.) denotes the asymmetric (symmetric, resp.) part of Ri . Let P denotethe set of preference profiles. A matching is a function µ : M ∪W → M ∪W
satisfyingi ∈ M ⇒ µ(i) ∈ W ∪ {i},i ∈ W ⇒ µ(i) ∈ M ∪ {i},i ∈ M ∪ W ⇒ µ(µ(i)) = i.
Let M denote the set of matchings.
Let µ, ν ∈ M. Let S ⊂ M ∪ W with S 6= ∅. Then we say that µ weakly
dominates ν via S if∀i ∈ S, µRi ν;∃j ∈ S : µP j ν;µ(S) = S.
And we say that µ strongly dominates ν via S if∀i ∈ S, µP i ν;µ(S) = S.
When a matching µ dominates (weakly or strongly) some other matching ν via S, equivalently, we say “S blocks ν by µ (with weak or strongdomination).”
Let G be a nonempty class of coalitions. Then the G-weak core is the setof all matchings that are not strongly dominated by any other matchings via
1

any coalitions in G. Similarly, the G-strong core is the set of all matchings
that are not weakly dominated by any other matchings via any coalitions inG. For the case where G = 2M ∪W \{∅}, these cores are simply called the weakcore and the strong core, respectively. Since in the sequel the components
M, W are fixed, these G-cores are regarded as functions of preference profiles.
Let us denote the G-weak core by wC G , and the G-strong core by sC G . And
let wC and sC denote the weak core and the strong core, respectively.
Let V denote the set of “pairs.” Here a “pair” means a coalition consisting of one man and one woman. That is, V := {S ⊂ M ∪ W | #S =2, #(S ∩M ) = 1}. A stable matching is a matching that cannot be blocked(with strong domination) by any pair or individual. Thus the set of stablematchings is nothing but the G-weak core with G = {{i} | i ∈ M ∪ W } ∪ V .

0.2

Motivation

There are two observations that have motivated the present study. The firstone is the following well-known result.
Theorem 0 (Roth and Sotomayor, 1990) Let G be {{i} | i ∈ M ∪ W } ∪ V .
Then on P, the following four core concepts are all equivalent:(i) G-strong core,(ii) G-weak core,(iii) weak core,(iv) strong core.
Given the theorem in the above, one may suspect that the equivalencesimilar to as stated in this theorem holds true for arbitrary G. However,this is not the case. (A counter-example is Example 1 in the below.) Then
we are motivated to ask for what G one obtains such equivalence.
Example 1 Let M be {1, 3} and W be {2, 4}. Let G consist of only one
element, namely M ∪ W . Assume that each individual has the following
preference at R.
R1 : (2, 1, 4),
R2 : (1, 2, 3),
R3 : (4, 3, 2),
R4 : (3, 4, 1).
Consider a matching µ such that µ(1) = 1, µ(2) = 2 and µ(3) = 4, andanother matching ν such that ν(1) = 2 and ν(3) = 4. Then ν weakly
dominates µ via M ∪ W . But no matchings strongly dominate µ via M ∪ W .
Thus wC G (R) 6= sC G (R). 22

The second observation that has motivated this study is some resultsfrom implementation theory. In Sönmez (1997), it has been proved that in
the context of the marriage problem, the direct mechanism induced by any
solution that is individually rational and Pareto efficient implements the Gweak core in G-proof Nash equilibrium.1 This result unifies several preceding
results in implementation by direct mechanisms in the marriage problem suchas Alcalde (1996), Ma (1995) and Shin and Suh (1996).
On the other hand, Takamiya (2005) proved that the direct mechanism
induced by any solution that is individually rational and Pareto efficient
implements the G-strong core in strict G-proof Nash equilibrium, under
the additional assumption that G is monotonic.2 This result is proved in
the context of a general class of allocation problems (as defined in Sönmez(1999)) that contains the marriage problem as a special case.
Given these results, one would naturally ask when these two results overlap with each other. Then, one is motivated to ask for what G, the G-weakcore and the G-strong core are equivalent to each other.

1Results

1.1

Main theorem and corollaries

Let G1 and G2 be classes of coalitions. In the sequel, for example, “wC G2 ⊂sC G1 ” is a shorthand notation for “∀R ∈ P, wC G2 (R) ⊂ sC G1 (R).”
Condition A For any S ∈ G1 , both of the following hold true:(i) ({m, w} ⊂ S & {m, w} ∈ V ) ⇒ {m, w} ∈ G2 , and(ii) [i ∈ S & ((i ∈ M & W 6⊂ S) ∨ (i ∈ W & M 6⊂ S))] ⇒ {i} ∈ G2 .
Then the following is the main theorem of this paper.
Theorem 1 G1 and G2 satisfy Condition A if, and only if, it holds true thatwC G2 ⊂ sC G1 .
Let G be a class of coalitions. Then by replacing G1 and G2 with G inCondition A above, one obtains a necessary and sufficient condition for the1

In a game in strategic-form, a strategy profile is said to be “G-proof Nash equilibrium”
if no coalition belonging to G can deviate from that strategy profile with every player inthe coalition being strictly better off. “Strict G-proof Nash equilibrium” is defined in thesame way except that a group deviation succeeds merely with at least one player being
strictly better off and the other players not being worse off. These concepts originate in
Kalai, Postlewaite and Roberts (1979).
2
Here G is said to be “monotonic” if for any coalition S in G, any supercoalition of S
belongs to G.

3

equivalence of the G-weak core and the G-strong core. This is the most important corollary to Theorem 1.
Condition A0 For any S ∈ G, both of the following hold true:(i) ({m, w} ⊂ S & {m, w} ∈ V ) ⇒ {m, w} ∈ G, and(ii) [i ∈ S & ((i ∈ M & W 6⊂ S) ∨ (i ∈ W & M 6⊂ S))] ⇒ {i} ∈ G.
Corollary 1 G satisfies Condition A0 if, and only if, it holds true that wC G =sC G .
The following presents some other corollaries that directly follow from
Theorem 1 in the above. Let us denote F = {{i} | i ∈ M ∪ W } ∪ V .
Corollary 2 For any class of coalitions G, wC F ⊂ sC G and sC F ⊂ wC G .
Corollary 3 If F ⊂ G, then sC F = wC F = sC G = wC G = wC = sC.
Clearly, the well-known Theorem 0 (Roth and Sotomayor, 1990) mentioned in Section 0.2 follows from Corollary 3. The following is somewhat
less obvious.
Corollary 4 F is the unique ⊂-minimal element in the set of classes ofcoalitions {G | sC G = wC G = sC = wC}.
Remark In all these results, the assumption of linear preferences is essential.
Things would be totally different when weak preferences are included. This
deserves independent research.

1.2

Proof of Theorem 1

Proof of the “only if ” part. Suppose that Condition A is satisfied and thatthere exist some R ∈ P and µ ∈ M such that µ ∈ wC G2 (R) and µ 6∈ sC G1 (R).
Then there exists some S ∈ G1 that blocks µ with weak domination, that is,for some ν ∈ M,∀i ∈ S, ν(i)Ri µ(i),∃j ∈ S : ν(j)P j µ(j),ν(S) = S.

(1)
(2)
(3)

Then fix j ∈ S that satisfies (2) above. And denote k = ν(j). Then thereare two cases that have to be considered:(i) If k 6= j, then k ∈ S by (3). Then (i) of Condition A implies {j, k} ∈ G2 .
And ν(k)P k µ(k) since all preferences are linear orderings. Thus ν strongly
dominates µ via {j, k}. This yields µ 6∈ wC G2 (R), a contradiction.
4

(ii) If k = j, then j having improved strictly from µ to ν means that j
was matched with some other individual in µ. Let us call this individual l.
Then, without loss of generality, assume j ∈ M . This implies l ∈ W . Let us
consider the two cases in the following:(ii-1) First, assume W 6⊂ S. In this case, (ii) of Condition A implies{j} ∈ G2 . And clearly, ν strongly dominates µ via {j}. Then it followsµ 6∈ wC G2 (R), a contradiction.
(ii-2) Next, assume W ⊂ S. This implies l ∈ S. Then since linear preferences are assumed, it must be ν(l)P l µ(l). Let us denote h = ν(l). Then let
us consider two cases, namely h = l and h 6= l: First, assume h = l. Thenν({j, l}) = {j, l}. Then it follows that ν strongly dominates µ via {j, l}.
And by (i) of Condition A, {j, l} ∈ G2 . Thus µ 6∈ wC G2 (R), a contradiction.
Second, assume h 6= l. This case is identical to the case (i) in the above. 2
Proof of the “if ” part. Suppose that Condition A is not satisfied. Then I
want to show that there are some preference profiles R for which wC G2 (R) 6⊂
sC G1 (R). There are two cases to consider.
(i) Suppose that (i) of Condition A is not satisfied. Then there exist apair {m, w} and a coalition S such thatS ∈ G1 ,{m, w} ⊂ S,{m, w} 6∈ G2 .

(4)
(5)
(6)

Consider a preference profile R ∈ P that satisfies
Rm : (w, m, · · ·),Rw : (m, w, · · ·),(i ∈ M ∪ W & i 6= m, w) ⇒ Ri : (i, · · ·).

(7)
(8)
(9)

Consider two matchings µ and ν such thati ∈ M ∪ W ⇒ µ(i) = i;ν(m) = w,(i ∈ M ∪ W & i 6= m, w) ⇒ ν(i) = i.

(10)
(11)
(12)

Clearly, ν strongly dominates µ via {m, w}. Note that no other matchingstrongly dominates µ via any coalition. Then since {m, w} 6∈ G2 (by (6)), it
follows µ ∈ wC G2 (R).
On the other hand, since ν(S) = S (by (5), (11) and (12)), ν weakly
dominates µ via S. And S ∈ G1 (by (4)). These imply µ 6∈ sC G1 (R). Thus
wC G2 (R) 6⊂ sC G1 (R).

5

(ii) Suppose that (ii) of Condition A is not satisfied. Then without lossof generality, we may assume that there exist m ∈ M and a coalition S suchthatm ∈ S ∈ G1 ,W 6⊂ S,{m} 6∈ G2 .

(13)
(14)
(15)

Now fix one w ∈ W such that w 6∈ S. (This is possible due to (14).)
Consider a preference profile R ∈ P that satisfies
Rm : (m, w, · · ·),Rw : (m, w, · · ·),(i ∈ M ∪ W & i 6= m, w) ⇒ Ri : (i, · · ·).

(16)
(17)
(18)

Consider two matchings µ and ν such thatµ(m) = w,(i ∈ M ∪ W & i 6= m, w) ⇒ µ(i) = i;i ∈ M ∪ W ⇒ ν(i) = i.

(19)
(20)
(21)

Clearly, ν strongly dominates µ via {m}. Note that no other matchingstrongly dominates µ via any coalition. Then since {m} 6∈ G2 (by (15)), itfollows µ ∈ wC G2 (R).
On the other hand, since ν(S) = S (by (21)), ν weakly dominates µ via S.
And S ∈ G1 (by (13)). These imply µ 6∈ sC G1 (R). Thus wC G2 (R) 6⊂ sC G1 (R).
26

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] Kalai E, Postlewaite A and Roberts J (1979): A group incentive compatible
mechanism yielding core allocations. J Econ Theory 20: pp13–22[4] Ma J (1995): Stable matchings and rematching-proof equilibria in a two-sided
matching market. J Econ Theory 66: pp352–69.
[5] Roth A and Sotomayor M (1990): Two-Sided Matching: A Study in Game
Theoretic Modeling and Analysis. Cambridge University Press. London/NewYork.
[6] Shin S and Suh S-C (1996): A Mechanism implementing the stable rule inmarriage problems. Econ Letters 51: pp185–9.
[7] Sönmez T (1999): Strategy-proofness and essentially single-valued cores.
Econometrica 67: pp677–89.
[8] Sönmez T (1997): Games of manipulation in marriage problems. Games EconBehavior 20: pp169–76.
[9] Takamiya K (2005): Preference revelation games and strong cores of allocation
problems with indivisibilities. Mimeo. ISER, Osaka University.

7