A Better Way To Slice The Pie
Ariel Procaccia
Splitting a check, an inheritance or credit for an idea are activities of daily life that are filled with potential pitfalls.
Computer scientists at Carnegie Mellon University hope to minimize unwelcome outcomes through a new website, Spliddit.org, that offers "provably fair" solutions to everyday dilemmas.
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 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 site 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 his or her 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.
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. 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.
This work was supported by the National Science Foundation and Amazon.
Related Links: School of Computer Science