MIT LCS TR 913

MIT-LCS-TR-913 MIT-LCS-TR-913

User Manual: MIT-LCS-TR-913

Open the PDF directly: View PDF .
Page Count: 12

Marriage, Honesty, and Stability

Nicole Immorlica∗Mohammad Mahdian∗

Abstract

Many centralized two-sided markets form a matching between par-

ticipants by running a stable marriage algorithm. It is a well-known

fact that no matching mechanism based on a stable marriage algo-

rithm can guarantee truthfulness as a dominant strategy for partic-

ipants. However, as we will show in this paper, in a probabilistic

setting where the preference lists of one side of the market are com-

posed of only a constant (independent of the the size of the market)

number of entries, each drawn from an arbitrary distribution, the

number of participants that have more than one stable partner is van-

ishingly small. This proves (and generalizes) a conjecture of Roth

and Peranson [23]. As a corollary of this result, we show that, with

high probability, the truthful strategy is the best response for a given

player when the other players are truthful. We also analyze equilib-

ria of the deferred acceptance stable marriage game. We show that

the game with complete information has an equilibrium in which a

(1−o(1)) fraction of the strategies are truthful in expectation. In the

more realistic setting of a game of incomplete information, we will

show that the set of truthful strategies form a (1+o(1))-approximate

Bayesian-Nash equilibrium. Our results have implications in many

practical settings and were inspired by the work of Roth and Peran-

son [23] on the National Residency Matching Program.

1 Introduction

Suppose all the eligible bachelors and bachelorettes in a town

confide in the town’s matchmaker their ideal spouses. Each

man submits an ordered preference list of the women he

would like to marry. Similarly, each woman submits an

ordered preference list of the men she would like to marry.

The matchmaker must arrange marriages such that no one is

tempted to ask for a divorce. In particular, the matchmaker

must be sure that there is no pair of young lovers who prefer

each other to their assigned spouses. Such a set of marriages

is called stable, and finding a set of stable marriages is known

as the stable marriage problem. Gale and Shapley [6] showed

that the stable marriage problem always has a solution and

developed an algorithm to find it. Since the seminal work

of Gale and Shapley, there has been a significant amount of

work on the mathematical structure of stable marriages and

related algorithmic questions. See, for example, the book by

Knuth [10], the book by Gusfield and Irving [8], or the book

by Roth and Sotomayoror [24].

The stable marriage problem has many promising appli-

cations in two-sided markets such as job markets [19], college

∗Computer Science and Artificial Intelligence Lab, MIT, Cambridge, MA

02139. Email: {nickle,mahdian}@theory.lcs.mit.edu.

admissions [19], sorority and fraternity rush [14], and assign-

ment of graduating rabbis to their first congregation [3]. Since

most applications of the stable marriage algorithm involve the

participation of independent agents, it is natural to investigate

how we should expect these agents to behave. In particular,

we would like to know whether agents can benefit by being

dishonest about their preference lists. Ideally, in economic

settings such as job markets, we would like to design mech-

anisms in which truth-telling is a dominant strategy, i.e., it is

in the best interest of each individual agent to tell the truth,

no matter what other agents do. We call such a mechanism a

truthful mechanism. Truthful mechanisms have received sig-

nificant attention in the computer science community (see, for

example, [1, 5, 15]). Unfortunately, as shown by Roth [20],

there is no mechanism for the stable marriage problem in

which truth-telling is a dominant strategy for both men and

women. See the book by Roth and Sotomayor [24] for a dis-

cussion about this problem and other problems related to the

economic aspects of the stable marriage problem.

Nonetheless, stable matching algorithms have had spec-

tacular success in practical applications. One particular job

market — the medical residency market — has been using a

centralized stable marriage market system called the National

Residency Matching Program (NRMP) since the 1950s [21].

To this day, most medical residences are formed through an

updated version of this centralized market system redesigned

in 1998 by Roth [22]. It seems surprising that an algorithm

like the one used by the NRMP which provably admits strate-

gic behavior can be so successful. Roth and Peranson [23]

noted that, in practice, very few students and hospitals could

have benefited by submitting false preferences. For exam-

ple, in 1996, out of 24,749 applicants, just 21 could have

affected their match by submitting false preferences (assum-

ing, of course, that no one lied in 1996). Roth and Peran-

son [23] conjectured that the main reason for this peculiarity

is the sheer size of the job market. In a small town, every

man knows every woman, but in the medical market, a stu-

dent can not possibly interview at every hospital. In practice,

the length of applicant preference lists is quite small, about

15, while the number of positions is large, about 20,000. Ex-

perimentally, Roth and Peranson [23] showed that in a model

where random preference lists of limited length are generated

for participants, the number of participants who have more

than one stable partner (and therefore the number of those

who can benefit by lying) is small. They conjectured that in

this probabilistic setting, the fraction of such people tends to

zero as the size of the market tends to infinity.

In this paper, we prove a statement that proves and

generalizes this conjecture. More precisely, we prove the

following: Assume there are nmen and nwomen in the

town, and each woman has an arbitrary ordering of all men as

her preference list. Each man independently picks a random

preference list of a constant (i.e., independent of n) number of

women, each according to an arbitrary distribution D. These

are the true preference lists. We show that in this setting the

expected number of people with more than one stable spouse

is vanishingly small. This result has a number of interesting

economic implications. We can interpret the preference lists

together with a stable marriage algorithm as a game G, in

which everybody submits a preference list (not necessarily

their true preference list) to the algorithm and receives a

spouse. The goal for each player is to receive the best spouse

possible according to their true preference list. First, we show

that, with probability 1−o(1) (as napproaches infinity),

in any stable marriage mechanism, the truthful strategy is

the best response for a given player when the other players

are truthful. We also show that when a deferred acceptance

mechanism is used, there is an equilibrium of this game in

which a majority of the players are truthful. Finally, we prove

that in the more realistic setting of a game of incomplete

information (where each player only knows the distribution

of the preference lists), the set of truthful strategies in the

game induced by the women-proposing mechanism form a

(1 + o(1))-approximate Bayesian-Nash equilibrium. It is

important to note that our results hold for any distribution

Dof women. For the special case of uniform distributions

(which includes the conjecture of Roth and Peranson), the

o(1) in the above bounds is roughly ek/n, and thus the bounds

converge quite quickly.

We use the following technique for our proof: First,

we design an algorithm, based on an algorithm of Knuth et

al. [11, 12], that for a given woman checks whether she has

more than one stable husband in one run of proposals. Using

this algorithm, we prove a relationship between the probabil-

ity that a given woman has more than one stable husband and

the number of single women who are more popular than she.

This relationship, essential to our main result, seems difficult

to derive directly, without going through the algorithm. Given

this relationship, we are able to derive our result by comput-

ing bounds on the expectation and variance of the number of

single popular women.

Related work. This paper is motivated by experimen-

tal results and a conjecture in the paper by Roth and Per-

anson [23]. Sethuraman et al. [25, 26] have studied the

stable matching game when participants are required to an-

nounce complete preference lists, and have given an optimal

cheating algorithm and several experimental results regard-

ing the chances that an agent can benefit by lying in this

