Market equilibrium computation

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).

Definitions

The input to the market-equilibrium-computation consists of the following ingredients:

1. A set of $m$ 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 $\mathbf {x} =x_{1},\dots ,x_{m}$, where $x_{j}$ is the quantity of resource $j$. When resources are indivisible, all x_j are integers; when resources are divisible, the x_j can be arbitrarily real numbers (usually normalized to [0,1]).
2. A set of $n$ agents. For each agent, there is a preference relation over bundles, which can be represented by a utility function. The utility function of agent $i$ is denoted by $u_{i}$.
3. An initial endowment for each agent.
   • In a Fisher market, the endowment is a budget $B_{i}$ 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 $\mathbf {e} ^{i}$; in this model, agents can be both buyers and sellers.

The required output should contain the following ingredients:

1. A price-vector $\mathbf {p} =p_{1},\dots ,p_{m}$; 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 $\mathbf {x}$ is $\mathbf {p} \cdot \mathbf {x} =\sum _{j=1}^{m}p_{j}\cdot x_{j}$.
2. An allocation - a bundle $\mathbf {x} ^{i}$ for each agent i.

The output should satisfy the following requirements:

1. The bundle $\mathbf {x} ^{i}$ 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 $\mathbf {p} \cdot \mathbf {x} ^{i}\leq B_{i}$.
   • In an Arrow-Debreu market, this means that $\mathbf {p} \cdot \mathbf {x} ^{i}\leq \mathbf {p} \cdot \mathbf {e} ^{i}$.
2. The bundle $\mathbf {x} ^{i}$ should be in the demand set of i: $\mathbf {x} ^{i}\in {\text{Demand}}_{i}(\mathbf {p} )$, defined as the set of bundles maximizing the agent's utility among all affordable bundles (regardless of supply), e.g., in a Fisher market: ${\text{Demand}}_{i}(\mathbf {p} ):=\arg \max _{\mathbf {p} \mathbf {x} \leq B_{i}}u_{i}(\mathbf {x} )$
3. 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., $u_{i}(\mathbf {x} )=\sum _{j=1}^{m}u_{i,j}(x_{j})$.
• Piecewise-linearity is a special case of separability, in which the utility function for each individual resource, $u_{i,j}(x_{j})$, 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, $u_{i}(\mathbf {x} )=\sum _{j=1}^{m}u_{i,j}\cdot x_{j}$, where $u_{i,j}$ are constants.

Utilities that are piecewise-linear and concave are often called PLC; if they are also separable, then they are called SPLC.

Algorithms

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.

Devanur and Kannan showed that finding a CE is PPAD-hard for Leontief utilities, which are a special case of PLC utilities.

Chen and Teng showed that, even for SPLC utiltiies, computing an approximate equilibrium in a Fisher market is PPAD-hard.

Exact algorithms

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$O((n+m)^{5}\log(u_{\max })+(n+m)^{4}\log {B_{\max }})$ maximum flow problems, and thus it runs in time $O((n+m)^{8}\log(u_{\max })+(n+m)^{7}\log {B_{\max }})$, where u_max and B_max are the maximum utility and budget, respectively.

Orlin gave an improved algorithm for a Fisher market model with linear utilities, running in time $O((n+m)^{4}\log(u_{\max })+(n+m)^{3}B_{\max })$. He then improved his algorithm to run in strongly-polynomial time: $O((m+n)^{4}\log(m+n))$.

Devanur and Kannan gave algorithms for Arrow-Debreu markets with concave utility fuctions, where all resources are goods (the utilities are positive):

• 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 both n and m are variable, it was left open whether a polytime algorithm exists).
• When the utilities are PLC (not necessarily separable) 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, which are a special case of PLC utilities (when n is constant but m is variable, it was left open whether a polytime algorithm exists).

Codenotti, McCune, Penumatcha and Varadarajan gave an algorithm for Arrow-Debreu markes with CES utilities where the elasticity of substitution is at least 1/2.

Convex optimization: homogeneous utilities

If the utilities of all agents are homogeneous functions, then the equilibrium conditions in the Fisher model can be written as solutions to a convex optimization program called the Eisenberg-Gale convex program. This program finds an allocation that maximizes the weighted geometric mean of the buyers' utilities, where the weights are determined by the budgets. Equivalently, it maximizes the weighted arithmetic mean of the logarithms of the utilities:

