Explorations in the Realm of the Gale-Shapley Model for Two-Sided Markets

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk

In 1962 the mathematicians David Gale and Lloyd Shapley published an important paper that dealt with the pairing of the members of two equal sized non-overlapping groups with each other in a "stable" manner. The two groups, the opposite sides of the two-sided market, are often described as men and women and the pairings are often referred to as "marriages." The men "rank" the women without ties and the women rank the men without ties. A pairing of the men and women (n "marriages") is called stable if there is no pair consisting of a man M and woman W and either of them, say, W by way of example, who would rather be married to some other man M* than M, and M* would prefer W to the woman he was originally assigned. Such a stable pairing is often referred to as a stable matching. Using an algorithm (procedure) now referred to as the deferred acceptance algorithm, Gale and Shapley showed that such stable matchings always exist, and they showed how to find two special stable matchings (which sometimes collapse to one stable matching) known as the male optimal and female optimal matchings. There are many ways to generalize the basic framework considered below: allow ties in preferences, allow men or women to prefer to remain unmatched rather than accept some particular mates, to allow different sizes between the sets of men and women, to have several men assigned to some women, etc. All of these are interesting both from a theoretical point of view and often from an applied point of view.

My purpose here is to indicate a small collection of problems, many of which have known solutions, as a way to show how one can have the experience of trying to move beyond working on "exercises" about a mathematical topic to get a feel for what doing "mathematical research" entails. I take for granted that the reader has been exposed to the basic ideas about the Gale-Shapley Marriage Model beyond the very basics given above.

To establish a foundation for what follows here are some basic notations and review of the ideas.

How does one indicate the preferences that the men have for the women and vice-versa? Look at Figure 1.

Figure 1

This notation is quite suggestive that man 1 likes woman 1 best, woman 3 second best, and woman 2 least well. However, it takes a lot of room to write down and is hard to type set. There are also other systems of providing this information. So what is much more common is that the information would be written this way:

Note this is an abbreviated version of the more suggestive:

In Figure 2 we have suppressed the fact then men rank women by dropping the w's from the notation that appear in Figure 3. Often one merely uses some kind of table where the rows correspond to the men, say, and to save space the information in Figure 2 would appear:

1. 1, 3, 2.

Now, we can write down a typical way (using the more detailed notation) for 4 women to rank 4 men:

and 4 men to rank four women:

Taken together, Figures 4 and 5 constitute an "instance" of a size 4, an n = 4, of the Gale-Shaplely Stable Marriage Problem.

Question 1

a. How many different tables (of the kind in Figure 4) where n women rank n men are there?
b. How many different tables (of the kind in Figure 5) where n men rank n women are there?

c. If a problem instance of size n consists of a pair of tables of order n where n men rank n women and n women rank n men, how many problem instances are there of order n?

Comment:

What makes two different tables different? One approach is to say that tables with different entries in the i, j (ith row, jth column) are different. However, one could say that tables or instances that arise from merely changing the names of the men (or women) or interchanging the roles of men and women are not different. You can consider a variety of different counting problems in this framework.

When each woman is paired with some man it gives rise to a matching M, a collection of n "marriages.". Some matchings may be stable and some may not be stable. Gale and Shapley's work shows that there is always some stable matching, and "typically" there are two, one that favors the men and one that favors the women (but sometimes these two matchings "coincide").

Given a man/woman pair m, w is said to block a matching M if m and w are NOT paired in M and prefer each other more than the people they are assigned as partners (mates) in M. When M has a blocking pair it cannot be a stable matching.

Question 2

a. What is the largest number of different stable matchings that one can have for an instance where n men and n women are involved?

b. Can you find tables which for every n give rise to exactly one stable matching?

c. Can you find tables which for every n give rise to exactly two stable matchings?

d. For a given n, let Max(n) denote the maximum number of different stable matchings which can arise for some instance of size n. Study the behavior of which values of r are possible for the number of stable matchings as r ranges from 1 to Max(n) as one changes the instance of the matching problem.

Question 3

a. For a fixed matching with n men and women, what is the largest number of blocking pairs which is possible for this matching?

b. Which tables of preferences for men and women give rise to the largest number of blocking pairs, summed over all possible ways to pair the men and women?

Question 4

Assume there are more than two stable matchings that occur for a given instance of a marriage problem of size n.

a. How might one pick out a stable matching which is in the "middle" with respect to the male optimal and female optimal matchings?

b. Consider different approaches to finding a "fair" stable matching which takes the interests of both the men and women into account.

Question 5

Investigate the consequences of some man (or group of men), with similar issues for women, not being honest in putting forth their preferences. For example, suppose a single woman got a copy of the preferences of i. one particular man ii. all of the men. iii. all other women. How might she take advantage of this particular information?

Question 6

Given a set of preference tables if a man-woman pair m,w is not in any stable marriage, how few changes to the table would make it possible for m and n to be paired in some stable marriage?

Question 7

How large a change in the number of stable marriages can occur by changing the preference of a particular man (or woman) for a pair of women (men)? For example, one might pick row of man i in Table 4 and interchange the entries in two adjacent columns, or interchange the entry in the first column and last column.

Question 8

What does reversing a single man's preferences do to the number of stable marriages and how happy a typical man is with the woman he is paired with in a particular stable marriage? What happens when one reverses the preferences of all men? of all men and all women? (Reversing here means that if a woman ranked a man first, now she would rank him last, and so on.)

Question 9

Study what happens when one starts with a random assignment of men to women. What is the expected number (average) of stable marriages? If one takes such an assignment and it is not stable, can one get to a stable marriage by "resolving" a sequence of blocking pairs? Here "resolving" means that one assigns to each other the members of a blocking pair (assigning their discarded mates to each other) and hopes one has gotten a stable pairing or "closer" to a stable pairing.

Question 10

In his famous work on voting based on ranked ballots Kenneth Arrow developed axioms that a "fair" voting system should obey. Find interpretations for the analogs of these axioms in the Gale-Shapley context.

References:

D. Gale and L. S. Shapley, College Admissions and the Stability of Marriage, American Mathematical Monthly 69 (1962) 9-14.

Gusfield, Dan, and Robert W. Irving. The stable marriage problem: structure and algorithms, MIT press, Cambridge, 1989.

Roth, A. E., and Sotomayor, M. A. O., Two-sided matching: A study in game-theoretic modeling and analysis, Cambridge University Press, NY, 1990.

Taylor, Alan, Social Choice and the Mathematics of Manipulation, Cambridge U. Press, New York, 2005.