COMP6207 Algorithmic Game Theory - Coursework 3: Gale-Shaply Algorithm and Stable Matching Problem
Student ID: Name:
COMP6207 Algorithmic Game Theory 2019/20
Coursework 3 (8.34% of the final mark)
- [60 marks] Suppose the preferences of men and women are given by the following tables, in which 1 is their most preferred partner and 5 is their least preferred partner. Find a stable matching using the Gale-Shapley algorithm with men making proposals. Find a stable matching using the Gale-Shapley algorithm with women making proposals.
| 1 | 2 | 3 | 4 | 5 |
Amy | Eric | Adam | Bill | Dan | Carl |
Beth | Carl | Bill | Dan | Adam | Eric |
Cara | Bill | Carl | Dan | Eric | Adam |
Diane | Adam | Eric | Dan | Carl | Bill |
Ellen | Dan | Bill | Eric | Carl | Adam |
Figure 1: Women’s preferences.
| 1 | 2 | 3 | 4 | 5 |
Adam | Beth | Amy | Diane | Ellen | Cara |
Bill | Diane | Beth | Amy | Cara | Ellen |
Carl | Beth | Ellen | Cara | Diane | Amy |
Dan | Amy | Diane | Cara | Beth | Ellen |
Eric | Beth | Diane | Amy | Ellen | Cara |
Figure 2: Men’s preferences.
- [40 marks] In the stable matching problem, if the relationship of the individuals is not ”two-sided,” then stable matching may not exist. Consider this ”roommate” problem. There are four students, A, B, C, and D. Every two of them must be paired up to share a two-bedroom house. Each of them has preferences over which of the others they would prefer to have as a roommate. The preferences are:
A: C > B > D
B: A > C > D
C: B > A > D
D: B > A > C
Show that no matter how do you pair them up, there will always be two students who are not matched, but prefer each other to their current roommate.
