Splitting the Rent, Keeping the Peace

It could be an episode on MTV's "The Real World": Four friends move into a house that has four rooms of different sizes. It doesn't seem fair for them all to pay the same rent. Is there some way to divvy up the rent so that nobody feels short-changed? Unfortunately for lovers of drama and conflict, mathematicians have now proven that an "envy-free" distribution of rent always exists--and they've written a computer program that finds it.

Francis Su, a mathematician at Harvey Mudd College in Claremont, California, began thinking about the rent-division problem when a friend found himself in the situation just described. He knew about a similar conundrum, called the "cake-cutting problem," in which several people try to divide a cake in a way that makes everyone happy. When there are two people, the solution is easy: One person cuts the cake, the other chooses, so neither can claim they got a bad deal. In 1992, New York University political scientist Steven Brams and Union College, New York, mathematician Alan Taylor devised the first envy-free method that works for any number of people. Their approach, however, is not very practical: It might require billions of cuts. "It would decimate the cake when you're done," Su says.

For the rent-division problem, Su figured it would be good enough to produce a solution that was nearly, if not absolutely, envy-free. His Fair Division Calculator works by repeatedly quizzing each roommate on which room they would choose if the rents were divided in certain ways. Over many iterations, the scheme gets closer and closer to a division that everyone is happy with. Though it's a simple idea, the hard part is proving mathematically that it always works. The crucial ingredient of the proof is a result from combinatorial topology called Sperner's lemma, a method for solving complex sets of equations that the researchers lay out in this month's issue of American Mathematical Monthly.

"People ask me, couldn't you get away with more if you didn't answer the questions truthfully?" Su says. "The answer is yes, but if you're truthful you're guaranteed an envy-free solution, even if everyone else lies." The only case in which the algorithm fails is if there is a room so bad that one of the roommates won't even take it for free. (In that case, Su suggests looking for a less picky roommate.)

Mathematicians say the method should be applicable to many conflict-resolution systems other than rent division. "To me, the interesting thing about it is the philosophy," says Michael Starbird, a mathematician at the University of Texas, Austin. "Instead of arguing with one another about value systems, you declare your own value system and let a third party find a middle way."

Posted in Math