Although production is an integral part of the Arrow-Debreu market model, most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. This paper takes a significant step towards understanding computational aspects of markets with production. We first define the notion of separable, piecewise-linear concave (SPLC) production by analogy with SPLC utility functions. We then obtain a linear complementarity problem (LCP) formulation that captures exactly the set of equilibria for Arrow-Debreu markets with SPLC utilities and SPLC production, and we give a complementary pivot algorithm for finding an equilibrium. This settles a question asked by Eaves in 1975 of extending his complementary pivot algorithm to markets with production. Since this is a path-following algorithm, we obtain a proof of membership of this problem in PPAD, using Todd, 1976. We also obtain an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and oddness of the number of equilibria. We further give a proof of PPAD-hardness for this problem and also for its restriction to markets with linear utilities and SPLC production. Experiments show that our algorithm runs fast on randomly chosen examples, and unlike previous approaches, it does not suffer from issues of numerical instability. Additionally, it is strongly polynomial when the number of goods or the number of agents and firms is constant. This extends the result of Devanur and Kannan (2008) to markets with production. Finally, we show that an LCP-based approach cannot be extended to PLC (non-separable) production, by constructing an example which has only irrational equilibria.
We consider the computation of equilibria in two economic models that generalize the exchange model by including production. In the constant returns model, each producer has a convex, constant-returns-to-scale, technology. In particular, this means that if the technology can output a certain quantity of a good using as input certain quantities of other goods, then scaling all these quantities by a common, non-negative, number also results in a technologically feasible plan. The technology also accomodates the no-free-lunch property, which says that it is not possible to produce something from nothing. At a given price, the producer picks a technologically feasible plan that maximizes her profit. Associated with each consumer is an initial endowment of goods and a utility function that describes her preferences between various bundles of goods. At a given price, the consumer sells her initial endowment, thus obtaining a certain income, and demands the bundle of goods maximizing her utility among all bundles that she can afford at the given price with her income.