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).
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.
The input to the market-equilibrium-computation consists of the following ingredients:[1]: chap.5 The required output should contain the following ingredients: The output should satisfy the following requirements: 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.
Market equilibrium computation has been studied under various assumptions regarding the agents' utility functions.
Scarf[2] was the first to show the existence of a CE using Sperner's lemma (see Fisher market).
Merrill[3] gave an extended algorithm for approximate CE.
Kakade, Kearns and Ortiz[4] 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.
Newman and Primak[5] studied two variants of the ellipsoid method for finding a CE in an Arrow-Debreu market with linear utilities.
In some cases, computing an approximate CE is PPAD-hard: Devanur, Papadimitriou, Saberi and Vazirani[10] 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.
Orlin[11] gave an improved algorithm for a Fisher market model with linear utilities, running in time
Devanur and Kannan[6] gave algorithms for Arrow-Debreu markets with concave utility functions, where all resources are goods (the utilities are positive): Codenotti, McCune, Penumatcha and Varadarajan[12] gave an algorithm for Arrow-Debreu markes with CES utilities where the elasticity of substitution is at least 1/2.
Bogomolnaia and Moulin and Sandomirskiy and Yanovskaia studied the existence and properties of CE in a Fisher market with bads (items with negative utilities)[13] and with a mixture of goods and bads.
[14] 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.
This work has led to several works on algorithms of finding CE in such markets: If both n and m are variable, the problem becomes computationally hard: 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.
Cell decomposition[6] is a process of partitioning the space of possible prices
into small "cells", either by hyperplanes or, more generally, by polynomial surfaces.
The challenge is to find a decomposition with the following properties: 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.
Equivalently, it maximizes the weighted arithmetic mean of the logarithms of the utilities: (since supplies are normalized to 1).
These conditions introduce Lagrangian multipliers that can be interpreted as the prices,
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.
The KKT conditions imply that the optimal solutions (allocations
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).
[1]: 107 Vazirani[1]: 109–121 presented an algorithm for finding equilibrium prices and allocations in a linear Fisher market.
The condition implies that, in equilibrium, every buyer buys only products that give him maximum BPB.
Hence, an equilibrium price-vector can be found using the following scheme: There is an algorithm that solves this problem in weakly polynomial time.
Recently, Gao, Peysakhovich and Kroer[20] presented an algorithm for online computation of market equilibrium.