The Fair Division Calculator v.2.5
This is not the most recent version. You can see the most recent one by going to the main Fair Division Page.
Instructions below

This applet is optimized for use with MS Internet Explorer.
Bug report: the applet does not seem to work properly on Macs with Netscape 4.0.

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), 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.

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. However, bear in mind that the Auto-Choose option (like all bidding procedures for rent division) assumes that preferences over money are linear. If you cannot make this assumption, you should run the algorithm interactively.
  • In a few weeks we'll have a new algorithm for rent-division (due to Haake-Raith-Su) encoded as an option in the Calculator. Then the [HRS] button will become active.

The algorithm homes 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
Last modified: September, 1999