§ Matching problems (TODO)

Given a graph $G = (V, E)$ a matching is a collection of edges of $G$ where every node has degree 1.

§ Perfect matching

A matching is perfect if it has size $|V|/2$, or no vertex is left isolated. That is, everyone is matched with someone.

§ Weighted (Perfect) Matching

Some matchings maybe more preferable than orders, by giving weights.Usually, lower weights are more desirable. We may want to find the minimum weight matching. n The weight of a matching is the sum of the weights on the edges of $M$. In this context, we usually always ask for a perfect matching . Otherwise, one can trivially not match anyone to get a min-weight matching of weight 0. So the definition of a min-weight matching for the graph $G$ is a perfect matching with minimum weight.
We don't see these in 6.042. Will have to read flows/hungarian to study this.

§ Preference matching

Given a matching, $(x, y)$ form a rogue couple if they both prefer each other over their matched mates. Ie, they both wish to defect from their 'matched mates'. A matching is stable if there aren't any rogue couples. The goal is to find a perfect stable matching. That is, get everyone married up, and make it stable!
The point is, not everyone has to become happy! It's just that we don't allow rogue couples who can mutually get a benefit.

§ Bad situation for preference matching

If boys can love boys as well as girls, then we can get preference orderings where no stable marriage is possible. The idea is to create a love triangle.

• Alex prefers Bobby over Robin
• Bobby prefers Robin over Alex
• Robin prefers Alex over Bobby.
• And then there is mergatoid, who is the third choice for everyone. mergatoid's preferences don't matter

§ Theorem: there does not exist a stable matching for this graph

Proof: assume there does exist a stable matching, call it $M$. Mergatoid must be matched with someone. WLOG, assume mergatoid is matched to Alex by symmetry. If mergatoid is matched to alex, then we must have Robin matched to Bobby

• Alex and Bobby are not rogue, because Bobby likes Robin more than Alex.
• Alex and Robin are the rogue, because (1) Robin prefers Alex over Bobby, and (2) Alex prefers Robin over Mergatoid.

Hence, we found a rogue couple. So $M$ was not stable.

§ Stable Marriage Problem: success in some cases!

We have $N$ boys and $N$ girls [need the same number of each ]. Each boy has his own ranked preference list of all the girls. Each gil has her own ranked preference list of all the boys. The lists are complete and there are no ties. We have to find a perfect matching with no rogue couples.

§ Mating algorithm / Mating ritual

The ritual takes place over several days.

• In the morning, the girl comes out to the balcony.
• Each boy goes to his favourite girl who hasn't been crossed off in his list and serenades her.
• In the afternoon, if a girl has suitors, she tells her favourite suitor "maybe I'll marry you, come back tomrrow". Girls don't make it too easy. For all the lower priority boys, she says "now way I'm marrying you".
• In the night, all the boys who heard a no cross that girl off from their list. If the boy heard a maybe, he will serenade her.
• If we encounter a day where every girl has at most one suitor, the algorithm terminates. So we don't have two or more boys under one balcony.

§ Things to prove

• Show that the algorithm terminates.
• Show that everyone gets married.
• Show that there are no rogue couples.
• We may want to show it runs quickly.
• Fairness? is this good for girls, or for boys?

§ Termination, terminates quickly: N^2 + 1 days

Proof by contradiction. suppose TMA does not terminate in $N^2+1$ days.
Claim If we don't terminate on a day, then that's because a girl had two or more boys under her balcony. Thus, at least one boy crosses the girl off of his list. We measure progress by the cross-out. In $N^2$ days, all boys would have crossed out all girls.

§ Invariant

• P is that if a girl $G$ every rejected a boy $B$ then she has a suitor who she prefers to $B$.

• To prove that this is indeed an invariant, induction on time. At the beginning, no girl has rejected any boy, so it's vacuously true.

• Assume P holds at the end of day $d$. At the end of day $d+1$, there's two cases.
• If $G$ rejects $B$ on day $d+1$, there must be a better boy, hence P is true.
• If $G$ rejected $B$ on day less than $d+1$, then $G$ must have had a better suitor $B'$on day $d$ by the induction hypothesis. Now on day $d+1$, she either has $B'$or someone even better, $B''$ came along.

§ Everyone is married

Proof by contradiction. Assume not everyone was married. Assume that some boy $B$ is not married. (If there is no boy who is not married then everyone is married).

• If we was not married at the end, then he must be rejected by everyone .
• If he were not rejected by everyone, then he would be under someone's balcony trying to serenade them. That he is unmatched means that all the girls have rejected him.
• This means that every girl has somebody better than $B$, which is not possible, because that would mean that every girl was married. That's not possible as there are an equal number of boys and girls.

Sid note: I don't buy this! we need to show that in the course of the algorithm,
it's impossible for a girl to end up empty handed. I'd prove this by noticing that
at each round, a girl acts like some kind of "gated compare and swap" where only
the highest value is allowed to be put into the mutex, and all of the others
are rejected. Thus, if there is a girl who has multiple writes, she will
only allow one of the writes to happen, and permanently disallow the other writes.
Thus, the other writes have to move to other girls.

§ No rogue couples

