Every finite distributive lattice is a set of stable matchings

UNIVERSITY Oh

ILLINOIS LIBRARY

AT URBANA-CHAMPAIGN

BOOKSTACKS

H

Ut* I ^ ** ^

m

H

H

Digitized by the Internet Archive

in 2011 with funding from

University of Illinois Urbana-Champaign

http://www.archive.org/details/everyfinitedistr865blai

* V~~..r "A ft

sBCS:-

•58B5*7

FACULTY WORKING
PAPER NO. 865

Every Finite Distributive Lattice Is a Set cf
Stable Matchings

Charles Blair

<*>i£

**^

*y,

Co-lege of Commerce and Business Administration
Bureau of Economic and Business Research
University of Illinois. Urbana-Chanpaign

BEBR

FACULTY WORKING PAPER NO. 865
College of Commerce and Business Administration
University of Illinois at Urbana-Champaign
April 1982

Every Finite Distributive Lattice
Is a Set of Stable Matchings

Charles Blair, Associate Professor
Department of Business Administration

Abstract
We show that, given a lattice, a set of men and women with prefer-
ences can be constructed whose stable matchings are precisely that
lattice. This is a converse of a result of J. H. Conway.

Every Finite Distributive Lattice is a Set of Stable Matchings

by
Charles Blair

Suppose we have n men and n women. Each of the 2n people has a
linear preference ordering on those of the opposite sex. We are inter-
ested in matchings to form n couples. A matching is stable if we cannot
find a woman in one couple and a man in another who would prefer each
other to their present partners.

Stable matchings were first defined by Gale and Shapley [1], who
showed that for any preference orderings a stable matching always exists.
In general, there will be several stable matchings. For example, if
all the men happen to have different first preferences, giving each man
his first choice will be stable, regardless of the women's preferences.
Similarly, giving each woman her first choice (if possible) will be
stable.

Conway [2, p. 87-92] defines a partial ordering on the set of stable
matchings as follows: one matching is >_ another if every man is at least
as happy with his partner in the first matching as with his partner in
the second. He shows that the set of stable matchings is always a finite
distributive lattice. Knuth 12, p. 92] asks whether every finite dis-
tributive lattice can occur as the set of stable matchings generated by
some set of men and women. We show this is the case.

We will require some preliminary facts about lattices. If L is a
distributive lattice and x€ L let V = {v |y <_x} be disjoint from L.
L is the partial ordering on L u V defined by (i) if w,z e L then w >_ z

-2-

in Lx iff w > z in L. (ii) if w € L, v e V w > v iff w > z in L. (iii)
— z — z —

•yr

v > v iff w > z» (iv) v f z for any w,z. L is a distributive lattice,
w — z — w —

Intuitively, L is formed from L by making a copy of all the elements <_ x
and putting the copies immediately below the originals.

Lemma 1: If a set S of lattices includes a one-element lattice and
includes a lattice isomorphic to L for every L e S, x e L then every
finite distributive lattice is isomorphic to a lattice in S.

Proof: Let M be a finite distributive lattice. We argue by induc-
tion on the size of M. If M has one element the result is immediate.
Otherwise let z be the smallest member of M which is not the meet of two
members different from z. Let w be the meet of all members > z.
H = fy|y ^z} is a distributive sublattice in which meets and joins are
preserved. The minimality property of z implies that if y <_ z then
y = z A u for some u e N. Moreover, if u1 A z = u_ A z f z then
u. A w = (u.. A w) A z = (u~ Aw) A z = u« Aw. Hence M is isomorphic
to NW. By induction hypothesis, N is isomorphic to a lattice in S, so
M is isomorphic to a lattice in S. Q.E.D.

To complete the proof we will show how to construct a set of
men and women whose preferences yield L from a set whose preferences
yield L.

Lemma_2: Let L be the set of stable matchings possible for women

