Carnegie Mellon Project Divides Everyday Tasks, Expenses In Ways Scientifically Calculated To Make Everyone Happy-CMU News - Carnegie Mellon University

Tuesday, April 28, 2015

Carnegie Mellon Project Divides Everyday Tasks, Expenses In Ways Scientifically Calculated To Make Everyone Happy

Spliddit.org Site Implements a Nobel Laureate’s Insights To Split Cab Fares

By Byron Spice / 412-268-9068 / bspice@cs.cmu.edu

The next time you share a cab, get a little help on splitting the fare from a Nobel laureate in economics. That’s possible as of today through Carnegie Mellon University’s Spliddit.org website, which offers “provably fair” solutions to everyday dilemmas.

The free, not-for-profit website, which launched last fall to provide help in dividing rents, sharing credit on work and for splitting inheritances, is adding two new services today: how to divide up chores or work shifts and how to fairly divide cab fares. Like the previous Spliddit services, the new ones leverage decades of academic research on how to divide things equitably and without rancor.

SplidditThe cab fare division app, for instance, is based on a concept called the Shapley value, named for Lloyd Shapley, who won the 2012 Nobel Prize in economics for his work on stable allocations and market design. Shapley value considers the marginal contributions of each person in a game or endeavor. In the case of a cab ride, it considers the distance to each person’s address and their proximity to each other.

For three riders, for instance, the app would estimate the cost of each rider alone, of each of the three possible pairs of riders, and of all three riders together. It would then calculate each rider’s average marginal contribution to the total fare and divide it accordingly.

“This is a concept that has been around since 1953 and, though it has been studied in thousands of research papers, this is the first time to my knowledge that it has ever been implemented in a publicly available service,” said Ariel Procaccia, an assistant professor of computer science who leads the Spliddit project.

Dividing a cake using the “I cut, you choose” method is the classic example used to illustrate the type of envy-free approaches to division that Spliddit employs. But finding algorithms that apply to a wide variety of situations and to larger numbers of people requires more elaborate algorithms and calculations.

Spliddit has had almost 40,000 unique users since it launched last November. One of the new services that begins today — distributing tasks — is in response to user feedback, Procaccia noted. Most of these requests came from health care workers, such as doctors and nurses, who have to be scheduled to fill a variety of day, night and holiday shifts.

The new task distribution service asks members of a group to identify their preferences for shifts or days, or for specific household or workplace tasks, and to quantify that preference. Someone with a preference for day shifts, for instance, might indicate she would be willing to work 1½ or two day shifts for every night shift. Or, someone might be willing to wash the dishes three times if it meant not mowing the lawn.

Procaccia said the site can then allocate tasks or shifts as fairly as possible; though some people may get a slightly less satisfactory allocation than others, those inequalities tend to balance each other out when the process is repeated on a weekly schedule or some other regular basis.

In its first six months, Spliddit has proven popular with teachers and professors, who look for ways to equitably divide credit and assign grades to group projects by students, Procaccia said. Improvements have been made to the site based on user feedback, including the addition of live demonstrations for each app, and some changes in the algorithms used to divide rent or goods.

Jonathan Goldman, a computer science major, has worked with Procaccia to develop Spliddit’s algorithms and interfaces as part of his senior research thesis.

This work was supported by the National Science Foundation and Amazon.

Procaccia is a faculty member in the Computer Science Department, a unit with the School of Computer Science. Follow the school on Twitter @SCSatCMU.