Market equilibrium computation (also called competitive equilibrium computation or clearing-prices 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 (a price for each resource), and an allocation (a resource-bundle for each agent), such that each agent gets the best bundle possible (for him) given the budget, and the market clears (all resources are allocated).
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.
Definitions
The input to the market-equilibrium-computation consists of the following ingredients:
A set of resources with pre-specified supplies. The resources can be divisible (in which case, their supply is w.l.o.g. normalized to 1), or indivisible . 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 (usually normalized to [0,1]). 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 . An initial endowment for each agent. 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. 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:
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 . An allocation - a bundle for each agent i.
The output should satisfy the following requirements:
The bundle should be affordable to i, that is, its price should be at most the price of agent i's endowment. In a Fisher market, this means that . In an Arrow-Debreu market, this means that . 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 (regardless of supply), e.g., in a Fisher market: 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 (CE) 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 (made by Fisher and Arrow&Debreu) is that the agents' utilities are concave functions, i.e., display diminishing returns. Homogeneity: In some cases, it is assumed that the utilities are homogeneous functions. This includes, in particular, 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. 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. Utilities that are piecewise-linear and concave are often called PLC; if they are also separable, then they are called SPLC.
Main results
Approximate algorithms
Scarf was the first to show the existence of a CE using Sperner's lemma (see Fisher market). He also gave an algorithm for computing an approximate CE.
Merrill gave an extended algorithm for approximate CE.
Kakade, Kearns and Ortiz gave algorithms for approximate CE in a generalized Arrow-Debreu market in which agents are located on a graph and trade may occur only between neighboring agents. They considered non-linear utilities.