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
| Download | |
| Open PDF In Browser | View PDF |
Marriage, Honesty, and Stability
Nicole Immorlica∗
Mohammad Mahdian∗
admissions [19], sorority and fraternity rush [14], and assignMany centralized two-sided markets form a matching between par- ment of graduating rabbis to their first congregation [3]. Since
ticipants by running a stable marriage algorithm. It is a well-known most applications of the stable marriage algorithm involve the
fact that no matching mechanism based on a stable marriage algo- participation of independent agents, it is natural to investigate
rithm can guarantee truthfulness as a dominant strategy for partic- how we should expect these agents to behave. In particular,
ipants. However, as we will show in this paper, in a probabilistic we would like to know whether agents can benefit by being
setting where the preference lists of one side of the market are com- dishonest about their preference lists. Ideally, in economic
posed of only a constant (independent of the the size of the market) settings such as job markets, we would like to design mechnumber of entries, each drawn from an arbitrary distribution, the anisms in which truth-telling is a dominant strategy, i.e., it is
number of participants that have more than one stable partner is van- in the best interest of each individual agent to tell the truth,
ishingly small. This proves (and generalizes) a conjecture of Roth no matter what other agents do. We call such a mechanism a
and Peranson [23]. As a corollary of this result, we show that, with truthful mechanism. Truthful mechanisms have received sighigh probability, the truthful strategy is the best response for a given nificant attention in the computer science community (see, for
player when the other players are truthful. We also analyze equilib- example, [1, 5, 15]). Unfortunately, as shown by Roth [20],
ria of the deferred acceptance stable marriage game. We show that there is no mechanism for the stable marriage problem in
the game with complete information has an equilibrium in which a which truth-telling is a dominant strategy for both men and
(1−o(1)) fraction of the strategies are truthful in expectation. In the women. See the book by Roth and Sotomayor [24] for a dismore realistic setting of a game of incomplete information, we will cussion about this problem and other problems related to the
show that the set of truthful strategies form a (1+o(1))-approximate economic aspects of the stable marriage problem.
Nonetheless, stable matching algorithms have had specBayesian-Nash equilibrium. Our results have implications in many
tacular
success in practical applications. One particular job
practical settings and were inspired by the work of Roth and Peranmarket
—
the medical residency market — has been using a
son [23] on the National Residency Matching Program.
centralized stable marriage market system called the National
Residency Matching Program (NRMP) since the 1950s [21].
1 Introduction
Suppose all the eligible bachelors and bachelorettes in a town To this day, most medical residences are formed through an
confide in the town’s matchmaker their ideal spouses. Each updated version of this centralized market system redesigned
man submits an ordered preference list of the women he in 1998 by Roth [22]. It seems surprising that an algorithm
would like to marry. Similarly, each woman submits an like the one used by the NRMP which provably admits strateordered preference list of the men she would like to marry. gic behavior can be so successful. Roth and Peranson [23]
The matchmaker must arrange marriages such that no one is noted that, in practice, very few students and hospitals could
tempted to ask for a divorce. In particular, the matchmaker have benefited by submitting false preferences. For exammust be sure that there is no pair of young lovers who prefer ple, in 1996, out of 24,749 applicants, just 21 could have
each other to their assigned spouses. Such a set of marriages affected their match by submitting false preferences (assumis called stable, and finding a set of stable marriages is known ing, of course, that no one lied in 1996). Roth and Peranas the stable marriage problem. Gale and Shapley [6] showed son [23] conjectured that the main reason for this peculiarity
that the stable marriage problem always has a solution and is the sheer size of the job market. In a small town, every
developed an algorithm to find it. Since the seminal work man knows every woman, but in the medical market, a stuof Gale and Shapley, there has been a significant amount of dent can not possibly interview at every hospital. In practice,
work on the mathematical structure of stable marriages and the length of applicant preference lists is quite small, about
related algorithmic questions. See, for example, the book by 15, while the number of positions is large, about 20,000. ExKnuth [10], the book by Gusfield and Irving [8], or the book perimentally, Roth and Peranson [23] showed that in a model
where random preference lists of limited length are generated
by Roth and Sotomayoror [24].
The stable marriage problem has many promising appli- for participants, the number of participants who have more
cations in two-sided markets such as job markets [19], college than one stable partner (and therefore the number of those
who can benefit by lying) is small. They conjectured that in
∗ Computer Science and Artificial Intelligence Lab, MIT, Cambridge, MA
this probabilistic setting, the fraction of such people tends to
Abstract
02139. Email: {nickle,mahdian}@theory.lcs.mit.edu.
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 n men and n women 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 n approaches 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
D of 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 probability 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 computing bounds on the expectation and variance of the number of
single popular women.
Related work. This paper is motivated by experimental results and a conjecture in the paper by Roth and Peranson [23]. Sethuraman et al. [25, 26] have studied the
stable matching game when participants are required to announce complete preference lists, and have given an optimal
cheating algorithm and several experimental results regarding the chances that an agent can benefit by lying in this
game. One can also view our results as an analysis of stable 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 developed 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 organized as follows. In Section 2, we define the stable marriage
problem and discuss the relevant known results from the literature. 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 Peranson [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 questions concerning stable marriage algorithms and two-sided
markets.
2 Stable marriage preliminaries
Consider a community consisting of a set W of n women and
a set M of n men. 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 ∪ W to M ∪ W in 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 ∈ M and w ∈ W , µ(m) = w,
we say that w is the wife of m and m is the husband of w
in µ; or, if for some x ∈ M ∪ W , µ(x) = x, we say that
x remains single in µ. A pair m ∈ M , w ∈ W is called a
blocking pair for a matching µ, if m prefers w to µ(m), and
w prefers m to µ(w). A matching with no blocking pair is
called a stable matching. If a man m and a woman w are a
couple in some stable matching µ, we say that m is a stable
husband of w, and w is 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 m and
creates a proposal from him to the next woman on his list.
If this woman prefers m to her current assignment, then she
tentatively accepts m’s proposal, and rejects the man she
lists of k women, 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 players 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.
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.
T HEOREM A. The men-proposing algorithm always finds a
stable matching µ. Furthermore, this stable matching is menoptimal, i.e., for every man m and every stable wife w of m
other than µ(m), m prefers µ(m) to w. At the same time, µ
is the worst possible stable matching for women, i.e., for any
woman w and any stable husband m of w other than µ(w),
w prefers m to µ(w).
C ONJECTURE 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,
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.
ck (n)
= 0.
lim
n→∞
n
T HEOREM B. The men-proposing algorithm always finds the
same stable matching, independent of the order in which the We prove this conjecture in this paper. In fact, we will prove
proposals are made.
the following stronger result. Let D be an arbitrary fixed
distribution over the set of women such that the probability
We will also need the following theorem of Roth [21] of each woman in D is nonzero.1 Intuitively, having a
and McVitie and Wilson [13], which says that the choice of high probability in D indicates that a woman is popular.
the stable matching algorithm does not affect the number of The preference lists are constructed by picking each entry
people who remain unmarried at the end of the algorithm.
of the list according to D, and removing the repetitions.
T HEOREM C. In all stable matchings, the set of people who More precisely, we construct a random list (l1 , . . . , lk ) of k
women as follows. At step i, repeatedly select women w
remain single is the same.
independently according to D until w 6∈ {l1 , . . . , li−1 } and
k
A stable matching mechanism is an algorithm that elicits then set li = w. Let D be the distribution over lists of size
2
a preference list from each participant, and outputs a match- k produced by this process. Notice that if D is the uniform
k
ing that is stable with respect to the announced preferences. distribution, D is nothing but the uniform distribution over
We say that truthfulness is a dominant strategy for a partic- the set of all lists of size k of women. Therefore, the model
ipant a if, no matter what strategy other participants use, a of Roth and Peranson [23] is a special case of our model. We
cannot benefit (i.e., improve his or her match according to also generalize their result in another respect: we assume that
his or her true preferences) by submitting a list other than women have arbitrary complete preference lists, as opposed
his or her true preference list. Ideally, we would like to de- to the assumption in [23] that they have random complete
sign mechanisms in which truthfulness is a dominant strategy preference lists. Our main result is the following theorem.
for all participants. However, Roth [20] proved that there is T HEOREM 3.1. Consider a situation where each woman has
no such mechanism for the stable marriage problem. On the an arbitrary complete preference list, and each man has a
positive side, the following theorem (due to Roth [20] and preference list chosen independently at random according to
Dubins and Freedman [4]) shows that in deferred acceptance D k . Then, for all fixed k,
mechanisms, truthfulness is a dominant strategy for half the
ck (n)
population.
lim
= 0.
n→∞
n
T HEOREM D. In the men-optimal stable marriage mechaEven though we state and prove our results assuming that
nism, truth-telling is a dominant strategy for men. Similarly, all preference lists are of size exactly k, it is straightforward
in the women-optimal mechanism, truth-telling is a dominant to see that our proof carries over to the case where preference
strategy for women.
lists are of size at most k. For uniform distributions, we can
prove a strong result on the rate of convergence of this limit.
3 Our results
Consider a situation where there are n men and n women.
1 This assumption is needed to make sure that the problem is well-defined.
2 See the conclusion for a discussion of why this is the most general setting
Assume the preference list of each man is chosen independently and uniformly at random from the set of all ordered in which we can hope to get a positive result.
3
T HEOREM 3.2. Consider a situation where each woman has
an arbitrary complete preference list, and each man has a
preference list of k women chosen uniformly and independently. Then, the expected number of women who have more
than one stable husband is bounded by ek+1 + k 2 , 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 probability, a given player’s best strategy is truth-telling when the
other players are truthful. Thus, a dishonest player who believes 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.
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.
C OROLLARY 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
C OROLLARY 3.1. Fix any stable matching mechanism, and Nash equilibrium in which everybody is truthful.
consider an instance with n women with arbitrary complete
preference lists and n men with preference lists drawn from
The proofs of these corollaries are presented in Section 5.
D k (as in Theorem 3.1). Then, for any given person x, the
probability (over the men’s preference lists) that for x, the 4 Proof of Theorem 3.1
truthful strategy is not the best response in a situation where In this section, we will prove our main technical result,
the other players are truthful is o(1) (at most O(ek /n) for Theorem 3.1. The proof consists of three main components.
uniform distributions).
First, we present an algorithm that, given the preference lists,
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
Pm and Pw denote 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].
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 simplest way to check whether a woman g has 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 g has the
same husband in both these matchings. However, analyzing
the probability that g has more than one stable husband using 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
C OROLLARY 3.2. Assume the preference lists Pw of women that outputs all stable husbands of a given woman in an arare arbitrary, and the preference lists Pm of men are drawn bitrary stable marriage problem in one run of a men-propose
from D k (as in Theorem 3.1). The game GPm ,Pw induced algorithm. This algorithm is a generalization of the algorithm
by these preferences and the men-proposing (or women- of Knuth et al. [11, 12] to the case of incomplete preference
proposing) mechanism has an equilibrium in which, in ex- lists.
Suppose we want the stable husbands of woman g.
pectation, a (1 − o(1)) fraction of strategies are truthful.
Initially all the people are unmarried (the matching is empty).
In the above setting, we assume that each player knows The algorithm closely follows the man-proposing algorithm
the preference lists of the other players when he/she is select- for finding a stable matching. However, g’s objective is
ing a strategy, i.e., we have a game of complete information. to explore all her options, therefore, every time the menA more realistic assumption is that each player only knows proposing algorithm finds a stable marriage, g divorces her
the distribution of preference lists of the other players. Each husband and lets the algorithm continue.
g preferred mi+1 to mi . Thus mi+1 is on g’s truncated preference list, and so the tentative matchings of the two algorithms
1. Initialization: Run the man-proposing algorithm to find are the same. Furthermore, m
i+1 is the first proposal g has acthe men-optimal stable matching. If g is unmarried, cepted in the man-proposing algorithm. All other women who
output ∅.
get married in the set of stable matchings already have hus2. Selection of the suitor: Output the husband m of g as one bands since they have husbands in Algorithm 4.1, and so the
of her stable husbands. Remove the pair (m, g) from the man-proposing algorithm terminates with the current matchmatching (woman g and man m are now unmarried) and ing. Thus, mi+1 is the worst possible stable husband for g
set b = m. (the variable b is the current proposing man.) which is better than mi .
A LGORITHM 4.1.
3. Selection of the courted: If b has already proposed to all
the women on his preference list, terminate. Otherwise,
let w be his favorite woman among those he hasn’t
proposed to yet.
4.2 Analyzing the expectation We are interested in the expected number of women with more than one stable husband,
or, equivalently, the probability that a fixed woman g has 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 D k . 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 Ai denotes the set of
women that man i has proposed to so far. Men and women
are indexed by numbers between 1 and n.
4. The courtship:
(a) If w has received a proposal from a man she
likes better than b, she rejects b and the algorithm
continues at the third step.
(b) If not, w accepts b. If w = g, the algorithm
continues at the second step. Otherwise, if w was
previously married, her previous husband becomes
the suitor b and the algorithm continues at the third
step. If w was previously unmarried, terminate the
algorithm.
Notice that in step 4(a) of the algorithm, w compares b
to the best man who has proposed to her so far, and not to the
man she is currently matched to. Therefore, after g divorces
one of her stable husbands, she has a higher standard, and will
not accept any man worse than the man she has divorced. For
w 6= g, step 4(a) is equivalent to comparing b to the man w is
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.
A LGORITHM 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 b be the l’th man and increase l by one.
(b) Otherwise, we have found a stable matching. If
g is single in this stable matching, then terminate.
Otherwise, increment xg , remove the pair (m, g)
from the matching (man m and woman g who
were previously married to each other are now
unmarried) and set b = m.
T HEOREM 4.1. Algorithm 4.1 outputs all stable husbands of
g in order of her preference from her worst stable husband to
her best stable husband.
Proof. We prove the theorem by induction. As the manproposing 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 g is matched in Algorithm 4.1 and unmatched in the man-proposing algorithm).
Now since mi+1 was accepted, the fourth step guarantees that
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 w randomly according to distribution D from the set of all women until w 6∈ Ab .
Add w to Ab .
4. The courtship:
(a) If w has received a proposal from a man she
likes better than b, she rejects b and the algorithm
continues at step 3.
5
(b) If not, w accepts b. If w was previously married,
her previous husband becomes the suitor b and
the algorithm continues at the third step. If w
was previously single and xg = 0, the algorithm
continues at the second step. If w was previously
single and xg ≥ 1, the algorithm continues at the
second step if w = g and terminates if w 6= g.
Before giving a proof of Theorem 3.1, we introduce a few
notations. For every woman i, let pi denote the probability of
i in the distribution D. We say that a woman i is 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 expected number of women with more than one stable husband. We show that for every > 0, if n is large
enough, thenPck (n)/n ≤ . By linearity of expectation,
ck (n) =
g∈W Pr[g has more than one stable husband].
Fix a woman g ∈ W . We want to bound the probability that
g has 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 xg in 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 > 1 conditioned 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 g that remain single in the stable matching µ and
Xµ (g) = |Sµ (g)|. If g is single in µ, then xg = 0
and therefore Pr[xg > 1 | µ] = 0. Otherwise, xg >
1 if only if woman g accepts another proposal before the
algorithm terminates. We bound this by the probability that
g receives 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, g appears 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 w is picked is at least as large as the probability that g
is picked. Therefore, the probability that g appears before all
elements of Sµ (g) in a sequence whose elements are picked
according to D is at most the probability the g appears first in
a random permutation on the elements of {g} ∪ Sµ (g), which
is 1/(Xµ (g) + 1). Thus, for every µ,
(4.1)
Thus,
(4.2)
Pr[xg > 1 | µ] ≤
1
Xµ (g) + 1
h
i
Pr[xg > 1] = Eµ Pr[xg > 1 | µ]
1
≤ Eµ
.
Xµ (g) + 1
We complete the proof assuming the following lemma,
whose proof is given in Section 4.3.
L EMMA 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 ≥
and Pr[xg > 1] ≤ 1 for smaller g’s, we obtain
ck (n) ≤
16nk
ln(n) ,
n
X
16nk
12e8nk/g
+
ln(n)
g
16nk
g= ln(n)
≤
n
X
3 ln(n)eln(n)/2
16nk
+
ln(n)
4nk
16nk
≤
√
16nk
+ 3 n ln(n)/(4k) = o(n),
ln(n)
g= ln(n)
and so for every constant k, the fraction of women with more
than one stable husband, ck (n)/n, goes to zero as n tends 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 w remains single is greater than or equal to the
probability that w does not appear on the preference list
of any man. More precisely, let Ew denote the event that
the woman w does not appear on the preference list of any
man when these preferences are drawn from D k . Let Yg
denote the number of women w ≤ g for which the event Ew
happens. Then we have the following lemma.
L EMMA 4.2. For every g, we always have Xµ (g) ≥ Yg .3
Let M be an arbitrarily large constant. The following
process is one way to simulate the selection of one preference list L = (l1 , . . . , lk ): Consider the multiset Σ consisting
of bpi M c copies of the name of woman i. Pick a random
permutation π of Σ. Let li be the i’th distinct name in π.
It is not hard to see that as M → ∞, the probability of a
given list L in this process converges to its probability under distribution D k . Therefore, Pr[Fi ] is equal to the limit as
M → ∞ of the probability that k distinct names occur before i in π. Similarly, if Σ0 denotes the multiset obtained by
removing all copies of woman j from Σ, then Pr[Fi |Fj ] is
equal to the limit as M → ∞ of the probability that k distinct
names occur before i in a random permutation of Σ0 . However, this is precisely equal to the probability that k distinct
names other than j occur before i in a random permutation π
of Σ. But that certainly implies that k distinct names (including j) occur before i in π, and so for every π where Fi |Fj happens, Fi also happens. Therefore, Pr[Fi |Fj ] ≤ Pr[Fi ]. Thus,
Pr[Ei ∧ Ej ] ≤ Pr[Ei ].Pr[Ej ], and so the variance σ 2 (Yg ) is
Proof. Every woman w < g for which Ew happens is a
woman who is at least as popular as g and 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 Yg is small and therefore it does not deviate far from its
mean.
L EMMA 4.3. For g > 4k, the expected number E[Xµ (g)]
of single women more popular than woman g is at least
g −8nk/g
.
2e
Pk
Proof. Let Q = j=1 pj denote the total probability of the
first k women under D. The probability that a man m does
not list a woman w as his i’th preference given that he picks
w1 , . . . , wi−1 as his first i − 1 women, is equal to
1−
1−
pw
Pi−1
j=1
pw j
≥1−
pw
.
1−Q
σ 2 (Yg )
Thus the probability that m does not list w at all is at least
pw k
(1 − 1−Q
) , and so the probability that woman w is not listed
pw nk
by any man is at least (1 − 1−Q
) . If w > k, there are at
least w − k women who are at least as popular as w, but not
1−Q
among the k most popular women. Therefore, pw ≤ w−k
.
By these two inequalities, for every w > 2k we have
= E[Yg2 ] − E[Yg ]2
g
X
X
=
Pr[Ei ] + 2
i=1
−
g
X
i=1
≤
g
X
Pr[Ei ∧ Ej ]
1≤i 4k, the expectation of Yg is at least
E[Yg ]
=
g
X
Pr[Ew ] ≥
w=1
≥
g
X
j=g/2
g
X
e−4nk/j
q
j=2k
e−8nk/g =
g −8nk/g
e
.
2
h
i
≤ Pr Yg − E[Yg ] > E[Yg ]/2
≤
4
σ 2 (Yg )
≤
.
(E[Yg ]/2)2
E[Yg ]
Therefore, by Lemma 4.2 and the fact that 1/(Yg + 1) is
always at most one, we have
L EMMA 4.4. The variance σ 2 (Yg ) of the random variable
Yg is at most its expectation E[Yg ].
1
1
E
≤ E
Xµ (g) + 1
Yg + 1
Proof. We show the events Ei are negatively correlated, i.e.,
1
≤
(1
−
q)
+q
for every i and j, Pr[Ei ∧ Ej ] ≤ Pr[Ei ].Pr[Ej ]. Let Fi be
E[Yg ]/2 + 1
the event that a given man does not include woman i on his
6
≤
,
preference list. By the independence and symmetry of the
E[Yg ]
n
preference lists of men, we have Pr[Ei ] = (Pr[Fi ]) , and
Pr[Ei ∧ Ej ] = (Pr[Fi ∧ Fj ])n . Therefore, it is enough to which together with Lemma 4.3 completes the proof.
show that for every i and j, Pr[Fi |Fj ] ≤ Pr[Fi ].
5 Proofs of economic implications
3 In more mathematical terms, this means that X (g) stochastically
In this section, we prove the corollaries stated in Section 3.
µ
dominates Yg .
The first of these results argues that a dishonest player has
7
economic incentives to be honest when other players are
honest.
then everybody being truthful is an approximate Bayesian
Nash equilibrium.
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 p and let µ be
the matching that the stable matching mechanism outputs.
Now run the men-optimal algorithm with the same preference
lists (i.e., p for Adam, and true preference lists for others)
and let µM be the resulting matching. By Theorem A,
Adam must prefer his match in µM to 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 µM and 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 p was not his best
response.
Proof of Corollary 3.3. Since the women-optimal mechanism 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), preferences are such that Charlie does not have more than one stable
wife. In this case, the argument used in the proof of the previous two corollaries shows that Charlie cannot gain by being
dishonest about his preferences. With probability o(1), Charlie 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, k is a constant.
Using this, it is easy to verify that on average, he can improve
his match by at most a factor of 1 + k 2 × 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
The second corollary shows that the game GPm ,Pw de- much tighter bound on the expected number of women with
fined in Section 3 has an equilibrium in which in expectation more than one stable husband.
a (1 − o(1)) fraction of participants are truthful.
Recall that in the proof of Theorem 3.1, we bounded the
Proof of Corollary 3.2.
Suppose we are using the men- probability that a fixed woman g is single by Eµ [1/(Xµ (g) +
proposing mechanism (the women-proposing situation is 1)], where Xµ (g) is the number of women at least as popular
analogous). We prove that the following set of strategies as g that are single in matching µ. In the case of the uniform
forms an equilibrium in the game GPm ,Pw : all men announce distribution, for every woman g, Xµ (g) is equal to the number
their true preferences; all women who have at most one stable of singles in µ. Therefore, if we define the random variable X
husband (with respect to Pm , Pw ) announce their true prefer- as the number of women who remain unmarried in the menences; and all women who have more than one stable husband optimal stable matching (recall that by Theorem C, the set of
truncate their preference lists just after their optimal stable unmarried women is independent of the choice of the stable
husband. We denote the altered preference lists of women marriage algorithm), then we have
by Pw0 . By Theorem D, men cannot improve their situation
1
by altering their strategy. Consider a woman, say Alice, and
.
ck (n) ≤ nE
X +1
assume Alice will be assigned to Bob if the players use the
strategies in (Pm , Pw0 ). It is easy to see that there is a unique
Thus, the following lemma shows that if men have
stable matching with respect to (Pm , Pw0 ). Therefore, if we random preference lists of size k, then the expected number
run the women-optimal mechanism on (Pm , Pw0 ), we get the of women who have more than one stable partner is at most
same outcome as in the men-optimal mechanism. However, ek+1 + k 2 . This completes the proof of Theorem 3.2.
by Theorem D we know that no woman can benefit from altering her preferences in a women-optimal mechanism. Thus, if L EMMA 6.1. Let X denote the random variable defined
Alice changes her strategy from the one dictated by Pw0 , then above. Then,
she gets a match, say Tom, that according to Pw0 is not better
1 ek+1 + k 2
than Bob. However, by the definition of Pw0 , this implies that
E
≤
.
X +1
n
Tom is not better than Bob according to the true preferences
of Alice. This shows that the set of strategies (Pm , Pw0 ) is
The proof of the above lemma is based on a connection bean equilibrium. By Theorem 3.1, we know that all men and
tween the stable marriage problem and the classical occuall but at most a o(1) fraction of women are truthful in this
pancy problem. In the occupancy problem, m balls are disequilibrium.
tributed amongst n bins. The distribution of the number of
Finally, we prove the third corollary, which says that if balls that end up in each bin has been studied extensively
we model the situation as a game of incomplete information, from the perspective of probability theory [9]. We denote the
Now, we show how the random variables X1 through X5
are related. It is easy to see that for any set of men’s preference lists, the number of unmarried women in Experiment 1
is at least the number of women who are not named in Experiment 2. Therefore, X1 ≥ X2 . Also, it is clear from the
description of Experiments 2 and 3 that X2 = X3 .
In order to relate X3 and X4 , we use the principle of
negligible perturbations. Experiments 4 is essentially the
same as Experiment 3, except in X4 we only count women
who are not named by any man as one of his first k + 1
choices. Let E denote the event that no man names more
than k + 1 women in Experiment 3. We first show that
Pr[Ē] < k 2 /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
more than k + 1 proposals
2Homer2makes
2
/n
<
k
/n
.
Thus,
by the union bound,
is at most k+2
2
the probability of this happens for at least one man is less
than k 2 /n. That is, Pr[Ē] < k 2 /n. Now, notice that
by the definition of X3 and X4 , the random variables X3
and X4 are equal when conditioned
of
on the occurrence
E. Therefore, E X31+1 |E = E X41+1 |E . Let C =
E X31+1 − E X41+1 be the unconditioned difference of
these expectations. Then,
occupancy problem with m balls and n bins by the (m, n)occupancy problem. The following lemma establishes the
connection between the number of singles in the stable marriage game and the number of empty bins in the occupancy
problem.
L EMMA 6.2. Let Ym,n denote the number of empty bins in
the (m, n)-occupancy problem and X denote the random
variable in Lemma 6.1. Then,
1
k2
1
+ .
E
≤E
X +1
Y(k+1)n,n + 1
n
Proof. We use the techniques of amnesia, the principle of deferred 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
k different women as his preference list. Then, we run
the men-proposing stable marriage algorithm, and let the
random variable X1 = X indicates the number of single
women at the end of this experiment. Notice that in this
experiment, men do not have to select their entire preference 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.
C
• In Experiment 2, each man names k different women
at random. We let X2 be the number of women that no
man names in this game.
1
1
|E + q̄E
|Ē
X3 + 1
X3 + 1
1
1
− qE
|E − q̄E
|Ē
X4 + 1
X4 + 1
1
1
|Ē − E
|Ē
= q̄ E
X3 + 1
X4 + 1
≤ q̄
k2
<
n
=
qE
• 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, where q = Pr[E] and q̄ = Pr[Ē]. Finally, we observe that
each man stops as soon as he names k different women. by the definition of Experiments 4 and 5, we have X ≥ X .
4
5
Let X3 be the number of women who are not named in The above observations imply
this process.
1
1
E
≤ E
X +1
X2 + 1
• In Experiment 4, we restrict every man to name at most
1
k + 1 women. Therefore, each man stops as soon as
= E
X
+
1
3
either he names k different women, or when he names
1
k2
k + 1 women in total (counting repetitions). Let X4
≤ E
+
X4 + 1
n
denote the number of women who are not named in this
k2
1
experiment.
≤ E
+ .
Y(k+1)n,n + 1
n
• In Experiment 5 every man names exactly k + 1 (not
This completes the proof of the lemma.
necessarily different) women. The number of women
who are not named in this experiment is denoted by X5 .
By the above lemma, the only thing we need to do
Clearly, X5 = Y(k+1)n,n .
is to analyze the expected value of 1/(Ym,n + 1) in the
9
occupancy problem. We do this by writing the expected value The value of S can be bounded easily using a combinatorial
of 1/(Ym,n +1) as a summation and bounding this summation argument.
Consider the (m, n + 1)-occupancy problem. The probby comparing it term-by-term to another summation whose
ability that at least one bin is empty is the sum, over r =
value is known.
1, . . . , n + 1, of Pr (m, n + 1). We denote this probability by
L EMMA 6.3. Let Ym,n denote the number of empty bins in S. By Equation (6.5) we have
the (m, n)-occupancy problem. Then,
n+1
X n+1−r
X
em/n
r+i m
1
i n+1
) ≤ 1,
S=
(−1)
(1 −
E
≤
.
n
+1
r,
i
Ym,n + 1
n
r=1 i=0
Proof. Let Pr (m, n) be the probability that exactly r bins 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
n
X
i
i n
(6.3)
P0 (m, n) =
(−1)
(1 − )m
n
i
i=0
where the inequality follows from the fact that S is the probability of an event. The summation in Equation (6.6) and
S have the same number of terms, and the ratio of each
term in the summation in Equation (6.6) to the correspondr+i m
m
ing term in S is equal to (1 − r+i−1
=
n ) /(1 − n+1 )
n+1−r−i m
1 m
n−r−i+1 m
)
=
(1
+
)
.
Therefore,
)
/(
(
n
n+1
n
1
1
1
em/n
E[
]=
(1 + )m S <
.
The probability Pr (m, n) of exactly r empty bins can be
Ym,n + 1
n+1
n
n
written in term of the probability of no empty bin in the
(m, n − r)-occupancy problem:
Lemma 6.1 immediately follows from Lemmas 6.2 and 6.3.
n
r
7 Conclusion
(6.4)
Pr (m, n) =
(1 − )m P0 (m, n − r).
r
n
In this paper we studied the stable marriage game in a
probabilistic setting and showed that dishonesty almost surely
By Equations (6.3) and (6.4),
does not benefit a player. This answers a question asked
n−r
X
by Roth and Peranson [23], and generalizes their model to
n
r
+
i
(6.5) Pr (m, n) =
(−1)i
(1 −
)m ,
one where women have arbitrary preferences and each man
r, i
n
i=0
independently picks a preference list from D k , where D is an
n
n!
where a,b
denotes the multinomial coefficient a! b! (n−a−b)!
. arbitrary distribution. One might hope to further generalize
Using Equation (6.5) and the definition of expected value we this model to one where each man picks a random list from
an arbitrary distribution over lists of size k. However, the
1
0
have, using the notation E = E[ Ym,n
+1 ], n = n + 1, and
following example shows that Theorem 3.1 is not true in this
r0 = r + 1,
model: Assume women 1, . . . , n/2 rank men in the order
n
1, 2, . . . , n, and women n/2 + 1, . . . , n rank them in the
X
1
(6.6) E =
Pr (m, n)
reverse order. Each man picks a random i ∈ {1, . . . , n/2},
0
r
r=0
and with probability 1/2 picks preference list (i, i + n/2) and
n n−r
X
X (−1)i n
otherwise picks preference list (i + n/2, i). It is not difficult
r+i m
=
(1 −
)
to see that with these preferences, at least a 1/(8e) fraction of
0
r
r, i
n
r=0 i=0
women will have more than one stable husband.
n n−r
X
X (−1)i n0
There are many other interesting open questions surr+i m
=
(1 −
)
0
0, i
rounding the application of the stable matching algorithm in
n
r
n
r=0 i=0
centralized markets. For example, in the NRMP market, the
0
n0 nX
−r
X
algorithm has to accommodate couples among students who
(−1)i n0
r+i−1 m
=
(1 −
) .
0
want to live in the same city. Such couples can submit a joint
n
r,
i
n
r=1 i=0
preference list of pairs of hospitals, and the algorithm has to
It is probably impossible to simplify the above summation as match them to one of the pairs in their list. With this extra
a closed-form formula. Therefore, we use the following trick: twist, there are instances for which no stable matching exwe consider another summation S with the same number of ist. However, so far every year the NRMP algorithm has been
terms, and bound the ratio between the corresponding terms able to find a stable matching. A theoretical justification for
in these two summations. This gives us a bound on the this (in a reasonable probabilistic model), and a study of inratio of the summation in Equation (6.6) to the summation S. centive properties in mechanisms with couples are interesting
open directions for future research. Finally, it would be in4 This can also be derived by dividing a well-known formula for Stirling
teresting to find other examples where one can prove that in a
probabilistic setting, truthfulness is probably the best strategy.
numbers of the second kind (see, for example, [7, 27]) by nm .
Acknowledgments. We are grateful to Al Roth for invaluable [19] Alvin E. Roth. The economist as engineer: Game theory,
experimentation, and computation as tools for design economics.
discussions about the problem. We would also like to thank
forthcoming in Econometrica.
Kamal Jain, Dana Randall, Amin Saberi, and Mike Saks for
[20] Alvin E. Roth. The economics of matching: stability and
helpful discussions about the stable marriage problem.
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 matching 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 issues 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.
References
[1] A. Archer and E. Tardos. Truthful mechanisms for oneparameter 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. INTERFACES, 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émes combinatoires. Les Presses de l’Université
de Montréal, 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 design. 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.
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 + k 2 )/n proven in this paper would be
improved.
L EMMA A.1. Consider a collection of n men and n women,
each man having a random ordering of k random 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
1
pk (n) ≥ ek2
k.
In order to prove the above lemma, we first generalize
the scenario defined in the lemma to a case where there
are m men and n women (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
L EMMA A.2. For every k, n, m1 , and m2 , if m1 ≤ m2 then
Now, we prove inequality (1.7). We use a similar
pk (m1 , n) ≤ pk (m2 , n).
argument: consider a situation where there are dcne + 1
men and n women, and fix a man, say Oscar. We prove
Proof. It is sufficient to prove that for every k, n, and m, that the probability that Oscar remains single is at least
k
pk (m, n) ≤ pk (m + 1, n). Consider a fixed man, Bert, in the
c
2 (1 − pk (dcne, n)) . To prove this, consider the menscenario where there are m + 1 men. We want to compute the
proposing algorithm, and let everyone other than Oscar make
probability that after running the men-proposing algorithm,
proposals. After they finish proposing, Oscar enters and
Bert remains single. By Theorem B we know that the order
proposes to the first woman in his list. Let M denote the
of proposals does not affect the outcome of the algorithm.
set of married women at this point. The expected size of
Therefore, we can assume that one of the m + 1 men, say
M , is the same as the expected number of married men,
Ernie, starts proposing to women only after everyone else
which is (1 − pk (dcne, n))dcne by the definition of pk (m, n).
is done with his or her proposals. Therefore, by definition,
Therefore,
there is a probability of dcne
n (1 − pk (dcne, n)) ≥
before Ernie starts proposing, the probability that Bert is
c(1
−
p
(dcne,
n))
that
Oscar
proposes
to a married woman.
k
single is precisely pk (m, n). If Bert is married at this point,
A
married
woman
rejects
a
new
proposal
with probability
then there is a chance that after Ernie starts proposing, he
at
least
1/2.
Thus,
there
is
a
probability
of
at least 2c (1 −
becomes single, since his wife might leave him and he might
not have anyone else in his list. However, if he is single before pk (dcne, n)) that Oscar’s marriage proposal is rejected by
Ernie starts proposing, there is no chance that he gets married her favorite woman. Similarly, the same can happen for
there is
as a result of Ernie’s proposal. Therefore, the probability that her second favorite woman, and so on. Therefore,
k
c
(1
−
p
(dcne,
n))
that
Oscar
a
probability
of
at
least
k
Bert remains single is not less than pk (m, n).
2
faces rejection immediately after each of his proposals, in
Proof of Lemma A.1. Let c < 1 be a constant that will be which case, he ends up single.
Inequalities 1.7 and 1.8 imply the following
fixed later. By Lemma A.2, we have pk (n) = pk (n, n) ≥
pk (dcne + 1, n). Therefore, we only need to prove that
1
pk (dcne + 1, n) ≥ ek2
k . The proof of this fact is based on
the following two inequalities:
(1.7)
(1.8)
pk (dcne + 1, n) ≥
c
2
k
(1 − pk (dcne, n))
pk (dcne, n) ≤ ck
We start by proving inequality (1.8). Consider the
situation where there are dcne men and n women. 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)n women who are still single. Let
S denote the set of single women at this point. Since Kermit’s
list consists of k randomly chosen women, the probability that
none of them is in S is at most ck . We claim that if at least
one of the women in Kermit’s list is in S then 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 .
pk (dcne + 1, n) ≥
−1/k
Choosing c = k
the proof of the lemma.
c
2
k
(1 − ck ) .
in the above inequality completes
Source Exif Data:
File Type : PDF File Type Extension : pdf MIME Type : application/pdf PDF Version : 1.3 Linearized : No Page Count : 12 Producer : pdfTeX-0.14h Creator : TeX Create Date : 2005:04:11 19:37:00EXIF Metadata provided by EXIF.tools