Market equilibrium computation


Market equilibrium computation is a computational problem in the intersection of economics and computer science. The input to this problem is a market, consisting of a set of resources and a set of agents. There are various kinds of markets, such as Fisher market and Arrow–Debreu market, with divisible or indivisible resources. The required output is a competitive equilibrium, consisting of a price-vector, and an allocation, such that each agent gets the best bundle possible given the budget, and the market clears.
Market equilibrium computation is interesting due to the fact that a competitive equilibrium is always Pareto efficient. The special case of a Fisher market, in which all buyers have equal incomes, is particularly interesting, since in this setting a competitive equilibrium is also envy-free. Therefore, market equilibrium computation is a way to find an allocation which is both fair and efficient.
Since the 1960s, there has been attempts to apply the general equilibrium theory to support policy decisions in subjects such as tax reform or simultaneous tariff reductions. These models are typically large, so efficient computation is needed.

Definitions

The input to the market-equilibrium-computation consists of the following ingredients:
  1. A set of resources with pre-specified supplies. The resources can be divisible, or indivisible.
  2. * A bundle is represented by a vector, where is the quantity of resource. When resources are indivisible, all xj are integers; when resources are divisible, the xj can be arbitrarily real numbers.
  3. A set of agents. For each agent, there is a preference relation over bundles, which can be represented by a utility function. The utility function of agent is denoted by.
  4. An initial endowment for each agent.
  5. * In a Fisher market, the endowment is a budget of "fiat money" - a money that has no value outside the market, and thus does not enter the utility function. Since the agents come with money only, they are often called buyers.
  6. * In an Arrow–Debreu market, the endowment is an arbitrary bundle ; in this model, agents can be both buyers and sellers.
The required output should contain the following ingredients:
  1. A price-vector ; a price for each resource. The price of a bundle is the sum of the prices of the resources in the, so the price of a bundle is.
  2. An allocation - a bundle for each agent i.
The output should satisfy the following requirements:
  1. The bundle should be affordable to i, that is, its price should be at most the price of agent i's endowment.
  2. * In a Fisher market, this means that .
  3. * In an Arrow-Debreu market, this means that .
  4. The bundle should be in the demand set of i:, defined as the set of bundles maximizing the agent's utility among all affordable bundles, e.g., in a Fisher market:
  5. The market clears, i.e., all resources are allocated. The corresponding prices are called market-clearing prices.
A price and allocation satisfying these requirements are called a competitive equilibrium or a market equilibrium; the prices are also called equilibrium prices or clearing prices.

Kinds of utility functions

Market equilibrium computation has been studied under various assumptions regarding the agents' utility functions.
  • Concavity: the most general assumption is that the agents' utilities are concave functions, i.e., display diminishing returns. This assumption is very common in economics.
  • Homogeneity: In some cases, it is assumed that the utilities are homogeneous functions.
  • * A special case is utilities with constant elasticity of substitution.
  • Separability: A utility function is called separable if the utility of a bundle is the sum of the utilities of the individual resources in the bundle, i.e.,.
  • Piecewise-linearity is a special case of separability, in which the utility function for each individual resource,, is a piecewise linear function of xj. This assumption is common in computer science, as it allows a finite representation of the utility functions.
  • *Utilities that are piecewise-linear and concave are often called PLC; if they are also separable, then they are called SPLC.
  • Linearity is an even more special case, in which the utility function for each individual resource is a linear function. That is,, where are constants.
  • Lenotief utilities are a special case of PLC utilities.

    Main results

Approximate algorithms

presented a proof of existence of a CE using Sperner's lemma. He converted this proof to an algorithm for computing an approximate CE. In his later work, he continued to develop these algorithms.
Merrill gave an extended algorithm for approximate CE.
Other algorithms for fixed-point computation, such as the homotopy method, can also be used to compute CE.
All these algorithms do not have a polynomial runtime guarantee.

Hardness results

Papadimitriou proved that computing an approximate CE for Arrow-Debreu markets given by aggregate excess demand functions is PPAD-complete. Later results have shown PPAD-hardness even for more specific classes of utility functions:
  • Codenotti, Saberi, Varadrajan and Ye prove that exchange markets with Leontief utilities encode nonzero sum two-player games. This implies that computing CE is at least as hard as Nash equilibrium computation for two-player nonzero sum games.
  • Devanur and Kannan proved PPAD-hardness for an Arrow-Debreu market with Leontief utilities.
  • Chen, Dai, Du and Teng proved PPAD-hardness for an Arrow-Debreu market with SPLC utilities. Their proof shows that this market-equilibrium problem does not have an FPTAS unless PPAD is in P.
  • Chen and Teng proved PPAD-hardness for a Fisher market with SPLC utilities.
  • Chaudhury, Garg, McGlaughlin and Mehta proved PPAD-hardness for a Fisher market with bads and linear utilities, even under a certain condition that guarantees CE existence.
