§ Matching problems (TODO)

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

§ Perfect matching

A matching is perfect if it has size ∣V∣/2|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 MM. 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 GG 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)(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 MM. 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 MM was not stable.

§ Stable Marriage Problem: success in some cases!

We have NN boys and NN 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 N2+1N^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 N2N^2 days, all boys would have crossed out all girls.

§ Invariant

  • P is that if a girl GG every rejected a boy BB then she has a suitor who she prefers to BB.
  • 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 dd. At the end of day d+1d+1, there's two cases.
  • If GG rejects BB on day d+1d+1, there must be a better boy, hence P is true.
  • If GG rejected BB on day less than d+1d+1, then GG must have had a better suitor B′B'on day dd by the induction hypothesis. Now on day d+1d+1, she either has B′B'or someone even better, B′′B'' came along.

§ Everyone is married

Proof by contradiction. Assume not everyone was married. Assume that some boy BB 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 BB, 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 SS be the set of all stable matchings. We know that SS is not empty because the algorithm is able to produce at least one stable matching.
  • For each person PP, we define the realm of possibility for PP to be the set QQ of people that they can be matched to in a stable matching. So Qp≡{q:(p,q)∈M,M∈S}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⋆,g)(b^\star, g) and (b,g)(b, g). WLOG let gg prefer b⋆b^\star over bb. Now, there exists some "stable matching" where gg is matched with bb, because gg is the optimal mate, hence in the realm of possibility of bb. However, this matching is unstable because (b⋆,g)(b^\star, g) is a rogue couple: gg likes b⋆b^\star more than bb, and b⋆b^\star likes gg 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=((b1,g1),(b2,g2),…(bn,gn))M = ((b_1, g_1), (b_2, g_2), \dots (b_n, g_n)) and M′=((b1,g1′),(b2,g2′),…,(bn,gn′))M' = ((b_1, g'_1), (b_2, g'_2), \dots, (b_n, g'_n)) be two stable matchings. Then.
M∨M′≡((b1,max⁡b1(g1,g1′),…,(bn,max⁡bn(gn,gn′))) M \lor M' \equiv ((b_1, \max_{b_1}(g_1, g_1'), \dots, (b_n, \max_{b_n}(g_n, g_n')))
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 g1=max⁡b1(g1,g1′)=max⁡b2(g2,g2′)=g2′g_1 = \max_{b_1}(g_1, g_1') = \max_{b_2}(g_2, g_2') = g_2'. Since (b2,g2′)(b_2, g_2') is the match in M′M' and g1=g2′g_1 = g_2', we have that (b2,g1)(b_2, g_1) is the match in M′M'. We also know that g1>b1g1′g_1 >_{b_1} g_1' from the assumption. Since the matching M′M' is stable, we need to ensure that (g1,b1)(g_1, b_1) is not a rogue couple; b1b_1 prefers g1g_1 over g1′g_1'. Thus, we must have that b2>g1b1b_2 >_{g_1} b_1 to ensure that (b2,g1)(b_2, g_1) is stable. However MM is stable, and (b1,g1)∈M(b_1, g_1) \in M. Since we have that b2>g1b1b_2 >_{g_1} b_1, for (b1,g1)(b_1, g_1) to be stable, we must ensure that (b2,g1)(b_2, g_1) is not a rogue couple, since g1g_1 prefers b2b_2 over b1b_1. This we must have that g1′>b2g1g'_1 >_{b_2} g_1. But this contradicts the equation max⁡b2(g2,g2′)=g2′=g1\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