# Researchers develop 'envy-free' algorithm for settling disputes

##### February 3, 2014

Whether it's season tickets to Green Bay Packers' games or silver place settings, divorce and inheritance have bred protracted disputes over the assignment of belongings. But, now, a trio of researchers has found a method for resolving such conflicts in an envy-free way.

The paper, authored by New York University's Steven Brams, Wilfrid Laurier University's D. Marc Kilgour, and the University of Graz's Christian Klamler and published this month in Notices of the American Mathematical Society, outlines a pair of algorithms that are based on the self-identified priorities of the parties.

"The problem of fairly dividing a divisible good, such as cake or land, between two people probably goes back to the dawn of civilization," write the authors.

They point out that dividing indivisible goods, like the marital property in a divorce, is harder, adding, "Unlike more demanding fair-division algorithms, which ask players to give more detailed information or make more difficult comparisons, our algorithms are easy to apply and, therefore, eminently practicable."

Their work is based on principles of fairness. In the first algorithm, the two players make simultaneous or independent choices in sequence, starting with their most-preferred items and progressively descending to less-preferred items that have not already been allocated. In the second, the players submit their complete preference rankings in advance to a referee or arbitrator.

This algorithm is "envy free" because each party prefers each of its items to a corresponding item of the other party. A potential conflict arises, of course, when the two parties desire the same item at the same time. For example, assume players A and B rank four items, going from left to right, as follows:

A: 1 2 3 4
B: 2 3 4 1

Now, if we give A item 1 and B item 2 (their most preferred), the next unallocated item on both their lists is item 3. Who should get it? The algorithm gives it to A and gives item 4 to B, which is an envy-free allocation because each player prefers its items to the other player's:

A prefers item 1 to 2 and item 3 to 4
B prefers item 2 to 3 and item 4 to 1

Not only does each party prefer its pair of items to the other's, but there is no alternative allocation that both parties would prefer, which makes it efficient. Although such an efficient, envy-free allocation is not always possible, the algorithm finds one that comes as close to this ideal as can be achieved.

Explore further: Why would consumers pay less for separate than bundled products?

More information: Brams, a professor in NYU's Wilf Family Department of Politics, is the author of Game Theory and the Humanities: Bridging Two Worlds (2011) and Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures (2008), among other works.

## Related Stories

#### Why would consumers pay less for separate than bundled products?

March 15, 2012

Packaging an expensive item with a cheap one seems like a no-brainer. But according to a new study in the Journal of Consumer Research, most consumers in this situation are not willing to pay as much for a combination as ...

#### What determines which sources within an episode are successfully remembered?

October 25, 2013

Memory about a core item (such as a word, object, or picture) is called item memory while memory about the context or related features of a core item is defined as source memory. What determines which sources within an episode ...

#### Get what you want with these three online holiday wish list tools

December 5, 2013

In 2013, kids aren't sending Santa a letter with their wish list. They're emailing him the Web address of their wish list.

#### 'Sequential' pricing can increase retail profits, study finds

April 30, 2013

Business researchers at the University of Arkansas have conducted an in-depth study of "sequential" pricing of retail products in both online and brick-and-mortar stores and found that the ability to set prices based on real-time ...

#### Location, location, location: Study shows the middle is the place to be

August 30, 2011

Choice is a central tenet of a free society. From the brand of cereal we eat for breakfast, to the answers we give on a survey, or the people we select to be our leaders, we frequently define ourselves by the choices we make. ...

#### Buying behavior can be swayed by cultural mindset

July 11, 2013

There are some combinations that just go well together: Milk and cookies, eggs and bacon, pancakes and maple syrup. But new research reveals that people with individualistic mindsets differ from their collectivist counterparts ...

## Recommended for you

#### Game theory research reveals fragility of common resources

September 29, 2016

New research in game theory shows that people are naturally predisposed to over-use "common-pool resources" such as transportation systems and fisheries even if it risks failure of the system, to the detriment of society ...

#### Giant dinosaur footprint discovered in Mongolia desert

September 30, 2016

One of the biggest dinosaur footprints ever recorded has been unearthed in the Gobi Desert, researchers said Friday, offering a fresh clue about the giant creatures that roamed the earth millions of years ago.

#### 3-D printed fish fossil may reveal origin of human teeth

September 30, 2016

Three-dimensional prints of a 400 million year old fish fossil from around Lake Burrinjuck in southeast Australia reveal the possible evolutionary origins of human teeth, according to new research by The Australian National ...

#### From America to Viagra: finding what you're not looking for

September 30, 2016

It's serendipity: from America to Viagra, history is full of great discoveries helped along by chance, as more than a century of Nobel prizes can attest.

#### Humans may have occupied Southern Cone 14,000 years ago

September 29, 2016

Humans may have occupied the Southern Cone 14,000 years ago, according to a study published September 28, 2016 in the open-access journal PLOS ONE by Gustavo Politis from CONICET and the Universidad Nacional del Centro de ...

#### Ancient reptile fossils claw for more attention

September 29, 2016

Newly recovered fossils confirm that Drepanosaurus, a prehistoric cross between a chameleon and an anteater, was a small reptile with a fearsome finger. The second digit of its forelimb sported a massive claw.