This document is a compilation of my notes for CPS 688: Advanced Algorithms at TMU. All information comes from my professor’s lectures, as well as the course textbook Algorithm Design by Kleinberg.
Adam Szava - 2tor.ca
W2023
This week just had an introductory lecture, along with an example algorithm. The algorithm tackles the problem of stable matching, which is defined as:
<aside> 💡 Problem 1 (Stable Matching):
Given a set of objects, each with its own ranking of every object, pair up objects in such a way that each object has no self-interest in changing pairs. ****
</aside>
For example, if $5$ eligible bachelors make an ordered list of their top $5$ eligible bachelorettes for marriage, and those $5$ bachelorettes each make an ordered list of their top $5$ bachelors, we want assign each bachelor to a bachelorette in such a way that no pair decides to split because of mutual self-interest.
Those splitting pairs are called unstable pairs, formally defined as:
<aside> ➕ Definition 1 (Unstable Pair)
In the context of stable matching, a bachelor $x$ and a bachelorette $y$ are unstable if:
In the case of an unstable pair, it would be in the self-interest of each individual $x$ and $y$ to ditch their current partners. Another way to rephrase the stable matching problem is to make a matching in which there are no unstable pairs, called a stable assignment.
An important distinction is that we care to have everyone as happy as possible (as making it so on average everyone gets near their top choices), all that matters is we make a matching with no unstable pairs.
Below is an example set of ratings the two groups could give to one another.
The following is an example of an unstable matching (a matching which contains an unstable pair):
Xavier prefers Amy over his current assigned partner, and Amy prefers Xavier over her current assigned partner. It would be in the self-interest of both of them to ditch their assigned partner. The point of the algorithm we are about to see is to make sure there are no such unstable pairs.
<aside> 💻 Algorithm 1 (Propose-and-Reject) [Stable Matching]
</aside>
This week is mostly a review of basic graph theory from COE428.