An algorithm for envy-free allocations in an economy with indivisible objects and money

This paper studies envy-free allocations for economies with indivisible objects, quasi-linear utility functions, and an amount of money. We give a polynomially bounded algorithm for finding envy-free allocations. Connectedness of envy-graphs, which are used in the algorithm, characterizes the extreme points of the polytopes of sidepayments corresponding with envy-free allocations. Received: 22 October 1997/Accepted: 19 January 1999