This program ran as a java applet which is no longer viewable with current browsers. This page contains historical information. To use the application, please access the New York Times version and view the related article.
A java applet for interactive decision making to find envy-free divisions of goods, burdens, or rent.
The Fair Division Calculator will soon be integrated into ARTUS, a process control system for group decision and negotiation on the Internet. ARTUS is a project directed by Matthias Raith. When the integration is complete, it will be the first analytical mediation support system on the Internet!
What is “Fair Division”?
The theory of fair division is concerned with finding ways to divide an object among n people fairly. There are many possible notions of fairness. The notion that has interested me recently is finding envy-free divisions, i.e., one in which each person feels she received the best piece, in her own estimation.
Exact vs. Approximate Algorithms
Existence of such divisions has been known for some time. Of greater interest are algorithms for achieving such divisions. For instance, in dividing a desirable object, such as cakes, a 2-person algorithm has been known since antiquity, a 3-person algorithm since at least 1960, but an exact algorithm for achieving n-person envy-free cake divisions was not produced until Brams and Taylor’s solution in 1995. (See the references below.) Elisha Peterson and I have recently extended these techniques to provide an exact envy-free chore-division algorithm for n people. However, such methods tend to be quite complicated as n grows large.
By contrast, I have been interested in developing approximate envy-free schemes, in particular, through the use of arguments from combinatorial topology (Sperner, Tucker, and generalizations). Such methods will find envy-free divisions up to a specified tolerance for error (such as at the level of crumbs), and have the advantage of (1) being easily generalized for arbitrary numbers of players, (2) using the minimal number of cuts, (3) for a fixed number of players and a fixed error, having a bounded number of steps in which the algorithm halts. My main inspiration and partner in this endeavor has been Forest Simmons. More recently, my students Elisha Peterson, Patrick Vinograd, and Karl Mahlburg have also been working with me.
To explore such algorithms, we have developed the Fair Division Calculator.
The Fair Division Calculator finds approximate envy-free divisions up to any precision for the following problems:
- cake-cutting (division of goods/desirables),
- chore-division (division of burdens/undesirables)
- rent-partitioning (allocation of indivisible goods mediated by divisible payments)
In a few weeks we’ll have a new algorithm for rent-partitioning (due to Haake-Raith-Su) encoded as an option in the Calculator.
References
Some good references on subject are:
- Brams, Steven J. and Taylor, Alan, Fair Division: from cake-cutting to dispute resolution, Cambridge Univ. Press, 1996.
- Robertson, Jack and Webb, William. Cake-cutting Algorithms. AK Peters Ltd., 1998.
See also the link to my papers. Or see also Elisha’s research page.
Recognitions
- Site of the Week (12-14-1999) by the Canadian Math Society!
- Also featured in a 1-7-2000 article in Science (p.37) and a 12-16-1999 story in the online publication ScienceNow.
- Featured in a 1-31-2000 interview for the radio show ScienceUpdate.
- Featured in a 2-26-2000 article “A Fair Deal for Housemates” in ScienceNews.
- Featured in Ivars Peterson’s MathTrek article on 3-11-2000 in ScienceNewsOnline.