Reading Assignment: Kleinberg and Tardos, Chapter 1.
Complete
Solve Kleinberg and Tardos, Chapter 1, Exercise 1.
True or false? In every instance of the Stable Matching Problem, there is a stable matching containing a pair (m, w) such that m is ranked first on the preference list of w and w is ranked first on the preference list of m.
Answer: False. Consider a case where every man's highest-ranking woman in terms of preference is uniquely his. Now assume that all women have the same order of preference among the men, with the exception of one woman, whose preferences are ranked in the opposite order. If the man who is beloved by almost all women proposes to the one woman whose preferences differ, his highest ranking choice, she will still say yes to him even though he is not her most preferred man. Nobody will propose to her again, as all remaining men will propose to their uniquely highest ranking woman, and each of woman will say yes to a man who is not her highest ranked choice.
Solve Kleinberg and Tardos, Chapter 1, Exercise 2.
True or false? Consider an instance of the Stable Matching Problem in which there exists a man m and a woman w such that m is ranked first on the preference list of w and w is ranked first on the preference list of m. Then in every stable matching S for this instance, the pair (m, w) belongs to S.
Answer: True. A matching is defined as stable if there does not exist a pair (m, w) in which m prefers w over his current match, and w prefers m over her current match. If the m and w from the problem statement are not matched with one another in a matching $S$, then $S$ is not a stable matching. Therefore, all stable matchings will contain the pair (m, w).
True or False: An instance of the stable marriage problem has a unique stable matching if and only if the version of the Gale-Shapely algorithm where the male proposes and the version where the female proposes both yield the exact same matching.
Answer: False.
A stable roommate problem with 4 students a, b, c, d is defined as follows. Each student ranks the other three in strict order of preference. A matching is defined as the separation of the students into two disjoint pairs. A matching is stable if no two separated students prefer each other to their current roommates. Does a stable matching always exist? If yes, give a proof. Otherwise give an example roommate preference where no stable matching exists.
Answer: Consider the following scenario:
$a$ prefers $b$ over $c$, and $c$ over $d$
$b$ prefers $c$ over $d$, and $d$ over $a$
$c$ prefers $d$ over $a$, and $a$ over $b$
$d$ prefers $a$ over $b$, and $b$ over $c$
In this case, there is no stable matching. After the first roomate pair is assigned, there are two students who can no longer choose their top choice. If they partner with the remaining roomate, then the pairing is complete. But it is not stable, and any attempt to switch the matchings will create a new pair that would rather be with one another over their current remaining choice.
Solve Kleinberg and Tardos, Chapter 1, Exercise 3.
For every set of TV shows and ratings, is there always a stable pair of schedules? Resolve this question by doing one of the following two things:
(a) give an algorithm that, for any set of TV shows and associated ratings, produces a stable pair of schedules; or
(b) give an example of a set of TV shows and associated ratings for which there is no stable pair of schedules.
Answer: Using option (b), consider the following set of TV shows and ratings:
| Network A | Network B |
|---|
| 1 | 2 |
| 3 | 4 |
| 5 | 6 |
| 7 | 8 |
No matter how network A aligns their TV show air times, network B always has a way of ordering its own times such that the show it airs is always exactly 1 point higher in ratings than whatever is airing on network A. Yet, network A always has 3 shows which it can schedule to air such that it airs at a time in which its rating will be 1 point higher than the show airing on network B.
Solve Kleinberg and Tardos, Chapter 1, Exercise 4.
We say that an assignment of students to hospitals is stable if neither of the following situations arises.
First type of instability:
There are students s and s′, and a hospital h, in which
- s is assigned to h
- s′ is assigned to no hospital
- h prefers s′ to s
Second type of instability:
There are students s and s′, and hospitals h and h′, in which
- s is assigned to h
- s′ is assigned to h′
- h prefers s′ to s
- s′ prefers h to h′
So we basically have the Stable Matching Problem, except that (i) hospitals generally want more than one resident, and (ii) there is a surplus of medical students.
Show that there is always a stable assignment of students to hospitals, and give an algorithm to find one.
Answer: For every hospital, create a vertex for every student position they are seeking to fill. For each student, assign an equal preference to be matched with any one particular hospital vertex. Run Gale-Shapley on the two sets of vertices, where the hospitals choose the students, ending when there are no remaining hospital vertices without a matching student.
N men and N women were participating in a stable matching process in a small town named Walnut Grove. A stable matching was found after the matching process finished and everyone got engaged. However, a man named Almazo Wilder, who is engaged with a woman named Nelly Oleson, suddenly changes his mind by preferring another woman named Laura Ingles, who was originally ranked right below Nelly in his preference list, therefore Laura and Nelly swapped their positions in Almanzos preference list. Your job now is to find a new matching for all of these people and to take into account the new preference of Almanzo, but you don’t want to run the whole process from the beginning again, and want to take advantage of the results you currently have from the previous matching. Describe your algorithm for this problem. Assume that no woman gets offended if she got refused and then gets proposed by the same person again.
Answer: Almazo breaks off his engagement with Nelly, and proposes to Laura. If Laura prefers her current partner over Almazo, she rejects Almazo, and Almazo will proceed to patch things up with Nelly. If Laura prefers Almazo over her current partner, she accepts Almazo, causing her current fiance to become single again. Let us call him, Millhouse.
If there was a woman that Millhouse preferred over Laura, he would have proposed to her already. Instead, Millhouse simply proposes to his next highest choice.
The algorithm continues to be Gale-Shapley after Millhouse originally became single, as Almazo is engaged to his highest-preference choice that also prefers him over anyone she has originally been proposed to. Millhouse becoming single is a natural consequence of the continuation of the algorithm, and the matching produced from this moment will result in the exact same matching as if we had run Gale Shapley from the beginning.