Algorithm helps to find ‘envy-free’ solutions

Kilgour and co-authors has developed an algorithm to help divide items fairly. (Photo by: Jessica Dik)

Kilgour and co-authors has developed an algorithm to help divide items fairly. (Photo by: Jessica Dik)

If you thought all of the useful, life-applicable math skills were learned in your elementary school years, then take a look at the work Marc Kilgour, chair of the department of mathematics at Wilfrid Laurier University, has been doing. Kilgour is one of the minds behind a new algorithm that is now being heralded as “the divorce algorithm,” proving that math can help provide solutions in more areas of life than many might realize.

“That’s what I like to do,” said Kilgour. “I like to find solutions to problems and we see math problems every day in our daily lives.”

Kilgour and co-authors Steven Brams from New York University and Christian Klamler from the University of Graz have published a paper in the Notices of the American Mathematical Society about their work on the algorithm.

“It’s a division formula for non-divisible items where two people have an even list of items that they want, but they each value each item differently,” explained Kilgour.

The algorithm involves both parties ranking the items they want from most to least. From this information, it produces an envy-free solution of how the items should be divided.

“And here ‘envy-free’ means that each person is happier with what they got than what the other person got,” said Kilgour.

The algorithm could be used for any situation where two people want to divide items of differing values, whether dividing assorted candies between children or dividing possessions in a divorce.

Kilgour uses the example of a divorce scenario where Jill and John each want the boat, the car, the dog and the couch – but value each differently – to explain how his algorithm would come up with a solution of who gets what.

“It’s an example I use because the algorithm can only be used when dealing with two people,” continued Kilgour. “But that would change once we are able to come up with a way to make [the algorithm] work with a larger number.”

Kilgour and his co-authors had considered patenting the algorithm, but Kilgour explained that there is more work to be done.

“The algorithm needs to be faster. It’s a very useful piece of work, but in order to be used at a professional capacity, it would need to be faster and it is not there yet.”

Because the algorithm is currently set for only two people, its use for a divorce scenario is the most obvious and, according to Kilgour, this is why it has earned its nickname as the “divorce algorithm.”

“I’m not sure how accepting people would be of a computer dividing up their desired items,” said Kilgour. “But it could erase any feelings of bias or that sides are being taken if a computer is providing a result based on what the information they put in.”

For now, Kilgour and his colleagues will continue to work on the algorithm to make it more adaptable to a variety of scenarios.

“It’s hard to say if people will accept [this algorithm],” said Kilgour. “But I’m doing this because I like solving problems and a big part of people’s lives involves division kinds of problems.”

Leave a Reply