  This paper resolves two of the handful of remaining questions on the
computability of market equilibria, a central theme within algorithmic game
theory (AGT). Our results are as follows:
  1. We show FIXP-hardness of computing equilibria in Arrow-Debreu markets
under Leontief utility functions, and Arrow-Debreu markets under linear utility
functions and Leontief production sets. We note that these are the first
FIXP-hardness results ever since the introduction of the class FIXP and the
hardness of 3-Nash established therein.
  2. We note that for the problems stated above, the corresponding results
showing membership in FIXP were established after imposing suitable sufficiency
conditions to render the problems total, as is customary in economics. However,
if all instances are under consideration, then in both cases we prove that the
problem of deciding if a given instance admits an equilibrium is
\Exists-R-complete, where \Exists-R is the class of decision problems which can
be reduced in polynomial time to Existential Theory of the Reals.
  3. For Arrow-Debreu markets under Leontief utility functions and a constant
number of agents, we give a polynomial-time algorithm for computing an
equilibrium. This settles part of an open problem of Devanur and Kannan
(FOCS'08).
  We note that PLC utilities are about the most general utilities of interest
in economics and several fundamental utility functions studied within AGT are
special cases of it. Several important problems, which have been shown to be in
FIXP, are waiting for proofs of FIXP-hardness. In this context, our technique
of reducing from 3-Nash to Multivariate Polynomial Equations and then to the
problem is likely to be useful in the future.
