05382274

j

05382274 Codenotti, Bruno Saberi, Amin Varadarajan, Kasturi Ye, Yinyu The complexity of equilibria: Hardness results for economies via a correspondence with games. Theor. Comput. Sci. 408, No. 2-3, 188-198 (2008). 2008 Elsevier Science Publishers, Amsterdam EN exchange economy linear complementarity Nash equilibrium quasi-equilibrium bimatrix games Leontief economy NP-hardness NP-completness

doi:10.1016/j.tcs.2008.08.007

The authors consider a special case of the Leontief exchange economy $E$ where $l$, the number of traders, is equal to the number of goods, and the $i$-th trader has an initial endowment given by one unit of the $i$-th good and by 0 for other goods, $i=1,\dots ,l$. The traders have a utility function of the form $u_i(x)= \min_{\{j: f_{ij}\not=0\}} x_{ij}/f_{ij}$ for $i=1,\dots ,l$, where $f_{ij}$ are elements a fixed matrix $F$ of size $l$ and $(x_{i1}, \dots , x_{il})$ is a bundle of goods of the $i$-th trader in $x$. The first result of the paper says that for any bimatrix game $(A,B)$ specified by a pair of matrices $A$ and $B$ of size $m\times n$ with positive entries determines a Leontief exchange economy $E$ with $l=n+m$, such that there is a one-to-one correspondence between the Nash equilibria of game $(A,B)$ and the market equilibria of exchange economy $E$. As a corollary of this a number of hardness results for questions related to the computation of market equilibria are obtained. The second main result is that the problem whether Leontief exchange economy has an equilibrium, is NP-hard. Tadeusz Radzik (Jelenia G\'ora)