game. One can also view our results as an analysis of sta-

ble matching with random preferences. There has been a

considerable amount of work on this area, mostly assuming

complete preference lists for participants, and none motivated

by the economic aspects of the problem. See, for example,

[11, 12, 18, 17]. We will use some of the techniques devel-

oped in these papers in our analysis.

Mechanisms that are truthful in a randomized sense (i.e.,

in expectation, or with high probability) have been a subject

of research in theoretical computer science [1, 2]. These

mechanisms seeks to encourage truthfulness by introducing

randomization into the mechanism. Our results are of a

different flavor. We show that one can conclude statements

regarding truthfulness by introducing randomization into the

players utility functions. To the best of our knowledge, our

result is the first result of this type.

Structure of the paper. The rest of the paper is orga-

nized as follows. In Section 2, we define the stable marriage

problem and discuss the relevant known results from the lit-

erature. In Section 3, we formalize our probabilistic setting

and summarize our results. In Section 4, we prove our main

technical result, the experimental conjecture of Roth and Per-

anson [23]. In Section 6, we strengthen our technical result

for the special case of uniformly distributed preference lists.

Finally, in Section 7, we conclude with interesting open ques-

tions concerning stable marriage algorithms and two-sided

markets.

2 Stable marriage preliminaries

Consider a community consisting of a set Wof nwomen and

a set Mof nmen. Each person in this community has a

preference list, which is a strictly ordered list of a subset of

the members of the opposite sex. A matching is a mapping µ

from M∪Wto M∪Win such a way that for every x∈M,

µ(x)∈W∪ {x}and for every x∈W,µ(x)∈M∪ {x},

and also for every x, y ∈M∪W,x=µ(y)if and only if

y=µ(x). If for some m∈Mand w∈W,µ(m) = w,

we say that wis the wife of mand mis the husband of w

in µ; or, if for some x∈M∪W,µ(x) = x, we say that

xremains single in µ. A pair m∈M,w∈Wis called a

blocking pair for a matching µ, if mprefers wto µ(m), and

wprefers mto µ(w). A matching with no blocking pair is

called a stable matching. If a man mand a woman ware a

couple in some stable matching µ, we say that mis a stable

husband of w, and wis a stable wife of m. Naturally, each

person might have more than one stable partner. In the stable

marriage problem, the objective is to find a stable matching

given the preference lists of all men and women.

The stable marriage problem was first introduced and

studied by Gale and Shapley [6] in 1962. They proved that a

stable matching always exists, and a simple algorithm called

the deferred acceptance procedure can find such a matching.

This procedure iteratively selects an unmarried man mand

creates a proposal from him to the next woman on his list.

If this woman prefers mto her current assignment, then she

tentatively accepts m’s proposal, and rejects the man she

was previously matched to (if any); otherwise, she rejects

the proposal of m. The algorithm ends when every man

either finds a wife that accepts him, or gets rejected by all

the women on his list, in which case he remains single. This

algorithm is sometimes called the men-proposing algorithm.

Similarly, one can define the women-proposing algorithm.

Gale and Shapley [6] proved the following.

THEOREM A. The men-proposing algorithm always finds a

stable matching µ. Furthermore, this stable matching is men-

optimal, i.e., for every man mand every stable wife wof m

other than µ(m),mprefers µ(m)to w. At the same time, µ

is the worst possible stable matching for women, i.e., for any

woman wand any stable husband mof wother than µ(w),

wprefers mto µ(w).

The men-optimal stable matching is unique, and so the

above theorem implies that the order of proposals does not

affect the output of the men-proposing algorithm.

THEOREM B. The men-proposing algorithm always finds the

same stable matching, independent of the order in which the

proposals are made.

We will also need the following theorem of Roth [21]

and McVitie and Wilson [13], which says that the choice of

the stable matching algorithm does not affect the number of

people who remain unmarried at the end of the algorithm.

THEOREM C. In all stable matchings, the set of people who

remain single is the same.

A stable matching mechanism is an algorithm that elicits

a preference list from each participant, and outputs a match-

ing that is stable with respect to the announced preferences.

We say that truthfulness is a dominant strategy for a partic-

ipant aif, no matter what strategy other participants use, a

cannot benefit (i.e., improve his or her match according to

his or her true preferences) by submitting a list other than

his or her true preference list. Ideally, we would like to de-

sign mechanisms in which truthfulness is a dominant strategy

for all participants. However, Roth [20] proved that there is

no such mechanism for the stable marriage problem. On the

positive side, the following theorem (due to Roth [20] and

Dubins and Freedman [4]) shows that in deferred acceptance

mechanisms, truthfulness is a dominant strategy for half the

population.

THEOREM D. In the men-optimal stable marriage mecha-

nism, truth-telling is a dominant strategy for men. Similarly,

in the women-optimal mechanism, truth-telling is a dominant

strategy for women.

3 Our results

Consider a situation where there are nmen and nwomen.

Assume the preference list of each man is chosen indepen-

dently and uniformly at random from the set of all ordered

lists of kwomen, and the preference list of each woman is

picked independently and uniformly at random from the set

of all orderings of all men. We are concerned about bounding

the expected number of people who might be tempted to lie to

the mechanism about their preferences when the other play-

ers are truthful. As we will show, only people who have more

than one stable partner might be able to influence their final

match by altering their preference lists. Therefore, we focus

on bounding the expected number of women with more than

one stable husband in this model. Notice that this number

is equal to the expected number of men with more than one

stable wife, since the number of single and uniquely matched

men must equal the number of single and uniquely matched

women. Roth and Peranson [23] conjectured the following.

CONJECTURE 1. Let ck(n)denote the expected number of

women who have more than one stable husband in the above

model. Then for all fixed k,

lim

n→∞

ck(n)

n= 0.

We prove this conjecture in this paper. In fact, we will prove

the following stronger result. Let Dbe an arbitrary fixed

distribution over the set of women such that the probability

of each woman in Dis nonzero.1Intuitively, having a

high probability in Dindicates that a woman is popular.

The preference lists are constructed by picking each entry

of the list according to D, and removing the repetitions.

More precisely, we construct a random list (l1, . . . , lk)of k

women as follows. At step i, repeatedly select women w

independently according to Duntil w6∈ {l1, . . . , li−1}and

then set li=w. Let Dkbe the distribution over lists of size

kproduced by this process.2Notice that if Dis the uniform

distribution, Dkis nothing but the uniform distribution over

the set of all lists of size kof women. Therefore, the model

of Roth and Peranson [23] is a special case of our model. We

also generalize their result in another respect: we assume that

women have arbitrary complete preference lists, as opposed

to the assumption in [23] that they have random complete

preference lists. Our main result is the following theorem.

THEOREM 3.1. Consider a situation where each woman has

an arbitrary complete preference list, and each man has a

preference list chosen independently at random according to

Dk. Then, for all fixed k,

lim

n→∞

ck(n)

n= 0.

Even though we state and prove our results assuming that

all preference lists are of size exactly k, it is straightforward

to see that our proof carries over to the case where preference

lists are of size at most k. For uniform distributions, we can

prove a strong result on the rate of convergence of this limit.

