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,
and Karl Mahlburg have also been working with me.
To explore such algorithms, we have developed:
A java applet for interactive
decision making to find envy-free
divisions of goods, burdens, or rent.
Click on The
Fair Division Calculator
which has recently been updated! (version 2.5, 9/19/99)
The Fair Division Calculator finds approximate envy-free divisions
up to any precision for the following problems:
cake-cutting (division of goods/desirables),
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.
chore-division (division of burdens/undesirables)
rent-partitioning (allocation of indivisible goods mediated
by divisible payments)
Some good references on subject are:
See also the link to my papers.
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
Comments? Write me, Francis Su,
Math Department |
My Home Page |
Main Fair Division Page
Last modified: August 18, 1998