In this paper, we resolve two open questions on the computation and approximation of an Arrow-Debreu equilibrium in a Leontief exchange economy: - We prove that the Leontief market exchange problem does not have a fully polynomial-time approximation scheme, unless PPAD ⊆ P. - We show that the smoothed complexity of any algorithm for computing a market equilibrium in a Leontief economy, is not polynomial, unless PPAD ⊆ RP.
['Li-Sha Huang', 'Shang-Hua Teng']
On the approximation and smoothed complexity of Leontief market equilibria