1This assumption is needed to make sure that the problem is well-defined.

2See the conclusion for a discussion of why this is the most general setting

in which we can hope to get a positive result.

3

THEOREM 3.2. Consider a situation where each woman has

an arbitrary complete preference list, and each man has a

preference list of kwomen chosen uniformly and indepen-

dently. Then, the expected number of women who have more

than one stable husband is bounded by ek+1 +k2, a constant

that only depends on k(and not on n).

There are a number of interesting economic implications

of this theorem. Our first result states that, with high proba-

bility, a given player’s best strategy is truth-telling when the

other players are truthful. Thus, a dishonest player who be-

lieves in the honesty of the other players has an economic

incentive to be honest. This is similar (but not identical) to

the notion of ex post Nash equilibria.

COROLLARY 3.1. Fix any stable matching mechanism, and

consider an instance with nwomen with arbitrary complete

preference lists and nmen with preference lists drawn from

Dk(as in Theorem 3.1). Then, for any given person x, the

probability (over the men’s preference lists) that for x, the

truthful strategy is not the best response in a situation where

the other players are truthful is o(1) (at most O(ek/n)for

uniform distributions).

The previous corollary states that a player can benefit

by lying only with a vanishingly small probability when the

other players are truthful. Now we turn to the situation

in which the other players are not necessarily truthful, but

are playing an equilibrium strategy of the game induced by

the stable matching mechanism. There are two ways to

interpret our stable marriage setting as a game. One way

is to consider it as a game of complete information: Let

Pmand Pwdenote the preference lists of men and women.

Knowing these preferences, each player chooses a strategy

from the strategy space of all possible preference lists. The

corresponding preference lists are submitted to a fixed stable

marriage algorithm and a matching is returned. A player’s

goal is to choose the strategy that gets him/her a spouse

as high on his/her preference list as possible. Let GPm,Pw

denote this game. An equilibrium of a game is a set of

strategies, one for each player, such that no single player

can improve his/her situation by deviating from his or her

equilibrium strategy [16].

COROLLARY 3.2. Assume the preference lists Pwof women

are arbitrary, and the preference lists Pmof men are drawn

from Dk(as in Theorem 3.1). The game GPm,Pwinduced

by these preferences and the men-proposing (or women-

proposing) mechanism has an equilibrium in which, in ex-

pectation, a (1 −o(1)) fraction of strategies are truthful.

In the above setting, we assume that each player knows

the preference lists of the other players when he/she is select-

ing a strategy, i.e., we have a game of complete information.

A more realistic assumption is that each player only knows

the distribution of preference lists of the other players. Each

player’s goal is to alter his/her preference list and announce it

to the mechanism in a way that the expected rank of his/her

assigned spouse is as high as possible. A strategy for a player

is a function that outputs an announced preference list for any

input preference list. Hence the truthful strategy is the identity

function. We wish to analyze the Bayesian-Nash equilibria in

this incomplete information game. A (1 + ε)-approximate

Bayesian-Nash equilibrium for this game is a collection of

strategies, one for each player, such that no single player can

improve his/her situation by more than a multiplicative factor

of 1 + εby deviating from his/her equilibrium strategy.

COROLLARY 3.3. Consider the game described above with

the women-optimal mechanism. Then for every ε > 0, if n

is large enough, the above game has a (1 + ε)-approximate

Nash equilibrium in which everybody is truthful.

The proofs of these corollaries are presented in Section 5.

4 Proof of Theorem 3.1

In this section, we will prove our main technical result,

Theorem 3.1. The proof consists of three main components.

First, we present an algorithm that, given the preference lists,

counts the number of stable husbands of a given woman

(Section 4.1). We would like to analyze the probability

that the output of this algorithm is more than one, over

a distribution of inputs. In Section 4.2, we bound this

probability assuming a lemma concerning the number of

singles in a stable marriage. This lemma is proved in

Section 4.3 by bounding the expectation of the number of

singles and proving that it is concentrated around its expected

value using the Chebyschev inequality.

4.1 Counting the number of stable husbands The sim-

plest way to check whether a woman ghas more than one

stable husband or not is to compute the men-optimal and the

women-optimal stable matchings using the algorithm of Gale

and Shapley (See Theorem A) and then check if ghas the

same husband in both these matchings. However, analyzing

the probability that ghas more than one stable husband us-

ing this algorithm is not easy, since we will not be able to

use the principle of deferred decisions (as described later in

Section 4.2). In this section we present a different algorithm

that outputs all stable husbands of a given woman in an ar-

bitrary stable marriage problem in one run of a men-propose

algorithm. This algorithm is a generalization of the algorithm

of Knuth et al. [11, 12] to the case of incomplete preference

lists.Suppose we want the stable husbands of woman g.

Initially all the people are unmarried (the matching is empty).

The algorithm closely follows the man-proposing algorithm

for finding a stable matching. However, g’s objective is

to explore all her options, therefore, every time the men-

proposing algorithm finds a stable marriage, gdivorces her

husband and lets the algorithm continue.

ALGORITHM 4.1.

1. Initialization: Run the man-proposing algorithm to find

the men-optimal stable matching. If gis unmarried,

output ∅.

2. Selection of the suitor: Output the husband mof gas one

of her stable husbands. Remove the pair (m, g)from the

matching (woman gand man mare now unmarried) and

set b=m. (the variable bis the current proposing man.)

3. Selection of the courted: If bhas already proposed to all

the women on his preference list, terminate. Otherwise,

let wbe his favorite woman among those he hasn’t

proposed to yet.

4. The courtship:

(a) If whas received a proposal from a man she

likes better than b, she rejects band the algorithm

continues at the third step.

(b) If not, waccepts b. If w=g, the algorithm

continues at the second step. Otherwise, if wwas

previously married, her previous husband becomes

the suitor band the algorithm continues at the third

step. If wwas previously unmarried, terminate the

algorithm.

Notice that in step 4(a) of the algorithm, wcompares b

to the best man who has proposed to her so far, and not to the

man she is currently matched to. Therefore, after gdivorces

one of her stable husbands, she has a higher standard, and will

not accept any man worse than the man she has divorced. For

w6=g, step 4(a) is equivalent to comparing bto the man wis

matched to at the moment.

We must prove that this algorithm outputs all stable

husbands of g. In fact, we will prove something slightly

stronger.

THEOREM 4.1. Algorithm 4.1 outputs all stable husbands of

gin order of her preference from her worst stable husband to

her best stable husband.

Proof. We prove the theorem by induction. As the man-

proposing algorithm returns the worst possible matching for

the women (by Theorem A), the first output is g’s worst stable

husband. Now suppose the i’th output is g’s i’th worst stable

husband mi. Consider running the man-proposing algorithm

with g’s preference list truncated just before man mi. As the

order of proposals do not affect the outcome (Theorem B), let

the order of proposals be the same as Algorithm 4.1. Then,

up until Algorithm 4.1 outputs the i+ 1’st output mi+1, its

tentative matching during the j’th proposal is the same as the

tentative matching of the man-proposing algorithm during the

j’th proposal (except, possibly, woman gis matched in Al-

gorithm 4.1 and unmatched in the man-proposing algorithm).

