Four-person envy-free chore division (with Francis Su), Mathematics Magazine 75, pp. 117-122, 2002. PDF
Abstract: In this article we explore 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, 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. 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 on fair division problems.