On computability of equilibria in markets with production
From MaRDI portal
(Redirected from Publication:5384060)
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms (68W40) Auctions, bargaining, bidding and selling, and other market models (91B26) Production theory, theory of the firm (91B38) Special types of economic equilibria (91B52)
Abstract: 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.
Recommendations
- A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
- A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities
- Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria
- Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions
- Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
Cited in
(12)- Computing equilibria for markets with constant returns production technologies
- Markets are efficient if and only if P = NP
- On the polynomial time computation of equilibria for certain exchange economies
- A perfect price discrimination market model with production, and a (rational) convex program for it
- A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
- scientific article; zbMATH DE number 1069798 (Why is no real title available?)
- Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
- Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions
- Dichotomies in equilibrium computation and membership of PLC markets in FIXP
- A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities
- Algorithmic Applications in Management
- Settling the complexity of Nash equilibrium in congestion games
This page was built for publication: On computability of equilibria in markets with production
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384060)
