Some splits are easy: if you’re with a group of friends at a restaurant, you total up what you ordered at the end of the night and pay your share.
But how do you fairly divide up the rent among roommates in an apartment with different-sized rooms? Who gets listed in what order as authors on an academic paper? How about dividing up the treasures Grandma left behind?
A Carnegie Mellon computer scientist is trying to provide answers to those questions with a new website called “Spliddit.”
Ariel Procaccia, an assistant professor in the computer science department, came to CMU in 2011 after earning his Ph.D. at the Hebrew University of Jerusalem and doing post-doctoral work at Harvard University and Microsoft. Along the way, he became fascinated by the thorny issue of “fair division.”
“It’s a pretty amazing field,” he says. “It has a huge collection of genius methods for solving practical problems. There’s a lot of mathematical theory about how to do this stuff … but it’s never been implemented, which is sort of what set the stage for Spliddit.”
Working with a CMU undergraduate, Jonathan Goldman (CS’15), Procaccia began focusing on three areas in which fair division could be applied to real-world problems.
“The idea behind Spliddit is this idea of provably fair solutions, where for every method that we use, we can give a hard fairness guarantee,” he says. Of those three initial Spliddit projects—rent division, credit division and splitting up goods—he says dividing up physical objects turned out to be the most challenging.
“Some of the classic fairness notions are just clearly impossible when you have indivisible goods,” Procaccia says. “So things like ‘envy freedom,’ for instance, where I prefer my bundle of goods to the bundle of goods allocated to any other player, that’s something you can’t always guarantee. If there’s only one good and two players and you give the good to one of the two players, the other one would be envious.
For example, he says, “if you had two players and two goods, if one good is a diamond and the other is a piece of garbage, you can’t prevent the guy who didn’t get the diamond from envying the guy who got the diamond.”
Ideally, Procaccia says, the algorithm would guarantee each player the equivalent of a maximum share guarantee—“as much as he could guarantee to himself if he divided up the goods and others chose.” While Spliddit can’t do that, it can guarantee each player a bundle that’s worth at least two-thirds of that “maximum share guarantee.”
For Spliddit’s other projects, the guarantees are stronger. Procaccia’s rent-division algorithm, for instance, starts with the assumption that there are an equal number of rooms and prospective renters. The Spliddit website asks each renter to move a series of sliders to say how much they’d pay at most for each of the rooms, with the total adding up to the full rent for the apartment. The Spliddit algorithm then goes to work, guaranteeing that the assignment of rooms and division of rent is envy-free: Each renter likes her room for the price she’s paying better than any other room for the price of that room. In particular, the renter in a windowless back room pays less than the one who gets the big room with the window in front, and the prices are configured such that no one has a reason to be jealous of the other.
Procaccia admits that the projects Spliddit has carried out so far are all part of an academic lifestyle, and none more so than its third algorithm, which tries to divide credit for work projects such as academic papers. The Spliddit credit-division algorithm requires at least four participants, and it works by asking each contributor to ignore his or her own effort and instead assess how much each of the other colleagues contributed to the final product. The algorithm then assigns each contributor a share of the credit—no small task in the world of academia.
“One property this method satisfies is the property of impartiality, which means that your report can’t affect your share of the credit,” Procaccia says. He says the credit-division algorithm has produced the most interesting new real-world applications of all of his Spliddit work so far.
“Initially, I was thinking of (credit-sharing) in the academic context, but then a lot of people reached out specifically about this application and asked, for example, can I use it for class projects? Some people have asked about splitting bonuses in their company according to how different people contributed. And the answer is definitely ‘yes.’”
With money at stake in each of those applications, it would be easy to imagine Spliddit being part of a commercial startup. But Procaccia isn’t looking to make money from the work. Instead, he’s adamant about keeping it all non-commercial. The Spliddit site (spliddit.org) offers real-world use of all three algorithms for free, using computational power sponsored by Amazon. A National Science Foundation grant paid for professional website design, while Goldman has been working on its implementation—“just for his fun and out of interest,” says Procaccia—for nearly three years.
Procaccia, who was awarded a Sloan Research Fellowship in February 2015 for his artificial intelligence work, says he’s working on at least two more Spliddit algorithms that he hopes to add to the website soon.
Just don’t ask him about dividing up those restaurant checks. Because each diner’s bill should track back directly to what they ordered, Procaccia says that’s a problem of simple calculation, not of fair division, and there are already plenty of apps for that.
“The idea behind Spliddit is not about doing the calculation for you,” he says. “It’s about using a fair method that you probably wouldn’t have thought about yourself. It’s really bringing to bear the research in fair division.”
—Scott Fybush is a Rochester, N.Y., based freelance media consultant, writer and broadcaster.
Jason Togyer | 412-268-8721 | firstname.lastname@example.org