Now since mi+1 was accepted, the fourth step guarantees that

gpreferred mi+1 to mi. Thus mi+1 is on g’s truncated prefer-

ence list, and so the tentative matchings of the two algorithms

are the same. Furthermore, mi+1 is the first proposal ghas ac-

cepted in the man-proposing algorithm. All other women who

get married in the set of stable matchings already have hus-

bands since they have husbands in Algorithm 4.1, and so the

man-proposing algorithm terminates with the current match-

ing. Thus, mi+1 is the worst possible stable husband for g

which is better than mi.

4.2 Analyzing the expectation We are interested in the ex-

pected number of women with more than one stable husband,

or, equivalently, the probability that a fixed woman ghas more

than one stable husband. We can compute this probability by

analyzing the output of Algorithm 4.1 on male preference lists

drawn from the distribution Dk. We simulate this experiment

using the principle of deferred decisions: a man only needs

to determine his i’th favorite woman when he makes his i’th

proposal. If we make these deferred decisions independently

according to D, then the distribution of the output of this new

algorithm over its coin flips will be exactly the same as the

distribution of the output of the old algorithm over its input.

This motivates the definition of the following algorithm. At

any point in this algorithm, the variable Aidenotes the set of

women that man ihas proposed to so far. Men and women

are indexed by numbers between 1 and n.

ALGORITHM 4.2.

1. Initialization: Let l= 1,∀1≤i≤n, Ai=∅,

xg= 0. (The matching is empty and no men have made

any proposals).

2. Selection of the suitor:

(a) If l≤n, let bbe the l’th man and increase lby one.

(b) Otherwise, we have found a stable matching. If

gis single in this stable matching, then terminate.

Otherwise, increment xg, remove the pair (m, g)

from the matching (man mand woman gwho

were previously married to each other are now

unmarried) and set b=m.

3. Selection of the courted:

(a) If |Ab| ≥ k, then do the following:

– If xg≥1, then terminate. Otherwise, return

to step two.

(b) Repeatedly select wrandomly according to distri-

bution Dfrom the set of all women until w6∈ Ab.

Add wto Ab.

4. The courtship:

(a) If whas received a proposal from a man she

likes better than b, she rejects band the algorithm

continues at step 3.

5

(b) If not, waccepts b. If wwas previously married,

her previous husband becomes the suitor band

the algorithm continues at the third step. If w

was previously single and xg= 0, the algorithm

continues at the second step. If wwas previously

single and xg≥1, the algorithm continues at the

second step if w=gand terminates if w6=g.

Before giving a proof of Theorem 3.1, we introduce a few

notations. For every woman i, let pidenote the probability of

iin the distribution D. We say that a woman iis more popular

than another woman j, if pi≥pj. Assume, without loss of

generality, that women are ordered in the decreasing order of

popularity, i.e., p1≥p2≥ ··· ≥ pn.

Proof of Theorem 3.1. Recall that ck(n)is the ex-

pected number of women with more than one stable hus-

band. We show that for every  > 0, if nis large

enough, then ck(n)/n ≤. By linearity of expectation,

ck(n) = Pg∈WPr[ghas more than one stable husband].

Fix a woman g∈W. We want to bound the probability that

ghas more than one stable husband. By Theorem 4.1 and the

principle of deferred decisions, this is the same as bounding

the probability that the random variable xgin Algorithm 4.2

is more than one.

We divide the execution of Algorithm 4.2 into two

phases: the first phase is from the beginning of the algorithm

until it finds the first stable matching, and the second phase is

from that point until the algorithm terminates. Assume at the

end of the first phase, Algorithm 4.2 has found the first stable

matching µ. We bound the probability that xg>1condi-

tioned on the event that µis the matching found at the end of

the first phase (we denote this by Pr[xg>1|µ]), and then

take the expectation of this bound over µ.

Let the set Sµ(g)denote the set of women more popular

than gthat remain single in the stable matching µand

Xµ(g) = |Sµ(g)|. If gis single in µ, then xg= 0

and therefore Pr[xg>1|µ] = 0. Otherwise, xg>

1if only if woman gaccepts another proposal before the

algorithm terminates. We bound this by the probability that

greceives another proposal before the end of the algorithm.

The algorithm may terminate in several ways, but we will

concentrate on the termination condition in step 4(b), i.e.,

that some man proposes to a previously single woman. Thus,

we are interested in the probability that in the second phase

of Algorithm 4.2 some man proposes to a previously single

woman before any man proposes to g.

Note that at the end of the first phase of the algorithm,

all Ai’s are disjoint from Sµ(g), since women have complete

preference lists. Thus whenever the random oracle in step

3(b) outputs a woman from set Sµ(g), the algorithm will

advance to step 4(b) and terminate. Thus, the probability

Pr[xg>1|µ]is less than or equal to the probability that

in a sequence whose elements are independently picked from

the distribution D,gappears before any woman in Sµ(g).

By the definition of Sµ(g), for every w∈Sµ(g), every time

we pick a woman randomly according to D, the probability

that wis picked is at least as large as the probability that g

is picked. Therefore, the probability that gappears before all

elements of Sµ(g)in a sequence whose elements are picked

according to Dis at most the probability the gappears first in

a random permutation on the elements of {g}∪Sµ(g), which

is 1/(Xµ(g) + 1). Thus, for every µ,

Pr[xg>1|µ]≤1

Xµ(g)+1

(4.1)

Thus,

Pr[xg>1] = EµhPr[xg>1|µ]i

≤Eµ1

Xµ(g)+1.(4.2)

We complete the proof assuming the following lemma,

whose proof is given in Section 4.3.

LEMMA 4.1. For every g > 4k,

E[1/(Xµ(g) + 1)] ≤12e8nk/g

g.

Thus, using Equation (4.2) and Lemma 4.1 for g≥16nk

ln(n),

and Pr[xg>1] ≤1for smaller g’s, we obtain

ck(n)≤16nk

ln(n)+

n

X

g=16nk

ln(n)

12e8nk/g

g

≤16nk

ln(n)+

n

X

g=16nk

ln(n)

3 ln(n)eln(n)/2

4nk

≤16nk

ln(n)+ 3√nln(n)/(4k) = o(n),

and so for every constant k, the fraction of women with more

than one stable husband, ck(n)/n, goes to zero as ntends to

infinity. 

For the case of uniform distributions, it is possible to

modify the above proof to get a much tighter bound of O(e8k)

on the expected number of women with more than one stable

husband. We derive an even tighter bound in this case, as

stated in Theorem 3.2, using a slightly different technique.

This bound is proved in Section 6.

4.3 Number of singles In this section we prove

Lemma 4.1. This completes the proof of Theorem 3.1.

We start with the following simple fact: the probability that

a woman wremains single is greater than or equal to the

probability that wdoes not appear on the preference list

of any man. More precisely, let Ewdenote the event that

the woman wdoes not appear on the preference list of any

man when these preferences are drawn from Dk. Let Yg

denote the number of women w≤gfor which the event Ew

happens. Then we have the following lemma.

LEMMA 4.2. For every g, we always have Xµ(g)≥Yg.3

Proof. Every woman w < g for which Ewhappens is a

