- News Home
27 November 2013 12:59 pm ,
Vol. 342 ,
The new head of the National Center for Science Education promises to "fight the good fight" against attacks on...
Analyses of the H7N9 strains isolated from four new cases show that the virus is evolving rapidly, heightening anxiety...
In 2009, Jack Szostak shared a Nobel Prize for his part in discovering the role of telomeres, the end bits of...
Science has exposed a thriving academic black market in China involving shady agencies, corrupt scientists, and...
Paper-selling agencies flourish in the aura of reputable businesses. For some scientists, it may be difficult to tell...
Data collected by satellites and floating probes have chronicled a 2-decade rise in the temperature and thickness of a...
Cholesterol, the artery-clogging molecule that contributes to cardiovascular disease, has another nasty trick up its...
Until recently, the Defense Advanced Research Projects Agency (DARPA) kept its plans for its $70 million portion of the...
- 27 November 2013 12:59 pm , Vol. 342 , #6162
- About Us
Splitting the Rent, Keeping the Peace
16 December 1999 6:00 pm
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."