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 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: 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: See also the link to my papers. Or see also Elisha's research page.

Comments? Write me, Francis Su, at su@math.hmc.edu.
Back to...
| Math Department | My Home Page | Main Fair Division Page
Last modified: August 18, 1998