§ Matching problems (TODO)
Given a graph a matching is a collection of edges of where every
node has degree 1.
§ Perfect matching
A matching is perfect if it has size , 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 . 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 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, 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 . 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
Hence, we found a rogue couple. So was not stable.
- 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.
§ Stable Marriage Problem: success in some cases!
We have boys and 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 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 days, all boys
would have crossed out all girls.
P is that if a girl every rejected a boy then she has a suitor who she prefers to .
- 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.
P holds at the end of day . At the end of day , there's two cases.
- If rejects on day , there must be a better boy, hence
P is true.
- If rejected on day less than , then must have had a better suitor on day by the induction hypothesis. Now on day , she either has or someone even better, came along.
§ Everyone is married
Proof by contradiction. Assume not everyone was married. Assume that some boy 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 , 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.
- 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 be the set of all stable matchings. We know that is not empty because the algorithm is able to produce at least one stable matching.
- For each person , we define the realm of possibility for to be the set of people that they can be matched to in a stable matching. So . 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 and . WLOG
let prefer over . Now, there exists some "stable matching" where
is matched with , because is the optimal mate, hence in the realm
of possibility of . However, this matching is unstable because
is a rogue couple: likes more than , and likes 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
- Proof from Optimal Stable Matching Video, MIT 6.042J Mathematics for Computer Science, Spring 2015.
§ We match every girl with her pessimal mate
§ Theorem: matchings form a lattice
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 .
Since is the match in and , we have that
is the match in . We also know that from the assumption.
Since the matching is stable, we need to ensure that is not a
rogue couple; prefers over . Thus, we must have that
to ensure that is stable.
However is stable, and . Since we have that ,
for to be stable, we must ensure that is not
a rogue couple, since prefers over . This we must have
But this contradicts the equation (?)
§ 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.