woman who is at least as popular as gand will remain

unmarried in any stable matching. 

We now bound the expectation of 1/(Yg+ 1) in a

sequence of two lemmas. In Lemma 4.3 we bound the

expectation of Yg. Then, in Lemma 4.4 we show the variance

of Ygis small and therefore it does not deviate far from its

mean.

LEMMA 4.3. For g > 4k, the expected number E[Xµ(g)]

of single women more popular than woman gis at least

g

2e−8nk/g .

Proof. Let Q=Pk

j=1 pjdenote the total probability of the

first kwomen under D. The probability that a man mdoes

not list a woman was his i’th preference given that he picks

w1, . . . , wi−1as his first i−1women, is equal to

1−pw

1−Pi−1

j=1 pwj≥1−pw

1−Q.

Thus the probability that mdoes not list wat all is at least

(1 −pw

1−Q)k, and so the probability that woman wis not listed

by any man is at least (1 −pw

1−Q)nk. If w > k, there are at

least w−kwomen who are at least as popular as w, but not

among the kmost popular women. Therefore, pw≤1−Q

w−k.

By these two inequalities, for every w > 2kwe have

Pr[Ew]≥(1 −1

w−k)nk ≥e−2nk/(w−k)≥e−4nk/w

Therefore, for every g > 4k, the expectation of Ygis at least

E[Yg] =

g

X

w=1

Pr[Ew]≥

g

X

j=2k

e−4nk/j

≥

g

X

j=g/2

e−8nk/g =g

2e−8nk/g .



LEMMA 4.4. The variance σ2(Yg)of the random variable

Ygis at most its expectation E[Yg].

Proof. We show the events Eiare negatively correlated, i.e.,

for every iand j,Pr[Ei∧Ej]≤Pr[Ei].Pr[Ej]. Let Fibe

the event that a given man does not include woman ion his

preference list. By the independence and symmetry of the

preference lists of men, we have Pr[Ei] = (Pr[Fi])n, and

Pr[Ei∧Ej] = (Pr[Fi∧Fj])n. Therefore, it is enough to

show that for every iand j,Pr[Fi|Fj]≤Pr[Fi].

3In more mathematical terms, this means that Xµ(g)stochastically

dominates Yg.

Let Mbe an arbitrarily large constant. The following

process is one way to simulate the selection of one prefer-

ence list L= (l1, . . . , lk): Consider the multiset Σconsisting

of bpiMccopies of the name of woman i. Pick a random

permutation πof Σ. Let libe the i’th distinct name in π.

It is not hard to see that as M→ ∞, the probability of a

given list Lin this process converges to its probability un-

der distribution Dk. Therefore, Pr[Fi]is equal to the limit as

M→ ∞ of the probability that kdistinct names occur be-

fore iin π. Similarly, if Σ0denotes the multiset obtained by

removing all copies of woman jfrom Σ, then Pr[Fi|Fj]is

equal to the limit as M→ ∞ of the probability that kdistinct

names occur before iin a random permutation of Σ0. How-

ever, this is precisely equal to the probability that kdistinct

names other than joccur before iin a random permutation π

of Σ. But that certainly implies that kdistinct names (includ-

ing j) occur before iin π, and so for every πwhere Fi|Fjhap-

pens, Fialso happens. Therefore, Pr[Fi|Fj]≤Pr[Fi]. Thus,

Pr[Ei∧Ej]≤Pr[Ei].Pr[Ej], and so the variance σ2(Yg)is

σ2(Yg) = E[Y2

g]−E[Yg]2

=

g

X

i=1

Pr[Ei]+2 X

1≤i<j≤g

Pr[Ei∧Ej]

−

g

X

i=1

Pr[Ei]2−2X

1≤i<j≤g

Pr[Ei].Pr[Ej]

≤

g

X

i=1

Pr[Ei] = E[Yg]



Proof of Lemma 4.1. Let qbe the probability that Yg<

E[Yg]/2. By the Chebyshev inequality and Lemma 4.4,

q≤Pr h

Yg−E[Yg]

>E[Yg]/2i

≤σ2(Yg)

(E[Yg]/2)2≤4

E[Yg].

Therefore, by Lemma 4.2 and the fact that 1/(Yg+ 1) is

always at most one, we have

E1

Xµ(g)+1≤E1

Yg+ 1

≤(1 −q)1

E[Yg]/2+1+q

≤6

E[Yg],

which together with Lemma 4.3 completes the proof. 

5 Proofs of economic implications

In this section, we prove the corollaries stated in Section 3.

The first of these results argues that a dishonest player has

7

economic incentives to be honest when other players are

honest.

Proof of Corollary 3.1. Fix a person, say a man named

Adam and suppose all other players are truthful. Theorem 3.1

implies that with probability at least 1−o(1), Adam has at

most one stable wife, Eve, with respect to the true preference

lists of the players. Suppose all other players are truthful.

We claim Adam’s best response is truth-telling. Suppose

not. Allow Adam to play his best response pand let µbe

the matching that the stable matching mechanism outputs.

Now run the men-optimal algorithm with the same preference

lists (i.e., pfor Adam, and true preference lists for others)

and let µMbe the resulting matching. By Theorem A,

Adam must prefer his match in µMto his match in µ.

However, by Theorem D, in the men-proposing algorithm,

Adam’s dominant strategy is truth-telling and, by assumption,

matches him to Eve. Therefore, Adam must prefer Eve to

his match in µMand thus to his match in µ. But Eve is the

woman that Adam would have been matched to in the original

mechanism if he had been truthful (since it was his unique

stable match), and so his altered strategy pwas not his best

response. 

The second corollary shows that the game GPm,Pwde-

fined in Section 3 has an equilibrium in which in expectation

a(1 −o(1)) fraction of participants are truthful.

Proof of Corollary 3.2. Suppose we are using the men-

proposing mechanism (the women-proposing situation is

analogous). We prove that the following set of strategies

forms an equilibrium in the game GPm,Pw: all men announce

their true preferences; all women who have at most one stable

husband (with respect to Pm, Pw) announce their true prefer-

ences; and all women who have more than one stable husband

truncate their preference lists just after their optimal stable

husband. We denote the altered preference lists of women

by P0

w. By Theorem D, men cannot improve their situation

by altering their strategy. Consider a woman, say Alice, and

assume Alice will be assigned to Bob if the players use the

strategies in (Pm, P 0

w). It is easy to see that there is a unique

stable matching with respect to (Pm, P 0

w). Therefore, if we

run the women-optimal mechanism on (Pm, P 0

w), we get the

same outcome as in the men-optimal mechanism. However,

by Theorem D we know that no woman can benefit from alter-

ing her preferences in a women-optimal mechanism. Thus, if

Alice changes her strategy from the one dictated by P0

w, then

she gets a match, say Tom, that according to P0

wis not better

than Bob. However, by the definition of P0

w, this implies that

Tom is not better than Bob according to the true preferences

of Alice. This shows that the set of strategies (Pm, P 0

w)is

an equilibrium. By Theorem 3.1, we know that all men and

all but at most a o(1) fraction of women are truthful in this

equilibrium. 

Finally, we prove the third corollary, which says that if

