Tuesday, 15:15 - 15:40 h, Room: MA 043


Yinyu Ye
A FPTAS for computing a symmetric Leontief competitive economy equilibrium

Coauthors: Chuangyin Dang, Zhisu Zhu


We consider a linear complementarity problem (LCP) arisen from the Arrow-Debreu competitive economy equilibrium with Leontief utilities. We prove that the decision problem, to decide whether or not there exists a complementary solution, is NP-complete even when the coefficient matrix is symmetric. But under certain conditions, an LCP solution is guaranteed to exist and represent a symmetric Leontief economy equilibrium. Then, we present a fully polynomial-time approximation scheme (FPTAS) for approximating a complementary solution. Our method is based on solving a quadratic social utility optimization problem. We also develop an interior-point path-following algorithm for the problem when the coefficient matrix is non-symmetric. Based on an extended Sard theorem, we construct an almost surely regular homotopy for the system. We report preliminary computational results which show that our methods are practically effective.


Talk 1 of the invited session Tue.3.MA 043
"New LCP-based market equilibrium algorithms" [...]
Cluster 8
"Game theory" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. What can cause long-term use of Viagra Sale? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.