Tuesday, November 4, 2014
Carnegie Mellon Project Uses “Provably Fair” Methods To Help People Split Rent, Divide Goods, Share Credit
Spliddit Website Leverages 70 Years of Fair Division Research Beyond “I Cut, You Choose”
By Byron Spice / 412-268-9068
PITTSBURGH—The need to divide things among people is an aspect of daily life filled with potential pitfalls. Whether the deal involves land, an inheritance or credit for an idea, a split perceived as unfair can lead to war, personal feuds, or silent, seething resentment.
Computer scientists at Carnegie Mellon University hope to minimize such unwelcome outcomes through a new website, Spliddit.org, that offers “provably fair” solutions to everyday dilemmas — how to split rent, divide goods or apportion credit for a project. The site employs the latest mathematical and theoretical approaches to these problems, but site visitors won’t need an advanced degree to use them.
Ariel Procaccia, an assistant professor of computer science who leads the Spliddit project, said finding ways to divide things without inciting envy has been a busy area of research among economists, mathematicians and computer scientists since at least the 1940s. But until now, the average person hasn’t had ready access to these advanced algorithms.
“People have worked hard to solve these problems in provably fair ways,” said Procaccia, whose research focuses on the interface between computer science and economics. “It’s sort of surprising that nobody has previously implemented these algorithms so that they could be used by society at large.”
Dividing a cake using the “I cut, you choose” method is the classic example used to illustrate envy-free approaches. But even cake cutting can get mighty complicated, as the number of people sharing increases and as the division begins to account for additional factors — people who prefer icing to cake, people who prefer chocolate over vanilla, those who like cake decorations, etc.
So when it comes to splitting rent, Spliddit does more than just divide the monthly rent by the number of roommates. The sites uses a method based on work by researchers currently at Duke University and Boston College that includes asking each roommate to specify how much each bedroom is worth to them. Each can use their own criteria — size of room, closet space, size and number of windows, etc. The algorithm then recommends who should occupy which room and how much each should pay.
“The hope is that we will give them a solution and they’ll say, ‘Yeah, that seems about right,’” Procaccia said. But he’s well aware that won’t happen in every case. “If 50 or 60 percent of the users actually use the solution we provide, I see that as a big win.
“We want to show people that math can be beautiful and useful,” he added.
Procaccia acknowledged that in some cases, even the best mathematics can’t make everyone happy. For dividing goods, such as inheritances or other items that may have sentimental value, these methods sometimes may only be able to guarantee that everyone gets some of what they want, even if not everyone feels satisfied with the result.
Spliddit’s method for dividing goods is based on Procaccia’s own research. As part of the process, the website computes each participant's “maximin” share, which is a lower boundary for what the participant would receive if he were to divide the goods into bundles and the other participants could choose their bundles first. In many cases, the method is able to give each participant their maximin share, but only guarantees them two-thirds of the maximin share.
As part of the research project, Procaccia plans to do happiness surveys to see if people find the proposed solutions worthwhile and whether they strike the right balance between fairness and social welfare. But simply implementing the algorithms in an easy-to-use interface was a research challenge of its own, he added.
“It's an incredibly difficult project, which involves deep mathematics and cloud computing,” Procaccia said, noting that Jonathan Goldman, a senior computer science major, did the bulk of the work to get the site up and running. “It’s really amazing work by an undergraduate,” he added.
Goldman said people already are finding new ways to use the applications, such as a teacher who is employing the credit-sharing app for group projects by his students, and suggesting new applications, such as dividing work shifts at hospitals or grouping students for projects, which will guide further development of Spliddit.
This work was supported by the National Science Foundation and Amazon.
Computer scientists at Carnegie Mellon have created a new website, Spliddit.org, that employs the latest mathematical and theoretical approaches to offer solutions to everyday dilemmas, such as splitting rent fairly among roommates.