we model the situation as a game of incomplete information,

then everybody being truthful is an approximate Bayesian

Nash equilibrium.

Proof of Corollary 3.3. Since the women-optimal mecha-

nism is used, we know by Theorem D that truthfulness is a

dominant strategy for women. It is enough to show that if

all men and women are truthful, then no man can improve

his match by more than a (1 + ε)factor if he uses a dishonest

strategy. Fix a man, Charlie. With probability 1−o(1), prefer-

ences are such that Charlie does not have more than one stable

wife. In this case, the argument used in the proof of the pre-

vious two corollaries shows that Charlie cannot gain by being

dishonest about his preferences. With probability o(1), Char-

lie has more than one stable wife, and in that case, he might

be able to improve his match from someone ranked at most k

in his list to someone ranked first. However, kis a constant.

Using this, it is easy to verify that on average, he can improve

his match by at most a factor of 1 + k2×o(1) = 1 + o(1).

Thus, everyone being truthful is an approximate equilibrium

in this game. 

6 Tighter analysis for the uniform distribution

For the case of uniform distributions, it is possible to derive a

much tighter bound on the expected number of women with

more than one stable husband.

Recall that in the proof of Theorem 3.1, we bounded the

probability that a fixed woman gis single by Eµ[1/(Xµ(g) +

1)], where Xµ(g)is the number of women at least as popular

as gthat are single in matching µ. In the case of the uniform

distribution, for every woman g,Xµ(g)is equal to the number

of singles in µ. Therefore, if we define the random variable X

as the number of women who remain unmarried in the men-

optimal stable matching (recall that by Theorem C, the set of

unmarried women is independent of the choice of the stable

marriage algorithm), then we have

ck(n)≤nE1

X+ 1 .

Thus, the following lemma shows that if men have

random preference lists of size k, then the expected number

of women who have more than one stable partner is at most

ek+1 +k2. This completes the proof of Theorem 3.2.

LEMMA 6.1. Let Xdenote the random variable defined

above. Then,

E1

X+ 1 ≤ek+1 +k2

n.

The proof of the above lemma is based on a connection be-

tween the stable marriage problem and the classical occu-

pancy problem. In the occupancy problem, mballs are dis-

tributed amongst nbins. The distribution of the number of

balls that end up in each bin has been studied extensively

from the perspective of probability theory [9]. We denote the

occupancy problem with mballs and nbins by the (m, n)-

occupancy problem. The following lemma establishes the

connection between the number of singles in the stable mar-

riage game and the number of empty bins in the occupancy

problem.

LEMMA 6.2. Let Ym,n denote the number of empty bins in

the (m, n)-occupancy problem and Xdenote the random

variable in Lemma 6.1. Then,

E1

X+ 1 ≤E1

Y(k+1)n,n + 1 +k2

n.

Proof. We use the techniques of amnesia, the principle of de-

ferred decisions, and the principle of negligible perturbations

used by Knuth [10] and Knuth, Motwani, and Pittel [11, 12].

Assume every woman has an arbitrary ordering of all men.

We define the following five random experiments:

•Experiment 1 is the experiment defined before

Lemma 6.1: every man chooses a random list of at most

kdifferent women as his preference list. Then, we run

the men-proposing stable marriage algorithm, and let the

random variable X1=Xindicates the number of single

women at the end of this experiment. Notice that in this

experiment, men do not have to select their entire pref-

erence list before running the algorithm. Instead, every

time a man has to propose to the next woman on his list,

he chooses a random woman among the women he has

not proposed to so far, and proposes to that woman. It

is clear that this does not change the experiment. This is

called the principle of deferred decisions.

•In Experiment 2, each man names kdifferent women

at random. We let X2be the number of women that no

man names in this game.

•Experiment 3 is the same as experiment 2, except here

the men are amnesiacs. That is, every time a man wants

to name a woman, he picks a woman at random from the

set of all women. Therefore, there is a chance that he

names a woman that he has already named. However,

each man stops as soon as he names kdifferent women.

Let X3be the number of women who are not named in

this process.

•In Experiment 4, we restrict every man to name at most

k+ 1 women. Therefore, each man stops as soon as

either he names kdifferent women, or when he names

k+ 1 women in total (counting repetitions). Let X4

denote the number of women who are not named in this

experiment.

•In Experiment 5 every man names exactly k+ 1 (not

necessarily different) women. The number of women

who are not named in this experiment is denoted by X5.

Clearly, X5=Y(k+1)n,n.

Now, we show how the random variables X1through X5

are related. It is easy to see that for any set of men’s prefer-

ence lists, the number of unmarried women in Experiment 1

is at least the number of women who are not named in Ex-

periment 2. Therefore, X1≥X2. Also, it is clear from the

description of Experiments 2 and 3 that X2=X3.

In order to relate X3and X4, we use the principle of

negligible perturbations. Experiments 4 is essentially the

same as Experiment 3, except in X4we only count women

who are not named by any man as one of his first k+ 1

choices. Let Edenote the event that no man names more

than k+ 1 women in Experiment 3. We first show that

Pr[ ¯

E]< k2/n. Fix a man, say Homer. We want to bound the

probability that Homer names at least k+ 2 women before

the number of different women he has named reaches k. By

the union bound, this probability is at most the sum, over

all pairs {i, j}⊂{1, . . . , k + 2}that both i’th and j’th

proposal of Homer are redundant. It is easy to see that for

any such pair, this probability is at most 1/n2. Therefore,

the probability that Homer makes more than k+ 1 proposals

is at most k+2

2/n2< k2/n2. Thus, by the union bound,

the probability of this happens for at least one man is less

than k2/n. That is, Pr[ ¯

E]< k2/n. Now, notice that

by the definition of X3and X4, the random variables X3

and X4are equal when conditioned on the occurrence of

E. Therefore, E1

X3+1 |E= E 1

X4+1 |E. Let C=





E1

X3+1 −E1

X4+1 



be the unconditioned difference of

these expectations. Then,

C=







qE1

X3+ 1|E+ ¯qE1

X3+ 1|¯

E

−qE1

X4+ 1|E−¯qE1

X4+ 1|¯

E







= ¯q







E1

X3+ 1|¯

E−E1

X4+ 1|¯

E







≤¯q

<k2

n

where q= Pr[E]and ¯q= Pr[ ¯

E]. Finally, we observe that

by the definition of Experiments 4 and 5, we have X4≥X5.

The above observations imply

E1

X+ 1 ≤E1

X2+ 1 

= E 1

X3+ 1 

≤E1

X4+ 1 +k2

n

≤E1

Y(k+1)n,n + 1 +k2

n.

This completes the proof of the lemma.

By the above lemma, the only thing we need to do

is to analyze the expected value of 1/(Ym,n + 1) in the

9

occupancy problem. We do this by writing the expected value

of 1/(Ym,n+1) as a summation and bounding this summation

by comparing it term-by-term to another summation whose

value is known.

LEMMA 6.3. Let Ym,n denote the number of empty bins in

the (m, n)-occupancy problem. Then,

E1

Ym,n + 1 ≤em/n

n.

Proof. Let Pr(m, n)be the probability that exactly rbins are

