Envy-Free Allocations of Indivisible Objects: An Algorithm and an Application

F. Klijn

Research output: Book/ReportReport

275 Downloads (Pure)


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.As an application, the existence result of envy-free allocations provides a proof of the total balancedness of permutation games.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages15
Publication statusPublished - 1997

Publication series

NameFEW Research Memorandum


  • algorithm
  • welfare economics


Dive into the research topics of 'Envy-Free Allocations of Indivisible Objects: An Algorithm and an Application'. Together they form a unique fingerprint.

Cite this