Saturday, February 14, 2009

Valentine's Day Math

(The Stable Marriage Problem, in other words.)

I was recently reminded of this fun problem from Combinatorics, which was my favorite math class in college. The goal is to match N men with N women in such a way that no man and woman would both prefer to be married to each than to their assigned spouse (ie, it is a stable matching). There's a simple algorithm for this, invented by Gale and Shapley:

Each round, every single man proposes to his favorite woman who has not previously rejected him. The women collect and consider all these offers, and accept their favorites. If a woman has already accepted another proposal, this engagement is broken off, and that man becomes single again. This continues until everyone is paired up (which necessarily happens, since eventually every man can propose to every woman.)

Notice three properties of the resulting matching:
  1. It is stable. If there existed a man and woman in the final matching who wanted to have an affair, then that man would have proposed to that woman before his actual spouse, and that woman would have accepted.
  2. The men are paired with their favorite women that they could possibly be paired with in a stable matching. If this were not true, then there is some man M1 who is the first man to be rejected by his favorite feasible wife, W1. Say she rejected M1 in favor of another man, M2. Since men propose in order of preference, and M1 is the first man to be rejected by his favorite feasible wife, M2 must prefer W1 to any of his feasible wives. But in that case, in the stable matching (existent by hypothesis) in which M1 marries W1, W1 prefers M2 and M2 prefers W1 to W2. This contradicts the definition of stable.
  3. The women are paired with their least favorite man that they could possibly be paired with in a stable matching. This is true since if M1 is married to W1 in the algorithm, and in some other stable matching, M1 is married to W2 and W1 is married to M2, then by fact 2, we know M1 prefers W1 to W2, and therefore W1 must prefer M2 to M1 or otherwise that other matching wouldn't be stable.
The moral of the story is obvious.

But, now let's abandon traditional gender roles and sexual orientation and consider the PC version of the puzzle, say the Stable Life Partnering Problem. Now we have N people, all of whom might like to marry any of the other people, and each person chooses at the beginning whether s/he wants to be an asker or an askee. The trick is, asker's can now also be asked. I'm not sure what an easy fix for this would be. The problem is, in any round, an asker of course prefers to get a "yes" from their askee than to say yes to any other offer made to him. But then you can have a cycle of askers proposing to each other, and everyone is waiting for the person downstream to respond before accepting or rejecting other offers. There needs to be different rules for timing to make the problem tractable. Any ideas? (If asker's can't ask other askers, of course this boringly devolves into the other problem.)

(By the way, Happy V-day to all others whose revealed preferences rank writing about math over going out for the holiday =)

Friday, February 6, 2009

football meets economics

Slate had an interesting article recently about proposed changes to an overtime rule in the NFL, specifically, how it is decided which team gets the first possession. This paper on the subject makes the point more formally, for those who, like me, prefer their stories with a side of math. The analysis leaves out some considerations, however, that I think should change the conclusion.

Currently, a coin flip determines who gets the first possession, and a kick-off by the other team determines the initial field position. As overtime is decided by sudden death, the team with first possession has an advantage: they win in overtime in the last ten years more than 60% of the time. (Interesting, the historical average is lower. But better offensive drives have pushed up the advantage.) This coin-flip determination is thus nonideal, although there is no ex ante advantage for either team, because the probability of winning is randomly decided.

Two solutions to this unfairness are proposed. One is the simple fair-division mechanism familiar to any rival siblings: one chooses a split, and the other chooses which side to take. That is, one team would choose an initial field position, and the other team would choose whether to play or defend from that position. The "fair" position would depend on the teams involved of course, and it would take a couple seasons for teams to work out the best strategy, but the average fair position is estimated to be 15-20 yards. Also, note that any improvement in offense will never push the fair position as far back as the 0 yard line, since the probability of giving up a safety enforces this lower bound. (The paper makes this assumption explicitly, but for some reason does not point out this reason for its realism.)

The imperfection in this mechanism arises from imperfect information: The choosing team knows its strengths better than the dividing team, so the dividing team is at a disadvantage. A different mechanism, based on auctions, does better in this respect. In this rule, each team "bids" on field position, and the one willing to take possession closer to their own goal gets the ball at some compromise between the bids of the two teams. This is a perfectly symmetric rule, and thus favored by the economists and by the guys who wrote to the NFL to try to get the rule changed.

My first objection to this conclusion is that a little bit of unfairness in the divide-and-choose scheme is ok. It's true that if a coin toss determines which team divides and which chooses, this introduces an arbitrary element into the game. But, instead of introducing additional arbitraryness, the asymmetry could be used to counteract an arbitrary advantage that already occurred: the coin flip at the beginning of the game to assign first possession. The winner of that coin flip had a small advantage, and thus if the game ends up tied, they played slightly worse. They should thus be forced to divide the field and allow the other team to choose possession in overtime. Both advantages are small, so cancelling them out in this way should be a nearly perfect resolution.

My second objection is to the pragmatic details of the implementation of an auction rule. There are several ways it could be done, as listed by the guy, Quanbeck, who tried to get the rules changed. First is a live dutch auction, then an ascending live auction, and last a sealed bid auction. The last way is just boring. The first two ways would of course cause the coaches to plan ahead what yard they would seize or concede possession at, but in a live auction format, they would also try to read each other's body language for subtle clues and adjust their strategy on the fly. This puts too much visible responsibility on the coach, when it's better for the game if the players are the ones responsible for their fate and the coaches stay on the sidelines. Additionally, can you picture a non-trivial pause in a super-tense hard-fought violent game for a geeky field-position auction exercise? Quanbeck can, but he's an electrical engineer =) A divide-and-choose rule would take no longer than the coin toss, and make a lot more sense to the masses.