empty in the (m, n)-occupancy problem. Then P0(m, n), the

probability of no empty bin, can be written as the following

summation by the principle of inclusion-exclusion.4

P0(m, n) =

n

X

i=0

(−1)in

i(1 −i

n)m

(6.3)

The probability Pr(m, n)of exactly rempty bins can be

written in term of the probability of no empty bin in the

(m, n −r)-occupancy problem:

Pr(m, n) = n

r(1 −r

n)mP0(m, n −r).(6.4)

By Equations (6.3) and (6.4),

Pr(m, n) =

n−r

X

i=0

(−1)in

r, i(1 −r+i

n)m,(6.5)

where n

a,bdenotes the multinomial coefficient n!

a!b! (n−a−b)! .

Using Equation (6.5) and the definition of expected value we

have, using the notation E= E[ 1

Ym,n+1 ],n0=n+ 1, and

r0=r+ 1,

E=

n

X

r=0

1

r0Pr(m, n)(6.6)

=

n

X

r=0

n−r

X

i=0

(−1)i

r0n

r, i(1 −r+i

n)m

=

n

X

r=0

n−r

X

i=0

(−1)i

n0n0

r0, i(1 −r+i

n)m

=

n0

X

r=1

n0−r

X

i=0

(−1)i

n0n0

r, i(1 −r+i−1

n)m.

It is probably impossible to simplify the above summation as

a closed-form formula. Therefore, we use the following trick:

we consider another summation Swith the same number of

terms, and bound the ratio between the corresponding terms

in these two summations. This gives us a bound on the

ratio of the summation in Equation (6.6) to the summation S.

4This can also be derived by dividing a well-known formula for Stirling

numbers of the second kind (see, for example, [7, 27]) by nm.

The value of Scan be bounded easily using a combinatorial

argument.

Consider the (m, n + 1)-occupancy problem. The prob-

ability that at least one bin is empty is the sum, over r=

1, . . . , n + 1, of Pr(m, n + 1). We denote this probability by

S. By Equation (6.5) we have

S=

n+1

X

r=1

n+1−r

X

i=0

(−1)in+ 1

r, i (1 −r+i

n+ 1)m≤1,

where the inequality follows from the fact that Sis the prob-

ability of an event. The summation in Equation (6.6) and

Shave the same number of terms, and the ratio of each

term in the summation in Equation (6.6) to the correspond-

ing term in Sis equal to (1 −r+i−1

n)m/(1 −r+i

n+1 )m=

(n−r−i+1

n)m/(n+1−r−i

n+1 )m= (1 + 1

n)m. Therefore,

E[ 1

Ym,n + 1] = 1

n+ 1(1 + 1

n)mS < em/n

n.

Lemma 6.1 immediately follows from Lemmas 6.2 and 6.3.

7 Conclusion

In this paper we studied the stable marriage game in a

probabilistic setting and showed that dishonesty almost surely

does not benefit a player. This answers a question asked

by Roth and Peranson [23], and generalizes their model to

one where women have arbitrary preferences and each man

independently picks a preference list from Dk, where Dis an

arbitrary distribution. One might hope to further generalize

this model to one where each man picks a random list from

an arbitrary distribution over lists of size k. However, the

following example shows that Theorem 3.1 is not true in this

model: Assume women 1, . . . , n/2rank men in the order

1,2, . . . , n, and women n/2 + 1, . . . , n rank them in the

reverse order. Each man picks a random i∈ {1, . . . , n/2},

and with probability 1/2picks preference list (i, i +n/2) and

otherwise picks preference list (i+n/2, i). It is not difficult

to see that with these preferences, at least a 1/(8e)fraction of

women will have more than one stable husband.

There are many other interesting open questions sur-

rounding the application of the stable matching algorithm in

centralized markets. For example, in the NRMP market, the

algorithm has to accommodate couples among students who

want to live in the same city. Such couples can submit a joint

preference list of pairs of hospitals, and the algorithm has to

match them to one of the pairs in their list. With this extra

twist, there are instances for which no stable matching ex-

ist. However, so far every year the NRMP algorithm has been

able to find a stable matching. A theoretical justification for

this (in a reasonable probabilistic model), and a study of in-

centive properties in mechanisms with couples are interesting

open directions for future research. Finally, it would be in-

teresting to find other examples where one can prove that in a

probabilistic setting, truthfulness is probably the best strategy.

Acknowledgments. We are grateful to Al Roth for invaluable

discussions about the problem. We would also like to thank

Kamal Jain, Dana Randall, Amin Saberi, and Mike Saks for

helpful discussions about the stable marriage problem.

References

[1] A. Archer and E. Tardos. Truthful mechanisms for one-

parameter agents. In Proceedings of the 42nd IEEE Symposium

on Foundations of Computer Science, pages 482–491, 2001.

[2] Aaron Archer, Christos Papadimitriou, Kunal Talwar, and Eva

Tardos. An approximate truthful mechanism for combinatorial

auctions with single parameter agents. In Proceedings of the

14th Annual ACM-SIAM Symposium on Discrete Algorithms,

2003.

[3] Lawrence Bodin and (Rabbi) Aaron Panken. High tech for

a Higher authority: the placement of graduating rabbis from

Hebrew Union College–Jewish Institute of Religion. INTER-

FACES, 33(3):1–11, May-June 2003.

[4] L.E. Dubins and D.A. Freedman. Machiavelli and the

Gale-Shapley algorithm. American Mathematical Monthly,

88(7):485–494, 1981.

[5] Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, and

Scott Shenker. A bgp-based mechanism for lowest-cost routing.

In ACM Symposium on Principles of Distributed Computing,

2002.

[6] D. Gale and L. S. Shapley. College admissions and the stability

of marriage. American Mathematical Monthly, 69:9–15, 1962.

[7] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.

Concrete Mathematics, 2nd ed. Addison-Wesley, 1994.

[8] Dan Gusfield and Robert W. Irving. The Stable Marriage

Problem: Structure and Algorithms. Foundations of Computing.

MIT Press, 1989.

[9] N. Johnson and S. Kotz. Urn models and their application: an

approach to modern discrete probability theory. John Wiley &

Sons, 1977.

[10] D.E. Knuth. Marriages Stables et leurs relations avec

d’autres probl´

emes combinatoires. Les Presses de l’Universit´

e

de Montr´

eal, 1976.

[11] Donald E. Knuth, Rajeev Motwani, and Boris Pittel. Stable

husbands. In Proceedings of the First Annual ACM-SIAM

Symposium on Discrete Algorithms, pages 397–404, 1990.

[12] Donald E. Knuth, Rajeev Motwani, and Boris Pittel. Stable

husbands. Random Structures and Algorithms, 1:1–14, 1990.

[13] D. G. McVitie and L. B. Wilson. Stable marriage assignments

for unequal sets. BIT, 10:295–309, 1970.

[14] S.J. Mongell and A.E. Roth. Sorority rush as a two-sided

matching mechanism. American Economic Review, 81:441–464,

1991.

[15] Noam Nisan and Amir Ronen. Algorithmic mechanism de-

sign. Annual ACM Symposium on Theory of Computing, pages

