Fair Division: The Fair Division Calculator

The Fair Division Calculator(version 1.0)

This is NOT the most recent version.
There's an updated Fair Division Calculator on The Fair Division Page.

This calculator will help you determine how to divide several kinds of things fairly 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, which are desirable)
together with a set of prices (rent, which is undesirable).

The algorithm finds an approximate envy-free division of cakes, chores, or rent. The idea for the algorithm was sparked by Forest Simmons, and further developed by Elisha Peterson and myself. It is an improvement upon the basic trapdoor algorithm that was outlined in my paper: "Rental harmony: Sperner's lemma in fair division ". In our new algorithm, the precision generally increases with each step. Though you are asked to specify a precision in advance, even when a solution is found you may still continue the algorithm to "home in" on a solution to your own satisfaction.

Elisha and I decided to write an applet to test the algorithm! To use it, you must first have a specific object in mind that you would like to divide. The graphics are provided for your convenience.

[Fair Division Applet] [If you can read this message, your browser doesn't support Java applets.]

Some examples to try:

Example 1: Cake, 3 players. Set precision at 20. Suppose C likes cherries, B prefers sprinkles, A just cares about getting the most cake.
Example 2: Chores, 4 players. Try default precision. Suppose A avoids bushes, trees, B hates bagging the trash, C prefers washing the car, D just wants the least quantity of chores.
Example 3: Rent-partitioning, 4 players. Suppose total rent = 400. Try precision 40. Suppose you have a house where Room 1 is the largest, Room 2 gets sun in the mornings, Room 3 is small but has a view, Room 4 has no distinguishing features. Try this out with you and 3 friends.

Instructions:

Enter the number of players (these will be referred to by letter: A,B,C,...) then click on cake, chores, or rent.
If cake or chores, enter the precision (i.e., if you want everyone to be happy within $X, then enter X). A default value is provided for starters.
If rent, you are asked for both the total price of the house and the desired precision.
After pressing the Continue button, the applet will suggest divisions and ask a specific player which portion he/she would prefer. Have that player enter the appropriate portion number. (For cakes and chores, he/she can instead just click on the graphic!)
The algorithm halts when a final division is reached (although you do not have to wait until that happens if you and your friends are satisfied with something sooner!). A suggested division is recorded in the display window. You may restart the applet or continue to get a more precise division if you wish (it will not halt a second time).

Remarks:

The divisions are measured in units out of 100 (or out of the total rent), but keep in mind that there are other factors which may influence your decision--- such as whether you prefer
- frosting, cherries, thickness of cake,
- or taking out the trash, washing the car, mowing the lawn,
- or how much each room costs.
The algorithm halts when it can be assured of a division that will be agreeable to everyone within the precision specified. However, you may land on something agreeable much sooner than that, so feel free to stop whenever you wish!
You may have noticed that sometimes it seems a player is asked more than one time about preferences for the same division. This is because we decided, in the interest of applet memory limitations, not to store player preferences. (A jazzier applet could, of course, do this.) Some redundant questioning can also be removed by identifying cake and chore divisions which are technically different (via different numbering of the pieces) but are actually the same.
The number of steps until this algorithm halts is on the order of O(100 or price/ Precision). Our algorithm can be made faster--- we have one with exponential convergence that just needs to be implemented. The details will be outlined in a forthcoming paper.
The applet seems to work best on a PC under Netscape. I do not know why it seems to run slowly under UNIX.

The Fair Division Page.
Comments? Write me, Francis Su, at su@math.hmc.edu.

Back to...
| Math Department | Faculty | My Home Page | The Fair Division Page
Last modified: August 18, 1998