New York University Skip to Content Skip to Search Skip to Navigation Skip to Sub Navigation

Researchers Develop “Envy-Free” Algorithm for Settling Disputes from Divorce to Inheritance

February 3, 2014
188

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.

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.

This Press Release is in the following Topics:
Arts and Science, Research, Faculty

Type: Press Release

Press Contact: James Devitt | (212) 998-6808

Researchers Develop “Envy-Free” Algorithm for Settling Disputes from Divorce to Inheritance

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. ©iStockPhoto.com/milosducati


Search News



NYU In the News

CUSP Unveils its “Urban Observatory”

Crain’s New York Business profiled CUSP’s “Urban Observatory” that is continuously photographing lower Manhattan to gather scientific data.

Post-Sandy Upgrades at the Langone Medical Center

NY1 reported on the major post-Sandy upgrades and renovations made at the Medical Center to protect the hospital from future catastrophic storms.

Steinhardt Research Helps Solve Tough Speech Problems.

The Wall Street Journal reported on research at Steinhardt’s Department of Communicative Sciences and Disorders, including an interview with Assistant Professor Tara McAllister Byun, that uses ultrasound to help solve tough speech problems.

Times Column Lauds Professor Stevenson’s New Memoir

New York Times columnist Nicholas Kristof wrote a column about “Just Mercy,” a new memoir by Law Professor Bryan Stevenson, the founder of the Equal Justice Initiative, whom he noted has been called America’s Nelson Mandela.

Entrepreneurship Lab Opens at NYU

Crain’s New York Business covered the opening of the Mark and Debra Leslie Entrepreneurial eLab, which will be the headquarters for NYU’s Entrepreneurial Institute and all of the University’s programs aimed at promoting innovation and startups.

NYU Footer