n-Person Envy-Free Chore Division (with Francis Su), submitted. arXiv:0909.0303
Abstract: In this paper we consider the problem of chore division, which is closely related to a classical question, due to Steinhaus, of how to cut a cake fairly. We focus on constructive solutions, i.e., those obtained via a well-defined procedure or algorithm. Among the many notions of fairness is envy-freeness: an envy-free cake division is a set of cuts and an allocation of the pieces that gives each person what she feels is the largest piece. In contrast to cakes, which are desirable, the dual problem of chore division is concerned with dividing an object deemed undesirable. Here, each player would like to receive what he considers to be the smallest piece, of say, a set of chores.
The purpose of this article is to give a general n-person solution to the chore division problem. Su gives an n-person chore division algorithm but it only yields an $\epsilon$-approximate solution after a finite number of steps. Brams and Taylor suggest how cake-cutting methods could be adapted to chore division without working out the details, and our algorithm owes a great debt to their ideas. But we also show where some new ideas are needed, and why the chore division problem is not exactly a dual or straightforward extension of the cake-cutting problem.