**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**

**Abstract:**

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"** [...]