The Fair Division Calculator   v.3.0 Instructions below. This applet is optimized for use with MS Internet Explorer. (For Macs running Netscape, the buttons are slow to respond. We believe the fault lies with the Netscape browser, so on Macs you should try another browser.) The old version is available here.

This calculator will help you determine how to divide among n people:
a desirable object (such as a cake),
an undesirable object (such as a set of chores),
or a set of indivisible objects (rooms, desirable) with payments (rent, undesirable).

If you saw my Amer. Math. Monthly article (Dec.'99), the Sperner routines in this applet uses a more sophisticated "trapdoor" algorithm than was discussed in that article (this one uses a "homotopy" algorithm, with Kuhn triangulation). It changes the mesh size as you go along, allowing one to converge on solutions with finer and finer precisions. The procedures used in this applet are discussed in the following papers:

Both are available on my papers/preprints page.

Instructions:

• Players are named A, B, C, ...
• The applet will suggest divisions and successively ask players which portion she would prefer.
• After polling several players though various scenarios, the "Suggest Division" button will light up. When it does, press it to see an approximate solution, good up to the displayed precision.
• Press "Continue Iteration" to run the algorithm longer and obtain solutions with better precision.
• For the rent problem, players have an option to run the algorithm interactively, or on "Auto-Choose", which will run the program by itself based on bids that players submit for each room. There is also a new feature (4/3/00) that runs the HRS algorithm. It locates an envy-free and efficient solution based on bids, and mimics a natural mediation process (and can be carried out without computer support).
• However, bear in mind that the Auto-Choose or HRS options (like all bidding procedures for rent division) assume that preferences over money are linear. If you cannot make this assumption, you should use the Interactive Sperner option.
 The algorithms based on Sperner's lemma home in on an envy-free division of cakes, chores, or rent. The advantage of this approach for cakes or chores over exact methods is that this procedure minimizes the number of cuts (for exact methods the number of cuts is unbounded and can decimate the cake). The difference between this and other approaches to the rent problem is that this procedure will work for highly non-linear preferences. Forest Simmons and I have been working to develop approximate algorithms for fair division problems using Sperner's lemma and related combinatorial theorems. This particular version of the FDC uses an algorithm which improves upon the basic "trapdoor" algorithm that was outlined in my paper: "Rental harmony: Sperner's lemma in fair division".  In our new algorithm (to be described in a future paper), the precision generally increases with each step.    Related work is also available on my preprint page. Notes: For cake/chore division, you may click on the graphic to select portions.  The graphics are for demonstrative purposes only--- if you are using this to divide your own goods/burdens, you will of course have your own object in mind. For Mac users, the preferred browser is MS Internet Explorer. The windowing will slow down if the buffer gets too large; if this happens, press the "Clear" button. Click here to return to the main Fair Division Page

Thanks to Patrick Vinograd for his extraordinary work on recent versions of the FDC, and Elisha Peterson for developing the charter version.

Thanks to a lot of work by Patrick Vinograd and Helge Wilker, the Fair Division Calculator will soon be integrated into ARTUS, a process control system for group decision and negotiation on the Internet, directed by Matthias Raith. When complete, it will be the first analytical mediation support system on the Internet!

Back to...
| Math Department | My Home Page | The Fair Division Page