Four-Person Envy-Free Chore Division
Elisha Peterson, Francis Edward Su · Mathematics Magazine · 2002
In this article we explore the problem of chore division, which is closely related to a classical question, due to Steinhaus [10], of how to cut a cake fairly.We focus on constructive solutions, that is, 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.It is non-trivial to find such a division, since the cake may not be homogeneous and player valuations on subsets of cake will differ, in general.Much progress has been made on finding constructive algorithms for achieving envy-free cake divisions; most recently, Brams and Taylor [3] produced the first general n-person procedure.The recent books by Brams and Taylor [4] and Robertson and Webb [8] give surveys on the cake-cutting literature.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.This problem appears to have been first introduced by Martin Gardner [6].Much less work has been done to develop algorithms for chore division than for cake-cutting.Of course, for 2 people, the familiar I-cut-you-choose cake-cutting procedure also works for dividing chores: one cuts the chores and the other chooses what she feels is the smallest piece.Oskui [8, p. 73] gave the first envy-free solutions for chore division among 3 people.Su [12] developed an envy-free chore-division algorithm for an arbitrary number of players; however, it does not yield an exact solution, but only an s-approximate one.There appear to be no exact envy-free chore-division algorithms for more than three players in the literature; in unpublished manuscripts, Brams and Taylor [2] and Peterson and Su [7] offer n-person algorithms but these are not bounded in the number of steps they require.In this article, we develop a simple and bounded procedure for envy-free chore division among 4 players.The reader will find that many of the ideas involved moving knives, trimming and lumping, and a notion of "irrevocable advantage" provide a nice introduction to similar techniques that arise in the literature onfair division problems.As a warm-up to some of these ideas, we also present a 3-person solution that is simpler and more symmetrical than the procedure of Oskui.We assume throughout this paper that chores are infinitely divisible.This is not unreasonable, as a finite set of chores can be partitioned by dividing up each chore (for instance, a lawn to be mowed could be divided just as if it were a cake), or dividing the time spent on them.We also assume that player valuations over subsets of the chores 1 1 7