Maximize $\sum _{i=1}^{n}\left(B_{i}\cdot \log {(u_{i})}\right)$

Subject to:

Non-negative quantities: For every buyer $i$ and product $j$: $x_{i,j}\geq 0$

Sufficient supplies: For every product $j$: $\sum _{i=1}^{n}x_{i,j}\leq 1$

(since supplies are normalized to 1).

This optimization problem can be solved using the Karush–Kuhn–Tucker conditions (KKT). These conditions introduce Lagrangian multipliers that can be interpreted as the prices, $p_{1},\dots ,p_{m}$. In every allocation that maximizes the Eisenberg-Gale program, every buyer receives a demanded bundle. I.e, a solution to the Eisenberg-Gale program represents a market equilibrium.

Vazirani's algorithm: linear utilities, weakly polynomial-time

A special case of homogeneous utilities is when all buyers have linear utility functions. We assume that each resource has a potential buyer - a buyer that derives positive utility from that resource. Under this assumption, market-clearing prices exist and are unique. The proof is based on the Eisenberg-Gale program. The KKT conditions imply that the optimal solutions (allocations $x_{i,j}$ and prices $p_{j}$) satisfy the following inequalities:

1. All prices are non-negative: $p_{j}\geq 0$.
2. If a product has a positive price, then all its supply is exhausted: $p_{j}>0\implies \sum _{i=1}^{n}x_{i,j}=1$.
3. The total bang-per-buck of a buyer (also called BPB or utility-per-coin; defined as the utility attained divided by the price paid) is weakly larger than his BPB from each single product: ${\frac {\sum _{k=1}^{m}u_{i,k}\cdot x_{i,k}}{B_{i}}}\geq {\frac {u_{i,j}}{p_{j}}}$.
4. If a buyer buys a positive amount of a product, then his total BPB from that product equals his total BPB: $x_{i,j}>0\implies {\frac {\sum _{k=1}^{m}u_{i,k}\cdot x_{i,k}}{B_{i}}}={\frac {u_{i,j}}{p_{j}}}$.

Assume that every product $j$ has a potential buyer - a buyer $i$ with $u_{i,j}>0$. Then, inequality 3 implies that $p_{j}>0$, i.e, all prices are positive. Then, inequality 2 implies that all supplies are exhausted. Inequality 4 implies that all buyers' budgets are exhausted. I.e, the market clears.

Since the log function is a strictly concave function, if there is more than one equilibrium allocation then the utility derived by each buyer in both allocations must be the same (a decrease in the utility of a buyer cannot be compensated by an increase in the utility of another buyer). This, together with inequality 4, implies that the prices are unique.

Vazirani presented an algorithm for finding equilibrium prices and allocations in a linear Fisher market. The algorithm is based on condition 4 above. The condition implies that, in equilibrium, every buyer buys only products that give him maximum BPB. Let's say that a buyer "likes" a product, if that product gives him maximum BPB in the current prices. Given a price-vector, construct a flow network in which the capacity of each edge represents the total money "flowing" through that edge. The network is as follows:

• There is a source node, s.
• There is a node for each product; there is an edge from s to each product j, with capacity $p_{j}$ (this is the maximum amount of money that can be expended on product j, since the supply is normalized to 1).
• There is a node for each buyer; there is an edge from a product to a buyer, with infinite capacity, iff the buyer likes the product (in the current prices).
• There is a target node, t; there is an edge from each buyer i to t, with capacity $B_{i}$ (the maximum expenditure of i).

The price-vector p is an equilibrium price-vector, if and only if the two cuts ({s},V\{s}) and (V\{t},{t}) are min-cuts. Hence, an equilibrium price-vector can be found using the following scheme:

• Start with very low prices, which are guaranteed to be below the equilibrium prices; in these prices, buyers have some budget left (i.e, the maximum flow does not reach the capacity of the nodes into t).
• Continuously increase the prices and update the flow-network accordingly, until all budgets are exhausted.

There is an algorithm that solves this problem in weakly polynomial time.