The complexity of economic equilibria for house allocation markets

Sándor P. Fekete; Martin Skutella; Gerhard Woeginger

doi:10.1016/j.ipl.2003.08.008

The complexity of economic equilibria for house allocation markets

Sándor P. Fekete, Martin Skutella, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

11 Citations (Scopus)

9 Downloads (Pure)

Abstract

We prove NP-completeness of deciding the existence of an economic equilibrium in so-called house allocation markets. House allocation markets are markets with indivisible goods in which every agent holds exactly one copy of some good.

Original language	English
Pages (from-to)	219-223
Number of pages	5
Journal	Information processing letters
Volume	88
Issue number	5
DOIs	https://doi.org/10.1016/j.ipl.2003.08.008
Publication status	Published - 2003

Keywords

Mathematical economics
Computational Complexity
IR-75015
METIS-213318
Economic equilibrium

Access to Document

10.1016/j.ipl.2003.08.008

Cite this

@article{724c6dc51ec441ceb4f53dec46b5201f,

title = "The complexity of economic equilibria for house allocation markets",

abstract = "We prove NP-completeness of deciding the existence of an economic equilibrium in so-called house allocation markets. House allocation markets are markets with indivisible goods in which every agent holds exactly one copy of some good.",

keywords = "Mathematical economics, Computational Complexity, IR-75015, METIS-213318, Economic equilibrium",

author = "Fekete, \{S{\'a}ndor P.\} and Martin Skutella and Gerhard Woeginger",

year = "2003",

doi = "10.1016/j.ipl.2003.08.008",

language = "English",

volume = "88",

pages = "219--223",

journal = "Information processing letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - The complexity of economic equilibria for house allocation markets

AU - Fekete, Sándor P.

AU - Skutella, Martin

AU - Woeginger, Gerhard

PY - 2003

Y1 - 2003

N2 - We prove NP-completeness of deciding the existence of an economic equilibrium in so-called house allocation markets. House allocation markets are markets with indivisible goods in which every agent holds exactly one copy of some good.

AB - We prove NP-completeness of deciding the existence of an economic equilibrium in so-called house allocation markets. House allocation markets are markets with indivisible goods in which every agent holds exactly one copy of some good.

KW - Mathematical economics

KW - Computational Complexity

KW - IR-75015

KW - METIS-213318

KW - Economic equilibrium

U2 - 10.1016/j.ipl.2003.08.008

DO - 10.1016/j.ipl.2003.08.008

M3 - Article

SN - 0020-0190

VL - 88

SP - 219

EP - 223

JO - Information processing letters

JF - Information processing letters

IS - 5

ER -

The complexity of economic equilibria for house allocation markets

Abstract

Keywords

Access to Document

Fingerprint

Cite this