Researchers develop 'envy-free' algorithm for settling disputes

Feb 03, 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: What determines which sources within an episode are successfully remembered?

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

Buying behavior can be swayed by cultural mindset

Jul 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

Newlyweds, be careful what you wish for

2 hours ago

A statistical analysis of the gift "fulfillments" at several hundred online wedding gift registries suggests that wedding guests are caught between a rock and a hard place when it comes to buying an appropriate gift for the ...

Can new understanding avert tragedy?

5 hours ago

As a boy growing up in Syracuse, NY, Sol Hsiang ran an experiment for a school project testing whether plants grow better sprinkled with water vs orange juice. Today, 20 years later, he applies complex statistical ...

Crowd-sourcing Britain's Bronze Age

5 hours ago

A new joint project by the British Museum and the UCL Institute of Archaeology is seeking online contributions from members of the public to enhance a major British Bronze Age archive and artefact collection.

Roman dig 'transforms understanding' of ancient port

5 hours ago

(Phys.org) —Researchers from the universities of Cambridge and Southampton have discovered a new section of the boundary wall of the ancient Roman port of Ostia, proving the city was much larger than previously ...

User comments : 0

More news stories

Newlyweds, be careful what you wish for

A statistical analysis of the gift "fulfillments" at several hundred online wedding gift registries suggests that wedding guests are caught between a rock and a hard place when it comes to buying an appropriate gift for the ...

Can new understanding avert tragedy?

As a boy growing up in Syracuse, NY, Sol Hsiang ran an experiment for a school project testing whether plants grow better sprinkled with water vs orange juice. Today, 20 years later, he applies complex statistical ...

Crowd-sourcing Britain's Bronze Age

A new joint project by the British Museum and the UCL Institute of Archaeology is seeking online contributions from members of the public to enhance a major British Bronze Age archive and artefact collection.

Roman dig 'transforms understanding' of ancient port

(Phys.org) —Researchers from the universities of Cambridge and Southampton have discovered a new section of the boundary wall of the ancient Roman port of Ostia, proving the city was much larger than previously ...

Tiny power plants hold promise for nuclear energy

Small underground nuclear power plants that could be cheaper to build than their behemoth counterparts may herald the future for an energy industry under intense scrutiny since the Fukushima disaster, the ...

Unraveling the 'black ribbon' around lung cancer

It's not uncommon these days to find a colored ribbon representing a disease. A pink ribbon is well known to signify breast cancer. But what color ribbon does one think of with lung cancer?