Gale Shapley and Stable Matching Problem
Let us assume a case that is impossible to happen in real life: a man, let’s call him m1, proposes to a woman, let’s call her w1, by one following the order of his preference list. If a woman is not “taken,” meaning she has not gotten paired up with a partner or she prefers m1 over her current partner m2, she will accept him and her new partner will be updated to m1. If she is already paired up with m3, another man, and she prefers m3 over m1, she rejects.
Now, think about the following question:
Can a man or a woman end up better off by lying about his or her preferences?
Suppose each participant has a preference list. A woman w supposedly prefers man m to m’, but both m and m’ are quite low on her list. If she lies about her preferences, meaning switching the order of m and m’ by falsely claiming the opposite order, will w end up being with m1, the man she truly prefers over m and m’?
This question explores the issue of truthfulness in the Stable Matching Problem and the Gale-Shapley algorithm used in this problem.
Stable Matching
Let’s first look at the definition of Stable Matching.
A stable match is a perfect match with no unstable pair.
- What is an Unstable Pair?
Given a set of preferences among men and women. Man m and woman w form an unstable pair if both:
- m prefers w to his matched woman
- w prefers m to her matched man
For example:
man m1’s list:
w1, w2
m1 is engaged with w2
woman w1’s list:
m1, m2
w1 is engaged with m2
Here, m1-w1 is an unstable pair
- What is a Perfect Match?
A perfect match MA is a set of ordered pairs m-w with m <- M and w <- W such that:
- Each man m <- M appears in at most one pair of MA
- Each woman w <- W appears in at most one pair of MA
A matching MA is perfect is |MA| = |M| = |W| = n
The goal of a stable matching problem is to find a stable match (if one exists), given the preference lists of n men and n women.
Gale-Shapley and Man-Optimality
To find a stable match, an intuitive method called the “Gale-Shapley deferred acceptance algorithm” is used.
The algorithm is basically the same as the process of pairing up men and women in the case I just asked you to imagine. To put it into a more general case, it is the following:
1. First, initialize M to empty matching
2. A WHILE loop. While some man m is unmatched and hasn’t proposed to every single woman on his list
In this loop, get w, the first woman on m’s list to whom m has not proposed yet
IF w is unmatched, add m-w to matching M
ELSE IF w prefers m to current partner m’, replace m’-w with m-w in matching M
ELSE, w rejects m
3. Finish the loop, return stable matching M
It is known that Gale-Shapley matching is man-optimal. To see further proof of this claim, feel free to read this.
Now that we understand the process of the Gale-Shapley algorithm and its way of finding a stable match, let’s get back to our original question: can a man or a woman end up better off by lying about his or her preferences?
This is a rather difficult question to prove if you want to give a proof that for any set of preference lists, lying about the preference of partners can improve a man or a woman’s final match in the Gale-Shapley algorithm. Hence, here I choose to come up with an example of a set of preference lists for men and women and there exists a switch that can improve a woman’s partner in the end.
Preference list of men:
D: A > B > C
E: B > A > C
F: A > B > C
Preference list of women:
A: E > D > F
B: D > E > F
C: D > E > F
If woman A lies, updated preference list of women:
A: E > F > D (she lies about preferring F over D but she actually does not)
B: D > E > F
C: D > E > F
If we run the Gale-Shapley on the first two preference lists above, we obtain the final match to be D-A, E-B, F-C, noticing that A is paired with her second preference.
If we run the Gale-Shapley on the updated preference list of women if A lies, we obtain the match to be D-B, E-A, F-C, noticing that A ends up with her first preference.
Voila! We now proved that lying about one’s preference list makes it possible for men or women to end up better off; that is, with their more desired partner.
