{"id":763,"date":"2020-09-01T20:40:18","date_gmt":"2020-09-01T20:40:18","guid":{"rendered":"https:\/\/math.hmc.edu\/su\/?page_id=763"},"modified":"2020-09-01T20:45:02","modified_gmt":"2020-09-01T20:45:02","slug":"fairdivision","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/su\/fairdivision\/","title":{"rendered":"Fair Division Calculator"},"content":{"rendered":"\n

This program ran as a java applet which is no longer viewable with current browsers. This page contains historical information. To use the application, please access the <\/strong>New York Times version<\/strong><\/a> and view the <\/strong>related article<\/strong><\/a>.<\/strong><\/p>\n\n\n\n

A java applet for interactive decision making to find envy-free divisions of goods, burdens, or rent.<\/em><\/p>\n\n\n\n

The Fair Division Calculator will soon be integrated into\u00a0ARTUS, a process control system for group decision and negotiation on the Internet. ARTUS is a project directed by\u00a0Matthias Raith. When the integration is complete, it will be the first\u00a0analytical<\/em>\u00a0mediation support system on the Internet!<\/p>\n\n\n\n

What is “Fair Division”?<\/h2>\n\n\n\n

The theory of fair division is concerned with finding ways to divide an object among n<\/em> people fairly<\/em>. There are many possible notions of fairness. The notion that has interested me recently is finding envy-free<\/em> divisions, i.e., one in which each person feels she received the best<\/em> piece, in her own estimation.<\/p>\n\n\n\n

Exact vs. Approximate Algorithms<\/h3>\n\n\n\n

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<\/em>-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<\/a> for n<\/em> people. However, such methods tend to be quite complicated as n<\/em> grows large.<\/p>\n\n\n\n

By contrast, I have been interested in developing\u00a0approximate<\/em>\u00a0envy-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\u00a0Elisha Peterson,\u00a0Patrick Vinograd, and Karl Mahlburg have also been working with me.<\/p>\n\n\n\n

To explore such algorithms, we have developed the Fair Division Calculator.<\/p>\n\n\n\n

The Fair Division Calculator finds approximate envy-free divisions up to any precision for the following problems:<\/p>\n\n\n\n