The computation of approximate competitive equilibrium is PPAD-hard

Xiaotie Deng; Ye Du

doi:10.1016/j.ipl.2008.07.011

The computation of approximate competitive equilibrium is PPAD-hard

Xiaotie Deng
, Ye Du

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

8 Citations (Scopus)

Abstract

Arrow and Debreu showed in 1954 that, under mild conditions, a competitive economy always has an equilibrium. In this paper, we show that, given a competitive economy that fully respects all the conditions of Arrow-Debreu's existence theorem, for any positive constant h > 0, it is PPAD-hard to compute a frac(1, n^h)-approximate competitive equilibrium. © 2008 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	369-373
Journal	Information Processing Letters
Volume	108
Issue number	6
DOIs	https://doi.org/10.1016/j.ipl.2008.07.011
Publication status	Published - 30 Nov 2008

Research Keywords

Competitive equilibrium
Computational complexity
Leontief economy
PPAD

Access Output

10.1016/j.ipl.2008.07.011

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{7d3eaa3962c74f9187a93d9df2e50748,

title = "The computation of approximate competitive equilibrium is PPAD-hard",

abstract = "Arrow and Debreu showed in 1954 that, under mild conditions, a competitive economy always has an equilibrium. In this paper, we show that, given a competitive economy that fully respects all the conditions of Arrow-Debreu's existence theorem, for any positive constant h > 0, it is PPAD-hard to compute a frac(1, nh)-approximate competitive equilibrium. {\textcopyright} 2008 Elsevier B.V. All rights reserved.",

keywords = "Competitive equilibrium, Computational complexity, Leontief economy, PPAD",

author = "Xiaotie Deng and Ye Du",

year = "2008",

month = nov,

day = "30",

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

language = "English",

volume = "108",

pages = "369--373",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - The computation of approximate competitive equilibrium is PPAD-hard

AU - Deng, Xiaotie

AU - Du, Ye

PY - 2008/11/30

Y1 - 2008/11/30

N2 - Arrow and Debreu showed in 1954 that, under mild conditions, a competitive economy always has an equilibrium. In this paper, we show that, given a competitive economy that fully respects all the conditions of Arrow-Debreu's existence theorem, for any positive constant h > 0, it is PPAD-hard to compute a frac(1, nh)-approximate competitive equilibrium. © 2008 Elsevier B.V. All rights reserved.

AB - Arrow and Debreu showed in 1954 that, under mild conditions, a competitive economy always has an equilibrium. In this paper, we show that, given a competitive economy that fully respects all the conditions of Arrow-Debreu's existence theorem, for any positive constant h > 0, it is PPAD-hard to compute a frac(1, nh)-approximate competitive equilibrium. © 2008 Elsevier B.V. All rights reserved.

KW - Competitive equilibrium

KW - Computational complexity

KW - Leontief economy

KW - PPAD

UR - https://www.scopus.com/pages/publications/53049094352

UR - https://www.scopus.com/pages/publications/53049094352#tab=impact

U2 - 10.1016/j.ipl.2008.07.011

DO - 10.1016/j.ipl.2008.07.011

M3 - RGC 21 - Publication in refereed journal

SN - 0020-0190

VL - 108

SP - 369

EP - 373

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

The computation of approximate competitive equilibrium is PPAD-hard

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this