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

F. Klijn

Research output: Book/ReportReport

271 Downloads (Pure)

Abstract

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
Volume751
Publication statusPublished - 1997

Publication series

NameFEW Research Memorandum
Volume751

Keywords

  • algorithm
  • welfare economics

Fingerprint 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