## Invited Session Tue.3.MA 043

#### Tuesday, 15:15 - 16:45 h, Room: MA 043

**Cluster 8: Game theory** [...]

### New LCP-based market equilibrium algorithms

**Chair: Vijay V. Vazirani**

**Tuesday, 15:15 - 15:40 h, Room: MA 043, Talk 1**

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

**Tuesday, 15:45 - 16:10 h, Room: MA 043, Talk 2**

**Jugal Garg**

A complementary pivot algorithm for markets under separable piecewise-linear concave utilities

**Coauthors: Ruta Mehta, Milind Sohoni, Vijay V. Vazirani**

**Abstract:**

Using the powerful machinery of the LCP and Lemke's algorithm, we give a practical algorithm for computing an equilibrium for Arrow-Debreu markets under separable, piecewise-linear concave (SPLC) utilities, despite the PPAD-completeness of this case. As a corollary, we obtain the first elementary proof of existence of equilibrium for this case.

In 1975, Eaves had given such an algorithm for the case of linear utilities and had asked for an extension to the piecewise-linear, concave utilities. Our result settles the relevant subcase of his problem as well as the problem of Vazirani and Yannakakis of obtaining a path following algorithm for SPLC markets, thereby giving a direct proof of membership in PPAD.

We also prove that SPLC markets have an odd number of equilibria (up to scaling), hence matching the classical result of Shapley about 2-Nash equilibria, which was based on Lemke-Howson algorithm.

For the linear case, Eaves had asked for a combinatorial interpretation of his algorithm. We provide this and it yields a particularly simple proof of the fact that the set of equilibrium prices is convex.

**Tuesday, 16:15 - 16:40 h, Room: MA 043, Talk 3**

**Ruta Mehta**

LCP and Lemke-type algorithm for markets with production

**Coauthors: Jugal Garg, Vijay V. Vazirani**

**Abstract:**

Building on the works of Eaves and Garg, Mehta, Sohoni and Vazirani, we

obtain an LCP that captures exactly the set of equilibria for Arrow-Debreu

and Fisher markets with separable, piecewise-linear concave (SPLC)

utilities and SPLC production, and we also give a complementary pivot algorithm for finding an equilibrium. This answers a question asked by Eaves in 1975. As corollaries, we obtain a proof of PPAD-completeness, an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and oddness of the number of equilibria. Experiments show that our algorithm is practical.