2002-00-00 Four-person envy-free chore division

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.

Return to list of publications and talks

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License