129–140, 1999.

[16] Martin J. Osborne and Ariel Rubinstein. A course in game

theory. MIT Press, 1994.

[17] Boris Pittel. The average number of stable matchings. SIAM

J. Disc. Math, pages 530–549, 1989.

[18] Boris Pittel. On likely solutions of a stable matching problem.

In Proceedings of the third annual ACM-SIAM symposium on

Discrete algorithms table of contents, pages 10–15, 1992.

[19] Alvin E. Roth. The economist as engineer: Game theory,

experimentation, and computation as tools for design economics.

forthcoming in Econometrica.

[20] Alvin E. Roth. The economics of matching: stability and

incentives. Mathematics of Operations Research, 7:617–628,

1982.

[21] Alvin E. Roth. The evolution of the labor market for medical

interns and residents: A case study in game theory. Journal of

Political Economy, 92:991–1016, 1984.

[22] Alvin E. Roth. The national residency matching program as

a labor market. Journal of the American Medical Association,

275(13):1054–1056, 1996.

[23] Alvin E. Roth and Elliott Peranson. The redesign of the match-

ing market for american physicians: Some engineering aspects

of economic design. American Economic Review, 89:748–780,

1999.

[24] Alvin E. Roth and Marilda A. Oliveira Sotomayor. Two-sided

Matching; A Study in Game-theoretic Modeling and Analysis.

Cambridge University Press, 1990.

[25] Jay Sethuraman, Chung-Piaw Teo, and Wee-Peng Tan. The

Gale-Shapley stable marriage problem revisited: strategic issues

and applications. In IPCO’99, pages 429–438, 1999.

[26] Jay Sethuraman, Chung-Piaw Teo, and Wee-Peng Tan. The

Gale-Shapley stable marriage problem revisited: strategic is-

sues and applications. Management Science, 47(9):1252–1267,

September 2001.

[27] J. H. van Lint and R. M. Wilson. A Course in Combinatorics.

Cambridge Univ. Press, 1992.

A Number of singles revisited

In this paper, we presented an analysis of the expected

number of players that remain single in a stable marriage

mechanism, and used this lemma to prove the main result

of the paper. However, analyzing the expected number of

singles in a probabilistic setting is of independent interest.

In this appendix, we present a tighter analysis of the expected

number of singles when men have random preference lists of

size k, and women have random complete preference lists. If,

in addition to the results of this appendix, one can prove that

the number of singles is concentrated around its expectation,

then the bound (ek+k2)/n proven in this paper would be

improved.

LEMMA A.1. Consider a collection of nmen and nwomen,

each man having a random ordering of krandom women, and

each woman having a random ordering of men. Let pk(n)

denote the probability that in a stable matching with respect

to these preference lists a fixed man remains single. Then

pk(n)≥1

ek2k.

In order to prove the above lemma, we first generalize

the scenario defined in the lemma to a case where there

are mmen and nwomen (m≤n). Let pk(m, n)denote

the probability that a fixed man remains unmarried in this

scenario. Therefore, pk(n) = pk(n, n). We start by proving

that if the population of women remains constant, an increase

in the number of men can only make it harder for a man to

find a stable wife.

11

LEMMA A.2. For every k, n, m1, and m2, if m1≤m2then

pk(m1, n)≤pk(m2, n).

Proof. It is sufficient to prove that for every k, n, and m,

pk(m, n)≤pk(m+ 1, n). Consider a fixed man, Bert, in the

scenario where there are m+ 1 men. We want to compute the

probability that after running the men-proposing algorithm,

Bert remains single. By Theorem B we know that the order

of proposals does not affect the outcome of the algorithm.

Therefore, we can assume that one of the m+ 1 men, say

Ernie, starts proposing to women only after everyone else

is done with his or her proposals. Therefore, by definition,

before Ernie starts proposing, the probability that Bert is

single is precisely pk(m, n). If Bert is married at this point,

then there is a chance that after Ernie starts proposing, he

becomes single, since his wife might leave him and he might

not have anyone else in his list. However, if he is single before

Ernie starts proposing, there is no chance that he gets married

as a result of Ernie’s proposal. Therefore, the probability that

Bert remains single is not less than pk(m, n).

Proof of Lemma A.1. Let c < 1be a constant that will be

fixed later. By Lemma A.2, we have pk(n) = pk(n, n)≥

pk(dcne+ 1, n). Therefore, we only need to prove that

pk(dcne+ 1, n)≥1

ek2k. The proof of this fact is based on

the following two inequalities:

pk(dcne+ 1, n)≥c

2(1 −pk(dcne, n))k

(1.7)

pk(dcne, n)≤ck

(1.8)

We start by proving inequality (1.8). Consider the

situation where there are dcnemen and nwomen. Fix a

man, say Kermit. The probability that Kermit remains single

is pk(dcne, n). Now, consider the men-proposing algorithm.

Since the order of proposals does not change the outcome,

we can assume that Kermit will wait until everyone else stops

proposing, and then he will make his first proposal. At this

moment, there are at most dcne − 1< cn women who are

married, and at least (1 −c)nwomen who are still single. Let

Sdenote the set of single women at this point. Since Kermit’s

list consists of krandomly chosen women, the probability that

none of them is in Sis at most ck. We claim that if at least

one of the women in Kermit’s list is in Sthen Kermit will

find a wife. The reason is that every time Kermit makes a

proposal, if he proposes to a single woman, the proposal will

be accepted and the algorithm ends. But if he proposes to a

married woman, he might start a chain of proposals that will

either end at a single woman, in which case Kermit ends up

married, or gets back to Kermit, in which case the set of single

women does not change and we can repeat the same argument

for the next proposal of Kermit until he reaches a woman in

her list that is in S. By this claim, the probability that Kermit

remains single is upper bounded by the probability that none

of the women in her list is in S, which is at most ck.

Now, we prove inequality (1.7). We use a similar

argument: consider a situation where there are dcne+ 1

men and nwomen, and fix a man, say Oscar. We prove

that the probability that Oscar remains single is at least

c

2(1 −pk(dcne, n))k. To prove this, consider the men-

proposing algorithm, and let everyone other than Oscar make

proposals. After they finish proposing, Oscar enters and

proposes to the first woman in his list. Let Mdenote the

set of married women at this point. The expected size of

M, is the same as the expected number of married men,

which is (1−pk(dcne, n))dcneby the definition of pk(m, n).

Therefore, there is a probability of dcne

n(1 −pk(dcne, n)) ≥

c(1 −pk(dcne, n)) that Oscar proposes to a married woman.

A married woman rejects a new proposal with probability

at least 1/2. Thus, there is a probability of at least c

2(1 −

pk(dcne, n)) that Oscar’s marriage proposal is rejected by

her favorite woman. Similarly, the same can happen for

her second favorite woman, and so on. Therefore, there is

a probability of at least c

2(1 −pk(dcne, n))kthat Oscar

faces rejection immediately after each of his proposals, in

which case, he ends up single.

Inequalities 1.7 and 1.8 imply the following

pk(dcne+ 1, n)≥c

2(1 −ck)k.

Choosing c=k−1/k in the above inequality completes

the proof of the lemma. 