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

F. Klijn

Research output: Book/ReportReportProfessional

218 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

Fingerprint

Indivisible
Balancedness
Extreme Points
Connectedness
Polytopes
Utility Function
Linear Function
Existence Results
Permutation
Game
Object
Graph in graph theory

Keywords

  • algorithm
  • welfare economics

Cite this

Klijn, F. (1997). Envy-Free Allocations of Indivisible Objects: An Algorithm and an Application. (FEW Research Memorandum; Vol. 751). Tilburg: Operations research.
Klijn, F. / Envy-Free Allocations of Indivisible Objects : An Algorithm and an Application. Tilburg : Operations research, 1997. 15 p. (FEW Research Memorandum).
@book{2a7e4e1ebdbf46669aaf3d4c1d420b62,
title = "Envy-Free Allocations of Indivisible Objects: An Algorithm and an Application",
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.",
keywords = "algorithm, welfare economics",
author = "F. Klijn",
note = "Pagination: 15",
year = "1997",
language = "English",
volume = "751",
series = "FEW Research Memorandum",
publisher = "Operations research",

}

Klijn, F 1997, Envy-Free Allocations of Indivisible Objects: An Algorithm and an Application. FEW Research Memorandum, vol. 751, vol. 751, Operations research, Tilburg.

Envy-Free Allocations of Indivisible Objects : An Algorithm and an Application. / Klijn, F.

Tilburg : Operations research, 1997. 15 p. (FEW Research Memorandum; Vol. 751).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Envy-Free Allocations of Indivisible Objects

T2 - An Algorithm and an Application

AU - Klijn, F.

N1 - Pagination: 15

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

KW - algorithm

KW - welfare economics

M3 - Report

VL - 751

T3 - FEW Research Memorandum

BT - Envy-Free Allocations of Indivisible Objects

PB - Operations research

CY - Tilburg

ER -

Klijn F. Envy-Free Allocations of Indivisible Objects: An Algorithm and an Application. Tilburg: Operations research, 1997. 15 p. (FEW Research Memorandum).