Transcript Stable Marriage Lecture - Northwestern University

Marriage, Honesty, & Stability
NICOLE IMMORLICA, NORTHWESTERN UNIVERSITY
Math
&
Romance
Love, marriage, & bipartite graphs
the boys
Jake
Holly > Claire > Twiggy > Jill
Elwood
Claire > Jill > Twiggy > Holly
Curtis
Twiggy
Jake > Elwood > Curtis > Ray
Claire
Jake > Curtis > Elwood > Ray
Jill
Twiggy > Jill > Holly > Claire
Ray > Curtis > Elwood > Jake
Ray
Holly > Claire > Twiggy > Jill
Holly
Ray > Jake > Elwood > Curtis
and girls
When is marriage stable?
Jake
Holly > Claire > Twiggy > Jill
Elwood
Claire > Jill > Twiggy > Holly
Curtis
Twiggy > Jill > Holly > Claire
Twiggy
Jake > Elwood > Curtis > Ray
Claire
Jake > Curtis > Elwood > Ray
Jill
Ray > Curtis > Elwood > Jake
Ray
A pair (m,w) is a blocking pair for a matchingHolly
if m
Holly > Claire prefers
> Twiggyw> to
Jill his match and w prefers m to
Ray
> Jake
> Elwood > Curtis
her
match.
When is marriage stable?
AApair
matching
(m,w) isis astable
blocking
if there
pair is
fornoa blocking
matchingpair.
if m
prefers w to his match and w prefers m to her match.
The courtship ritual
Jake
Holly > Claire > Twiggy > Jill
Elwood
Claire > Jill > Twiggy > Holly
Curtis
Twiggy
Jake > Elwood > Curtis > Ray
Claire
Jake > Curtis > Elwood > Ray
Jill
Twiggy > Jill > Holly > Claire
Ray > Curtis > Elwood > Jake
Ray
Holly > Claire > Twiggy > Jill
Holly
Ray > Jake > Elwood > Curtis
What’s math say about romance?
Question 1. Do stable matchings always exist?
Question 2. Are they easy to find?
Question 3. Does the courtship ritual work?
Question 4. Are stable matchings unique?
Question 5. If not, who benefits?
What would Cupid prove?
Theorem. Courtship algorithm terminates.
Theorem. Resulting marriage is stable.
Corollary. Stable marriages always exist and are
easy to find.
We’ll prove this using potential functions.
Step 1: proof of termination
The courtship ritual terminates.
1. Define a potential function: the number of
names on boys’ lists.
2. Note this is strictly decreasing and always
non-negative.
Step 2a: defining invariant
The girls’ options only ever improve!
For every girl G and boy B, if G is crossed off B’s
list it is because she’s married to him or has a
suitor she prefers.
… because B only crosses off G after proposing,
and G only rejects proposals when she finds
someone better.
Step 2b: proof of stability
The resulting matching is stable.
Consider boy B and girl G that are not married to
each other.
1. Suppose G was crossed off B’s list. Then G
prefers husband to B, so won’t elope with B.
2. Suppose G is on B’s list. Then B didn’t
propose to G yet, so B prefers wife to G, so
won’t elope with G.
What can math say on romance?
Question 1. Do stable matchings always exist?
Question 2. Are they easy to find?
Question 3. Does the courtship ritual work?
Question 4. Are stable matchings unique????
Question 5. If not, who benefits????
Recall …
Jake
Holly > Claire > Twiggy > Jill
Elwood
Claire > Jill > Twiggy > Holly
Curtis
Twiggy
Jake > Elwood > Curtis > Ray
Claire
Jake > Curtis > Elwood > Ray
Jill
Twiggy > Jill > Holly > Claire
Ray > Curtis > Elwood > Jake
Ray
Holly > Claire > Twiggy > Jill
Holly
Ray > Jake > Elwood > Curtis
In an alternate universe
Jake
Holly > Claire > Twiggy > Jill
Elwood
Claire > Jill > Twiggy > Holly
Curtis
Twiggy
Jake > Elwood > Curtis > Ray
Claire
Jake > Curtis > Elwood > Ray
Jill
Twiggy > Jill > Holly > Claire
Ray > Curtis > Elwood > Jake
Ray
Holly > Claire > Twiggy > Jill
Holly
Ray > Jake > Elwood > Curtis
Conclusion: not unique
Jake
Holly > Claire > Twiggy > Jill
Elwood
Claire > Jill > Twiggy > Holly
Curtis
Twiggy
Jake > Elwood > Curtis > Ray
Claire
Jake > Curtis > Elwood > Ray
Jill
Twiggy > Jill > Holly > Claire
Ray > Curtis > Elwood > Jake
Ray
Holly > Claire > Twiggy > Jill
Holly
Ray > Jake > Elwood > Curtis
Stable spouses
In general, there are many stable marriages.
Girl G
Boy B
Girl G’
A person P is a stable spouse of a person P’ if
P is married to P’ in some stable matching.
Boys are happier than girls
way
Boys marry their most preferred stable wife….
… and girls get their least preferred stable husband!
Of 1st claim, by contradiction. Suppose some boy isn’t
married to favorite stable spouse.
1. He must have proposed to her and been refused.
2. Let B be 1st boy to lose his favorite stable wife G.
3. Then G must have had a proposal from a boy B’
she preferred to B.
4. Since B’ has not yet crossed off his favorite stable
wife, B’ must love G more than any stable wife.
5. But then B’ and G will elope in marriage which
matches B to G, contradicting stability of wife G.
Of 2nd claim, by contradiction. Suppose there is a stable
matching in which girl G gets worse husband.
1. Let B be her husband when boys propose and B’
be her husband in worse matching.
2. Then G prefers B to B’ by assumption.
3. Furthermore, by 1st claim, G is favorite stable wife
of B, so B prefers G to wife in worse matching.
4. But then B and G will elope in worse matching.
But of course … symmetry
If girls propose, then they will get
their favorite stable husbands.
Applications of Stable Matching
Centralized two-sided markets.
– National Residency Matching Program (NRMP) since 1950’s
– Dental residencies and medical specialties in the US,
Canada, and parts of the UK
– National university entrance exam in Iran
– Placement of Canadian lawyers in Ontario and Alberta
– Sorority rush
– Matching of new reform rabbis to their first congregation
– Assignment of students to high-schools in NYC
–…
Classical Results
Theorem 1. The matching produced by the men-proposing
algorithm is the best stable matching for men and the worst
stable matching for women.
This matching is called the men-optimal matching.
Theorem 2. The order of proposals does not affect the stable
matching produced by the men-proposing algorithm.
Theorem 3. In all stable matchings, the set of people who remain
single is the same.
NRMP
National Residency Matching Program
• After finishing med school in the US, students
must complete internships at hospitals prior
to receiving their degree
• Students interview at hospitals and rank their
preferences
• Hospitals rank students they interviewed
• A hospital-optimal deferred acceptance
algorithm determines placement
Incentive Compatibility
Question. Do participants have an incentive to
announce a list other than their real
preference lists?
Answer. Yes!
In the men-proposing algorithm, sometimes
women have an incentive to be dishonest
about their preferences.
Recall …
Jake
Holly > Claire > Twiggy > Jill
Elwood
Claire > Jill > Twiggy > Holly
Curtis
Twiggy
Jake > Elwood > Curtis > Ray
Claire
Jake > Curtis > Elwood > Ray
Jill
Twiggy > Jill > Holly > Claire
Ray > Curtis > Elwood > Jake
Ray
Holly > Claire > Twiggy > Jill
Holly
Ray > Jake > Elwood > Curtis
A small white lie
Jake
Holly > Claire > Twiggy > Jill
Elwood
Claire > Jill > Twiggy > Holly
Curtis
Twiggy
Jake > Elwood > Curtis > Ray
Claire
Jake > Curtis > Elwood > Ray
Jill
Twiggy > Jill > Holly > Claire
Ray > Curtis > Elwood > Jake
Ray
Holly > Claire > Twiggy > Jill
Holly
Ray > Jake > Elwood > Curtis
Incentive Compatibility
Next Question. Is there any truthful mechanism for the
stable matching problem?
Answer. No!
Roth (1982) proved that there is no mechanism for
the stable marriage problem in which truth-telling is
the dominant strategy for both men and women.
Incentive Compatibility
Next Question. When can people benefit from lying?
Theorem. The best match a woman can receive from a
stable mechanism is her optimal stable husband with
respect to her true preference list and others’
announced preference lists.
In particular, a woman can benefit from lying only if
she has more than one stable husband.
Data from NRMP show that the chance that a
participant can benefit from lying is slim.
1993
1994
1995
1996
# applicants 20916 22353 22937 24749
# positions 22737 22801 22806 22578
# applicants who
could lie
16
20
14
21
Explanations
(Roth and Peranson, 1999)
The following limit the number of stable husbands of women:
Preference lists are correlated.
Applicants agree on which hospitals are most prestigious;
hospitals agree on which applicants are most promising.
If all men have the same preference list, then everybody has a
unique stable partner, whereas if preference lists are
independent random permutations almost every person has
more than one stable partner. (Knuth et al., 1990)
Preference lists are short.
Applicants typically list around 15 hospitals.
A Probabilistic Model
Men. Choose preference lists uniformly at
random from lists of at most k women.
Women. Randomly rank men that list them.
Conjecture (Roth and Peranson, 1999). Holding
k constant as n tends to infinity, the fraction of
women who have more than one stable
husband tends to zero.
Our Results
Theorem. Even allowing women arbitrary
preference lists in the probabilistic model,
the expected fraction of women who have
more than one stable husband tends to zero.
Economic Implications
Corollary 1. When other players are truthful, almost surely a
random player’s best strategy is to tell the truth.
Corollary 2. The stable marriage game has an equilibrium in
which in expectation a (1-o(1)) fraction of the players are
truthful.
Corollary 3. In stable marriage game with incomplete
information there is a (1+o(1))-approximate Bayesian Nash
equilibrium in which everybody tells the truth.
Structure of proof
Step 1. An algorithm that counts the number of
stable husbands of a given woman.
Step 2. Bounding the probability of having more
than one stable husband in terms of the
number of singles
Step 3. Bounding the number of singles by the
solution of the occupancy problem.
Step 1. Finding stable husbands of g
1. Use men-proposing algorithm to find a stable
matching.
2. Whenever the algorithm finds a stable matching,
have g divorce her husband and continue the menproposing algorithm (but now g has a higher
standard for accepting new proposals).
3. Terminate when either
– a man who is married in the men-optimal matching runs
through his list, or
– a woman who is single in the men-optimal matching
receives a proposal.
Question. If each woman has an arbitrary complete
preference list, and each man has a random list of k
women, what is the probability that this algorithm
returns more than one stable husband for g?
The main tool that we will use to answer this question
is the principle of deferred decisions:
Men do not pick the list of their favorite women in
advance; Instead, every time a man needs to propose, he
picks a woman at random and proposes to her. A man
remains single if he gets rejected by k different women.
Step 2. Bounding the probability
• Consider moment when algorithm finds first (i.e.,
men-optimal) matching. Call this matching μ.
• Let A denote the set of women who are single in μ,
and X denote |A|.
• Fix random choices before the algorithm finds μ, and
let probabilities be over random choices that are
made after that.
Step 2, cont’d.
• Look at sequence of women who receive a proposal.
• Probability algorithm finds another stable husband
for g is bounded by probability g comes before all
members of A in sequence, i.e., 1/(X+1).
• Therefore, the probability that g has more than one
stable husband is at most E[1/(X+1)].
Step 3. Number of singles
We need to compute E[1/(X+1)], where X is
the number of singles in the men-optimal
matching.
Simple Observation. The probability that a
woman remains single is at least the
probability that she is never named by men.
Step 3, cont’d.
Let Ym,n denote the number of empty bins in an
experiment where m balls are dropped
independently and uniformly at random in n bins.
Lemma.
E[
1
X+1
] < E[
1
Y(k+1)n, n + 1
] +
k2
n
Proof Sketch. Assume (without loss of generality!) that
men are amnesiacs and might propose to a woman
twice. The total number of proposals (bins) is at most
(k+1)n w.h.p.
The occupancy problem
Lemma. E[
1
Ym, n + 1
] <
em/n
n
Proof sketch.
– Use the principle of inclusion and exclusion to
compute E[1/(Ym,n+1)] as a summation.
– Compare this summation to another (known)
summation term-by-term.
Putting it all together…
Theorem. In the model where women have
arbitrary complete preference lists and men
have random lists of size k, the probability
that a fixed woman has more than one stable
husband is at most
k+1
e
+
n
2
k
Future Directions
Preference Elicitation. How do students choose hospitals to
interview at? Can we increase the efficiency of the
market?
Settings with correlation. What if students have geographic
preferences?
Stable matching with couples. Why has the NRMP algorithm
found a matching every year?