w1,...,w and men m. m . Suppose x = (n^W-i mnWn^ S *" ^ien

the set of stable matchings for the 2n men nL,...,m ; m! m' and women

w. , . . . ,w ; w' , . . . ,w' with the following preferences is isomorphic to L :

m. ; Use the original preferences of m. in the n-couple situation
for all women strictly preferred to (above) w^ Replace w± by w|.
After w' put w! and finish the ordering arbitrarily.

-3-

m! : First choice w! , followed by w. and the original preferences

of m. below w. . Finish arbitrarily.
11

w. : In the original preference ordering replace m. by (m!,m.) for

i=i and all m. above m.. For m. below m. use (m.,m!). Example: if
J 3 i j i 3 3

the original ordering for w is (best) m-num. new ordering is mjm. mlnum.m' .

w! : First choice is m. , . Second choice is m . , followed by m ! .
i l-l i i

Finish arbitrarily.

In this definition all arithmetic is modulo n. We illustrate with
an example after the proof.

Proof: We begin by observing that in any stable 2n-couple matching
with these preferences (1) If for some i, m. gets w' then w! (pre-
ferred by m.) must get m ., hence m. must get w' for all i. (2) w!
is the first choice of m! , hence w' must get either m._1 (and 1 applies),
or m. , or m ' . (3) m. must get somebody at least as good as w!... (4) If
m. does not get w' or w^+1» then m! gets w! . (5) If m. prefers w. to w',
m! does not get w.. (Since x is stable w. prefers m. to ml. If m! got w
(4) would imply m. gets w* or w' . so m. and w. would be happier to-
gether.)

These observations imply that nobody gets assigned to the arbitrary
part of his or her ordering. Further if we are given a stable matching
for the 2n couples we obtain a stable matching for the n-couple problem
(i.e., a member of L) by giving each w. her partner in the 2n-couple
problem, deleting primes where necessary. Conversely if y € L, there is
a corresponding stable matching for the 2n-couple situation in which m.
is replaced by m! iff m. gets w or somebody worse in y. If y <_ x there
are two 2n-couple matches corresponding to y — one in which each m. gets

-4-

w' and one in which each m. gets w! ... Those matches in which each m.
gets w! corresponds to V in the definition of L . Q.E.D.

Example: The four people with preferences given below have stable
matching corresponding to a four-element lattice: (A) m. gets w , m„ gets
w , m3 gets w3, m^ gets w4 (abbreviated (2134)) (B) (1243) (C) (1234)
(D) (2143).

"l m2 m3 m4 Wl W2 W3 W4

W2 Wl W3 W4 ml m2 m4 m3

Wl W2 W4 W3 m2 "l m3 m4

(. .. = arbitrary)

f 1 0 *3/ ^

L is a six-element lattice generated by the preferences:

,i ,,i ,,t „t

*\ m2 m3 m4 "£ m2 "S m4 wl w2 w3 w4 wl w2 W3 w4

W2 Wl W3 W4 Wl W2 W3 W4 ml m2 ml m3 m4 "H m2 m3

w' w' w! w' w w„ w_ w, m. m- m, m_ m. m„ m_ m,

w' wl w, w_ m_ nL m' mf mj ml m' m!

e • © f f

m- m- m« m,
• • •

The stable matchings are (213'4'1,2,34) , (1'2'3'4'1234) , (1,2,3'4'1243) ,
(2i3'4«i«2'43), (2'3,4'1'1234), and (2?3'4'1'1243) . The last two are
members of V.

The construction we have given does not use the smallest number of
people needed to represent a given lattice. The six-element lattice can
be represented using ten people as follows

^ m2 m3 m4 m5 w± w2 w3 w4 w,.

w w„ w_ w, w,. m„ m_ m. m,. m,

w_ w_ w_ w. w

3 W3 W2 W5 W4 "l m2 m2 m4 m5

Wl m3

-5-

The stable matches are (12345), (12354), (13245), (13254), (31245),
and (31254). However, it is not possible in general to go from L to L
by adding only one additional couple.

The structure of the set of matches is clearly reminiscent of the
representation of a permutation by cycles. This theme will be explored
in forthcoming work with Alvin Roth, whose recent work [3] motivated
this note.

-6-

References

1. Do Gale and L. Shapley, "College Admissions and the Stability of
Marriage," American Math Monthly 69 (1962), pp. 9-15.

2. D. Knuth, Marriage Stables, Montreal University Press 1976.

3. A. Roth, "The Economics of Matching: Stability and Incentives,"
to appear in Mathematics of Operations Research.

M/C/294

IECKMAN

t|NDERV INC.

JUN95