A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium

Zhisu Zhu; Chuangyin Dang; Yinyu Ye

doi:10.1007/978-3-540-92185-1_12

A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium

Zhisu Zhu, Chuangyin Dang, Yinyu Ye

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

1 Citation (Scopus)

Abstract

We consider a linear complementarity problem (LCP) arisen from the Arrow-Debreu-Leontief competitive economy equilibrium where the LCP coefficient matrix is symmetric. We prove that the decision problem, to decide whether or not there exists a complementary solution, is NP-complete. Under certain conditions, an LCP solution is guaranteed to exist and we present a fully polynomial-time approximation scheme (FPTAS) for computing such a solution, although the LCP solution set can be non-convex or non-connected. Our method is based on solving a quadratic social utility optimization problem (QP) and showing that a certain KKT point of the QP problem is an LCP solution. Then, we further show that such a KKT point can be approximated with running time O ((1/ε)log (1/ε)log (log(1/ε)) in accuracy ε ∈(0,1) and a polynomial in problem dimensions. We also report preliminary computational results which show that the method is highly effective.

Original language	English
Title of host publication	Internet and Network Economics
Subtitle of host publication	4th International Workshop, WINE 2008 Shanghai, China, December 17-20, 2008 : Proceedings
Editors	Christos Papadimitriou, Shuzhong Zhang
Pages	31-40
ISBN (Electronic)	9783540921851
DOIs	https://doi.org/10.1007/978-3-540-92185-1_12
Publication status	Published - 2008
Event	4th International Workshop on Internet and Network Economics (WINE 2008) - Shanghai, China Duration: 17 Dec 2008 → 20 Dec 2008

Publication series

Name	Lecture Notes in Computer Science
Volume	5385
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th International Workshop on Internet and Network Economics (WINE 2008)
Place	China
City	Shanghai
Period	17/12/08 → 20/12/08

Access Output

10.1007/978-3-540-92185-1_12

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Zhu, Z., Dang, C., & Ye, Y. (2008). A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium. In C. Papadimitriou, & S. Zhang (Eds.), Internet and Network Economics: 4th International Workshop, WINE 2008 Shanghai, China, December 17-20, 2008 : Proceedings (pp. 31-40). (Lecture Notes in Computer Science; Vol. 5385). https://doi.org/10.1007/978-3-540-92185-1_12

@inproceedings{9a0344b9dab84d6bb85fc47f6d7a94a7,

title = "A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium",

abstract = "We consider a linear complementarity problem (LCP) arisen from the Arrow-Debreu-Leontief competitive economy equilibrium where the LCP coefficient matrix is symmetric. We prove that the decision problem, to decide whether or not there exists a complementary solution, is NP-complete. Under certain conditions, an LCP solution is guaranteed to exist and we present a fully polynomial-time approximation scheme (FPTAS) for computing such a solution, although the LCP solution set can be non-convex or non-connected. Our method is based on solving a quadratic social utility optimization problem (QP) and showing that a certain KKT point of the QP problem is an LCP solution. Then, we further show that such a KKT point can be approximated with running time O ((1/ε)log (1/ε)log (log(1/ε)) in accuracy ε ∈(0,1) and a polynomial in problem dimensions. We also report preliminary computational results which show that the method is highly effective.",

author = "Zhisu Zhu and Chuangyin Dang and Yinyu Ye",

year = "2008",

doi = "10.1007/978-3-540-92185-1_12",

language = "English",

isbn = "3540921842",

series = "Lecture Notes in Computer Science",

pages = "31--40",

editor = "Christos Papadimitriou and Shuzhong Zhang",

booktitle = "Internet and Network Economics",

note = "4th International Workshop on Internet and Network Economics (WINE 2008) ; Conference date: 17-12-2008 Through 20-12-2008",

}

Zhu, Z, Dang, C & Ye, Y 2008, A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium. in C Papadimitriou & S Zhang (eds), Internet and Network Economics: 4th International Workshop, WINE 2008 Shanghai, China, December 17-20, 2008 : Proceedings. Lecture Notes in Computer Science, vol. 5385, pp. 31-40, 4th International Workshop on Internet and Network Economics (WINE 2008), Shanghai, China, 17/12/08. https://doi.org/10.1007/978-3-540-92185-1_12

A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium. / Zhu, Zhisu; Dang, Chuangyin; Ye, Yinyu.
Internet and Network Economics: 4th International Workshop, WINE 2008 Shanghai, China, December 17-20, 2008 : Proceedings. ed. / Christos Papadimitriou; Shuzhong Zhang. 2008. p. 31-40 (Lecture Notes in Computer Science; Vol. 5385).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium

AU - Zhu, Zhisu

AU - Dang, Chuangyin

AU - Ye, Yinyu

PY - 2008

Y1 - 2008

N2 - We consider a linear complementarity problem (LCP) arisen from the Arrow-Debreu-Leontief competitive economy equilibrium where the LCP coefficient matrix is symmetric. We prove that the decision problem, to decide whether or not there exists a complementary solution, is NP-complete. Under certain conditions, an LCP solution is guaranteed to exist and we present a fully polynomial-time approximation scheme (FPTAS) for computing such a solution, although the LCP solution set can be non-convex or non-connected. Our method is based on solving a quadratic social utility optimization problem (QP) and showing that a certain KKT point of the QP problem is an LCP solution. Then, we further show that such a KKT point can be approximated with running time O ((1/ε)log (1/ε)log (log(1/ε)) in accuracy ε ∈(0,1) and a polynomial in problem dimensions. We also report preliminary computational results which show that the method is highly effective.

AB - We consider a linear complementarity problem (LCP) arisen from the Arrow-Debreu-Leontief competitive economy equilibrium where the LCP coefficient matrix is symmetric. We prove that the decision problem, to decide whether or not there exists a complementary solution, is NP-complete. Under certain conditions, an LCP solution is guaranteed to exist and we present a fully polynomial-time approximation scheme (FPTAS) for computing such a solution, although the LCP solution set can be non-convex or non-connected. Our method is based on solving a quadratic social utility optimization problem (QP) and showing that a certain KKT point of the QP problem is an LCP solution. Then, we further show that such a KKT point can be approximated with running time O ((1/ε)log (1/ε)log (log(1/ε)) in accuracy ε ∈(0,1) and a polynomial in problem dimensions. We also report preliminary computational results which show that the method is highly effective.

UR - http://www.scopus.com/inward/record.url?scp=58849100404&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-58849100404&origin=recordpage

U2 - 10.1007/978-3-540-92185-1_12

DO - 10.1007/978-3-540-92185-1_12

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 3540921842

SN - 9783540921844

T3 - Lecture Notes in Computer Science

SP - 31

EP - 40

BT - Internet and Network Economics

A2 - Papadimitriou, Christos

A2 - Zhang, Shuzhong

T2 - 4th International Workshop on Internet and Network Economics (WINE 2008)

Y2 - 17 December 2008 through 20 December 2008

ER -

A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this