Market equilibrium computation

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. 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 (CES).
• 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., ${\displaystyle 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, ${\displaystyle u_{i,j}(x_j)}$, 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, ${\displaystyle u_i(\mathbf{x})=\sum _{j=1}^m{u}_{i,j}\cdot x_j}$, where ${\displaystyle u_{i,j}}$ are constants.
• Lenotief utilities are a special case of PLC utilities.

Main results

Approximate algorithms

Herbert Scarf presented a proof of existence of a CE using Sperner's lemma (see Fisher market). 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 (who invented the class PPAD) 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 (even in a special class which is guaranteed to have a 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 (who defined the complexity class FIXP) 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 (already described in 1983 by Nenakov and Primak) 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${\displaystyle O((n+m{)}^5\log (u_{max})+(n+m{)}^4\log B_{max})}$ maximum flow problems, and thus it runs in time ${\displaystyle 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 ${\displaystyle O((n+m{)}^4\log (u_{max})+(n+m{)}^3{B}_{max})}$. He then improved his algorithm to run in strongly-polynomial time: ${\displaystyle O((m+n{)}^4\log (m+n))}$.

Devanur and Kannan gave algorithms for Arrow-Debreu markets with concave utility functions, 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, a subclass of PLC utilities (when n is constant but m is variable, it was left open whether a polytime algorithm exists).

Garg, Mehta, Vazirani and Yazdanbod gave a polytime algorithm for Leontief utilities when n is constant and m is variable.

Bads and mixed manna

Bogomolnaia and Moulin and Sandomirskiy and Yanovskaia studied the existence and properties of CE in a Fisher market with bads (items with negative utilities) and with a mixture of goods and bads. In contrast to the setting with goods, when the resources are bads the CE does not solve any convex optimization problem even with linear utilities. CE allocations correspond to local minima, local maxima, and saddle points of the product of utilities on the Pareto frontier of the set of feasible utilities. The CE rule becomes multivalued. This work has led to several works on algorithms of finding CE in such markets:

• Branzei and Sandomirskiy gave an algorithm for finding all the CE in a Fisher market with bads and linear utilities. Their algorithm runs in strongly-polynomial time if either n or m is fixed. Their approach combines three ideas: all consumption graphs of PO allocations can be listed in polynomial time; for a given consumption graph, a CE candidate can be constructed via explicit formula; and a given allocation can be checked for being a CE using a maximum flow computation.
• Garg and McGlaughlin gave an algorithm for computing all the CE in a Fisher market with mixed manna and linear utilities. Their algorithm runs in polynomial time if either n or m is fixed.
• Chaudhury, Garg, McGlaughlin and Mehta gave an algorithm for computing a single CE in a Fisher market with mixed manna and SPLC utilities. Their algorithm is simplex-like and based on Lemke's scheme. While its worst-case runtime is not polynomial (the problem is PPAD-hard even with goods), it runs fast on random instances. It also proves that the problem is in PPAD, the solutions are rational-valued, and the number of solutions is odd. Their algorithm runs in polynomial time in the special case in which all utilities are negative.

If both n and m are variable, the problem becomes computationally hard:

• Chaudhury, Garg, McGlaughlin and Mehta show that, in a Fisher market with bads and linear utilities, it is NP-hard to decide whether a CE exists. The same hardness holds even for finding an (11/12+δ)-CE for any δ>0, and even with equal incomes. They also prove a sufficient condition, based on graph connectivity, to the existence of a CE. With this condition, a CE always exists, but finding it is PPAD-hard.

Indivisible goods

When the goods are indivisible, a CE may not exist, but it may be possible to compute an approximate CE.

Deng, Papadimitriou and Safra study exchange markets with m goods, that may be indivisible. They show the following:

1. WIth indivisible goods, it is NP-hard to approximate the deficiency of the market to a factor better than 1/3. It is NP-hard to find equilibrium prices even when they are known to exist. This holds even for linear utilities.
2. With indivisible goods, there is a polytime algorithm for finding an approximate CE when m is bounded and the utilities are linear.
3. When utilities are not strictly-concave, computing a Pareto efficient allocation requires Omega(n log(m+n)) bits of communication, in order to coordinate the bundles (when utilities are strictly-concave no coordination is needed, as each agent has a unique optimal bundle given the price vector). The lower bound holds even for divisible goods; for indivisible goods, the lower bound is even for approximately-efficient allocation, for any approximation ratio. These bounds hold even for constant m.

Main techniques

Bang-for-buck

When the utilities are linear, the bang-per-buck of agent i (also called BPB or utility-per-coin) is defined as the utility of i divided by the price paid. The BPB of a single resource is ${\displaystyle bp{b}_{i,j}:=\frac{u_{i,j}}{p_j}}$; the total BPB is ${\displaystyle bp{b}_{i,total}:=\frac{\sum _{j=1}^m{u}_{i,j}\cdot x_{i,j}}{B_i}}$.

A key observation for finding a CE in a Fisher market with linear utilities is that, in any CE and for any agent i:

• The total BPB is weakly larger than the BPB from any individual resource, ${\displaystyle \mathrm{\forall }j:bp{b}_{i,j}\le bp{b}_{i,total}}$.
• Agent i consumes only resources with the maximum possible BPB, i.e., ${\displaystyle \mathrm{\forall }j:x_{i,j}>0⟹bp{b}_{i,j}=bp{b}_{i,total}}$.

Assume that every product ${\displaystyle j}$ has a potential buyer - a buyer ${\displaystyle i}$ with ${\displaystyle u_{i,j}>0}$. Then, the above inequalities imply that ${\displaystyle p_j>0}$, i.e., all prices are positive.

Cell decomposition

Cell decomposition is a process of partitioning the space of possible prices ${\displaystyle {\mathbb{R}}_{+}^m}$ into small "cells", either by hyperplanes or, more generally, by polynomial surfaces. A cell is defined by specifying on which side of each of these surfaces it lies (with polynomial surfaces, the cells are also known as semialgebraic sets). For each cell, we either find a market-clearing price-vector (i.e., a price in that cell for which a market-clearing allocation exists), or verify that the cell does not contain a market-clearing price-vector. The challenge is to find a decomposition with the following properties:

• The total number of cells is polynomial in the size of the input. This uses the fact that any collection of k hyperplanes in ${\displaystyle {\mathbb{R}}_{+}^m}$ partitions the space into ${\displaystyle O(k^m)}$ cells. This is polynomial if m is fixed. Moreover, any collection of k polynomial surfaces of degree at most d partitions the space into ${\displaystyle O(k^{m+1}\cdot d^{O(m)})}$ non-empty cells, and they can be enumerated in time linear in the output size.
• Finding a market-clearing price-vector in each cell can be done in polynomial time, e.g., using linear programming.

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 ${\displaystyle \sum _{i=1}^n\left(B_i\cdot \log (u_i)\right)}$

Subject to:

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

Sufficient supplies: For every product ${\displaystyle j}$: ${\displaystyle \sum _{i=1}^n{x}_{i,j}\le 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, ${\displaystyle 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 ${\displaystyle x_{i,j}}$ and prices ${\displaystyle p_j}$) satisfy the following inequalities:

1. All prices are non-negative: ${\displaystyle p_j\ge 0}$.
2. If a product has a positive price, then all its supply is exhausted: ${\displaystyle p_j>0⟹\sum _{i=1}^n{x}_{i,j}=1}$.
3. The total BPB is weakly larger than the BPB from any individual resource, ${\displaystyle \mathrm{\forall }j:bp{b}_{i,j}\le bp{b}_{i,total}}$.
4. Agent i consumes only resources with the maximum possible BPB, i.e., ${\displaystyle \mathrm{\forall }j:x_{i,j}>0⟹bp{b}_{i,j}=bp{b}_{i,total}}$.

Assume that every product ${\displaystyle j}$ has a potential buyer - a buyer ${\displaystyle i}$ with ${\displaystyle u_{i,j}>0}$. Then, inequality 3 implies that ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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.

Generalizations and extensions

Graphical markets

Kakade, Kearns and Ortiz studied a generalized Arrow-Debreu market in which agents are located on a graph, trade may occur only between neighboring agents, and all the local markets must clear. They proved a general existence theorem for graphical equilibria, and an algorithm for computing graphucak equilibria which runs in time polynomial in the number of consumers when the graph is a tree. Their algorithms work also for agents with non-linear utilities.

Online computation

Gao, Peysakhovich and Kroer presented an algorithm for online computation of market equilibrium.