Introduction

In this chapter we present the solution to the problem first raised by Gamow and Stern (1958) of finding a finite algorithm for providing an envy-free division among any number of players. Before presenting this solution, however, we will describe two algorithms in section 7.2 – one continuous, involving a moving knife, and the other discrete – that provide allocations that are approximately envy-free, with the degree of error within any preset tolerance level.

We describe in section 7.3 an exact but “infinite” solution to the n-person envy-freeness problem, using what we call the “trimming procedure.” Because this procedure requires an infinite number of stages to accomplish, however, it is not, technically, an algorithm.

Fortunately, the trimming procedure can be rendered finite, but only by complicating it considerably. Without giving full details, we will describe enough of the finite procedure in section 7.4 to give the reader a good idea of how it works, and why it is unbounded – the number of stages it may require cannot be specified without knowing the preferences of the players. We will also illustrate this procedure with an example involving four players.

In section 7.5 we apply the trimming procedure to an inheritance example that involves indivisible as well as divisible goods, showing that it may be necessary to sell some of the indivisible goods to complete the procedure.