Complementing these results, Garg, Mehta, Vazirani and Yazdanbod show that computing an approximate CE with PLC utilities is in PPAD. The main technical challenge was to show that an approximate fixed-point corresponds to an approximate CE.
Etessami and Yannakkis proved that computing CE prices for exchange markets with algebraic demand functions is FIXP-complete. Later results have shown FIXP-hardness for more specific classes of utilities:
  • Garg, Mehta, Vazirani and Yazdanbod proved FIXP-hardness even for Leontief utilities, which implies FIXP-hardness for PLC utilities. Combined with a previous proof of membership in FIXP, their results imply FIXP-completeness. The FIXP-hardness result holds when only "yes" instances are considered; when all instances are considered, deciding whether a CE exists is ETR-complete.

    Exact algorithms

For some special cases, polynomial-time algorithms have been developed.
Eaves showed that, in an exchange market with Cobb-Douglas utilities, the CE be written as the solution to a linear program; hence it is possible to compute all CE in polynomial time.
Deng, Papadimitriou and Safra present a polytime algorithm for finding the CE when m is bounded and the utilities are linear.
Kakade, Kearns and Ortiz generalize the above algorithm for bounded m. Their generalized algorithm computes an approximate CE for a general class of non-linear utility functions.
Newman and Primak studied two variants of the ellipsoid method for finding a CE in an Arrow-Debreu market with linear utilities. They prove that the inscribed ellipsoid method is more computationally efficient than the circumscribed ellipsoid method.
Codenotti and Varadarajan gave a polytime algorithm for Fisher markes with Leontief utilities. Their approach extends to a wider family of utilities, which includes CES utilities. However, unlike in the linear case, the equilibrium prices can be irrational, which means that an exact computation is not possible.
Codenotti, McCune, Penumatcha and Varadarajan gave a polytime algorithm for Arrow-Debreu markes with CES utilities where the elasticity of substitution is at least 1/2.
Codenotti, Pemmaraju, Raman and Varadarajan presented a polytime algorithm for exchange markets with weak gross substitute utilities; these generalize linear, Cobb-Douglas, CES and even some non-homogeneous utility functions.
Chen, Deng, Sun and Yao gave a polytime algorithm for Fisher markets with logarithmic utilities, when either m or n is constant.
Kamal Jain introduced a convex program that characterizes the CE for exchange markets with linear utilities, CES utilities with r>0, and some other utility functions. He also proved that for linear utilities there exists a normalized CE with rational prices. Jain used this property to develop a variant of the ellipsoid method to compute the CE exactly in polytime. Later, Ye showed how to use Interior-point methods, which are much more efficient in practice. Codenotti and Varadarajan presented a different convex program that characterizes the CE also for CES utilities with -1 < r < 0.
Devanur, Papadimitriou, Saberi and Vazirani gave a polynomial-time algorithm for exactly computing an equilibrium for Fisher markets with linear utility functions. Their algorithm uses the primal–dual paradigm in the enhanced setting of KKT conditions and convex programs. Their algorithm is weakly-polynomial: it solves maximum flow problems, and thus it runs in time , where umax and Bmax are the maximum utility and budget, respectively.
Orlin gave an improved algorithm for a Fisher market model with linear utilities, running in time. He then improved his algorithm to run in strongly-polynomial time:.
Devanur and Kannan gave algorithms for Arrow-Debreu markets with concave utility functions, where all resources are goods :
  • When the utilities are SPLC and either n or m is a constant, their algorithm is polynomial in the other parameter. The technique is decomposing the space of possible prices into cells using a constant number of hyperplanes, so that in each cell, each buyer’s threshold marginal utility is known.
  • When the utilities are PLC and m is constant, their algorithm is polynomial in n. When both m and n are variable, finding a CE is PPAD-hard even for Leontief utilities, a subclass of PLC utilities.
Garg, Mehta, Vazirani and Yazdanbod gave a polytime algorithm for Leontief utilities when n is constant and m is variable.