Headlines (News Releases)
Faculty of Science
John gets the dog; Jill gets the couch. Laurier researcher’s algorithm helps avoid envy when dividing ‘indivisible items’
Communications, Public Affairs & Marketing
Feb 11/14| For Immediate Release
Marc Kilgour, Professor and Chair
Lori Chalmers Morrison, Acting Director
WATERLOO – Almost everyone has heard of a couple going through a rather messy divorce. Often, the cause of that unpleasantness is jealousy over who gets what when the couple’s property is divided.
According to a recent paper authored by a team of researchers, including Marc Kilgour of Laurier’s Department of Mathematics, one way to avoid such disputes is to use a mathematical algorithm.
In the paper, which was recently published in the prestigious Notices of the American Mathematical Society, Kilgour and his co-authors — Steven Brams of New York University and Christian Klamler of the University of Graz — outline a pair of algorithms that can be used to divide “indivisible” items between parties without causing envy, if it’s possible to do so.
While things like land can be fairly divided by allocating each party shares they value equally (like saying “I cut, you choose” when cutting a cake), things like cars, furniture, art or personal keepsakes cannot simply be divided equally because the items cannot be split, in addition to having different perceived values to each person. The researchers’ algorithms address this situation by asking each party to rank the items from most preferred to least preferred, without giving additional information.
Both algorithms proceed by assigning each party the items at the top of their preference rankings. If the same item is ranked highest by both parties, the first algorithm does not assign it, while the second algorithm dictates that each party’s list of ranked items be analyzed by an independent third party, or computer, to determine whether the item can be assigned in a way that avoids envy.
“It’s part of our procedure to avoid envy, which means feeling like the other person got more than you,” said Kilgour. “There are two criteria of fairness: proportionality, which means you feel like you got at least your share of the total, and envy-freeness, which means that you’d rather have your items than the other person’s. If there are only two people, these criteria are exactly the same.”
By ranking items, and using the second algorithm to resolve conflicts when both parties have the same preference for an item, the parties have a good chance of finding a way to allocate the items so that each prefers the items they receive to the ones given to the other party.
For example: John and Jill are trying to fairly allocate four items: their car, their couch, their boat and their dog. Their preferences for the four items are as follows, John: car, boat, dog, couch; Jill: boat, dog, couch, car. In the first step, John receives the car while Jill receives the boat. But then conflict arises, because the next item both parties desire is the dog.
According to the second algorithm, John would receive the dog and Jill the couch. This is the only way to create an envy-free situation because both parties would prefer their items to the other party’s (John prefers the car to the boat and the dog to the couch, while Jill prefers the boat to the dog and the couch to the car).
Although envy-free allocations are not always possible, the second algorithm will produce such a solution whenever one is available. And while dividing property after a divorce or for an inheritance are the most obvious uses for the algorithms, Kilgour believes their use could go far beyond those two scenarios.
“Any distribution of resources is allocation. If you own a timeshare on a vacation property, you and the other owners have to divide up the vacation season,” he said. “Any time an organization has resources and lots of places to apply them, they’ll generally want to do it in a way that fairly reflects the sub-units’ goals, as well as the organization’s. But what is fair, and how do you achieve it? That kind of issue makes this an area of study that could have many uses.”