Contradiction: assume that there is a pair that are not married, call them bob and gail. We need to show that they will not go rogue. Since bob and gail are not married, either (1) gail rejected bob, or (2) gail did not reject bob because bob never serenaded her. If bob had serenaded her and was not rejected, then they would have been married!.

• (1) If gail rejected bob, then gail has marries someone she likes better than bob since she's rejected bob. Thus, gail and bob can't be a rogue couple because she likes her spouse more than bob.

• (2) bob never serenaded gail. This means that he married someone who he prefers more than gail, cause he never reached gail.

§ Fairness

• The girls get to pick the best ones who come to them.
• The boys get to go out and try their first choice though. A girl may wait for her Mr. Right who will never come along, and thus satisfice.
• Which is better? proposors or acceptors? Sociological question! Here it turns out that boys have all the power .
• Let $S$ be the set of all stable matchings. We know that $S$ is not empty because the algorithm is able to produce at least one stable matching.
• For each person $P$, we define the realm of possibility for $P$ to be the set $Q$ of people that they can be matched to in a stable matching. So $Q_p \equiv \{ q : (p, q) \in M, M \in S \}$. That is, there's a stable marriage where you're married to them.
• A person's optimal mate is their most favourite in the realm of possibility. Their pessimal mate is their least favourite in the realm of possibility.

§ Theorem: No two boys can have the same optimal mate.

Assume two boys do have the same optimal mate. Say $(b^\star, g)$ and $(b, g)$. WLOG let $g$ prefer $b^\star$ over $b$. Now, there exists some "stable matching" where $g$ is matched with $b$, because $g$ is the optimal mate, hence in the realm of possibility of $b$. However, this matching is unstable because $(b^\star, g)$ is a rogue couple: $g$ likes $b^\star$ more than $b$, and $b^\star$ likes $g$ best!

§ Theorem: No two girls can have the same optimal mate

Redo previous proof by switching girl and boy. It's not a proof about the algorithm , but about the structure of stable matches themselves.

§ Theorem: The algorithm matches every boy with his optimal mate

Proof by contradiction. Assume that Nicole is optimal for Keith, but Keith winds up not marrying Nicole. This means he must have crossed off Nicole in some day (bad day).
Note that he must have gotten to Nicole , because no girls he prefers over nicole would have led to a stable marriage, and would thus not be an output generated by the algorithm. This, all girls he prefers above nicole must reject him at some step of the algorithm till he reaches Nicole.
We assume that in this instance of the algorithm, he does not get Nicole, thus Nicole too must have rejected him.
Let us assume that Keith gets rejected by Nicole on the earliest bad day .
When Nicole rejects Keith, this means that Nicole had a suitor she likes better than Keith. Call him Tom. Tom >Nicole Keith. Furthermore, since this is the earliest bad day, tom has not crossed off his optimal girl, and thus nicole must be the "best girl" for tom --- either out of his league, or the optimal feasible math. Thus, Nicole >Tom optimal-feasible-mate-for-tom.
But this means that in a stable marriage with (Nicole, Keith), we would have (Nicole, Tom) be a rogue couple! This contradicts the fact that nicole is optimal for keith.

• Proof from Optimal Stable Matching Video, MIT 6.042J Mathematics for Computer Science, Spring 2015.

§ We match every girl with her pessimal mate

TODO

§ Theorem: matchings form a lattice

Let $M = ((b_1, g_1), (b_2, g_2), \dots (b_n, g_n))$ and $M' = ((b_1, g'_1), (b_2, g'_2), \dots, (b_n, g'_n))$ be two stable matchings. Then.

is a stable matching.

§ Step 1: This is a matching

First we show that it is indeed a matching: the marriages are all monogamous. Assume that we had $g_1 = \max_{b_1}(g_1, g_1') = \max_{b_2}(g_2, g_2') = g_2'$.
Since $(b_2, g_2')$ is the match in $M'$ and $g_1 = g_2'$, we have that $(b_2, g_1)$ is the match in $M'$. We also know that $g_1 >_{b_1} g_1'$ from the assumption. Since the matching $M'$ is stable, we need to ensure that $(g_1, b_1)$ is not a rogue couple; $b_1$ prefers $g_1$ over $g_1'$. Thus, we must have that $b_2 >_{g_1} b_1$ to ensure that $(b_2, g_1)$ is stable.
However $M$ is stable, and $(b_1, g_1) \in M$. Since we have that $b_2 >_{g_1} b_1$, for $(b_1, g_1)$ to be stable, we must ensure that $(b_2, g_1)$ is not a rogue couple, since $g_1$ prefers $b_2$ over $b_1$. This we must have that $g'_1 >_{b_2} g_1$.
But this contradicts the equation $\max{b_2}(g_2, g_2') = g_2' = g_1$ (?)

§ Sid musings

the girls are monotonic filters, where they only allow themselves to match higher.
The propogate (in the kmett/propogators sense of the word) information to all
lower requests that they will not match. The boys are in some kind of atomic
write framework with conflict resolution, where a girl allows a boy to "write"
into her 'consider this boy' state if the boy is accepted by her filter.

§ References

• MIT OCW Math for comp sci: lecture 7 --- matching
• SPOJ problem
• Knuth: Stable matching and its relation to other combinatorial problems
• Math for Comp Sci: Optimal stable matching