Fisher market

Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:^[1]

• A set of $m$ divisible products with pre-specified quantities.
• A set of $n$ buyers.
• For each buyer $i=1,\dots,n$, there is a pre-specified monetary budget $Bdgt_i$.
• The budget has no intrinsic value - it is useful only for buying products.

Each product $j$ has a price $p_j$; the prices are determined by methods that we describe below. The price of a bundle of products is the sum of the prices of the products in the bundle. A bundle is represented by a vector $x = x_1,\dots,x_m$, where $x_j$ is the quantity of product $j$ (the quantities are normalized such that the total quantity from each product is 1, i.e, $x_j$ is the fraction of product $j$ in the bundle); the price of a bundle $x$ is $p(x)=\sum_{j=1}^m p_j\cdot x_j$.

A bundle is affordable for a buyer if the price of that bundle is at most the buyer's budget. I.e, a bundle $x$ is affordable for buyer $i$ if $p(x)\leq Bdgt_i$

Once the prices are determined, each buyer decides what bundle he wants to buy based on the prices and the buyer's cardinal utility function. The utility function of buyer $i$ is denoted by $u_i$. Each buyer selects an affordable bundle that maximizes his utility, i.e, a bundle $x=\arg\max u_i(x)$, where the maximum is over all affordable bundles.

Market-clearing prices are prices $p_1,\dots,p_m$ in which the total demand of each product is exactly equal to the total supply of that product (i.e, the market is in in competitive equilibrium). The main challenge in analyzing Fisher markets is to find market-clearing prices.^{[2]:103–105}

The homogeneous-utilities case

Suppose the utilities of all the buyers are homogeneous functions (this includes, in particular, utilities with constant elasticity of substitution).

Then, the equilibrium conditions in the Fisher model can be written as solutions to a convex optimization program called the Eisenberg-Gale convex program.^[3] 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( Bdgt_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$

(note that 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.^[4]:141-142

The linear-utilities case

A special case of homogeneous utilities is when all buyers have linear utility functions. This means that for every buyer $i$ and product $j$ there is a constant $u_{i,j}$ such that the total utility the buyer derives from a bundle is:

$u_i(x_1,\dots,x_j) = \sum_{j=1}^m u_{i,j}\cdot x_j$

We assume that each product has a potential buyer - a buyer that derives positive utility from that product. 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 utility-per-coin of a buyer (total utility divided by total budget) is weakly larger than his utility-per-coin from each single product: $\frac{\sum_{j=1}^m u_{i,j}\cdot x_{i,j}}{Bdgt_i} \geq \frac{u_{i,j}}{p_j}$
4. If a buyer buys a positive amount of a product, then his total utility-per-coin equals his utility-per-coin from that product: $x_{i,j}>0 \implies \frac{\sum_{j=1}^m u_{i,j}\cdot x_{i,j}}{Bdgt_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. ^[2]:107

Finding an equilibrium

There is a weakly polynomial-time 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 utility-per-coin. Let's say that a buyer "likes" a product, if that product gives him maximum utility-per-coin in the current prices. Given a price-vector, we can build 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 $Bdgt_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.^[2]:109-121

See also

• The Arrow–Debreu model is a generalization of the Fisher model, in which each agent can be both a buyer and a seller. I.e, each agent comes with a bundle of products, instead of only with money.
• General equilibrium
• Eisenberg–Gale markets - another generalization of the linear Fisher market.^[5]

References

1. Yishay Mansour (2011). "Lecture 10: Market Equilibrium" (PDF). Advanced Topics in Machine Learning and Algorithmic Game Theory. Retrieved 15 March 2016.
2. Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). "Chapter 5: Combinatorial Algorithms for Market Equilibria / Vijay V. Vazirani". Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
3. Eisenberg, E. (1961). "Aggregation of Utility Functions". Management Science 7 (4): 337. doi:10.1287/mnsc.7.4.337.
4. Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). "Chapter 6: Computation of Market Equilibria by Convex Programming / Bruno Codenotti and Kasturi Varadarajan". Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
5. Jain, Kamal; Vazirani, Vijay V. (2010). "Eisenberg–Gale markets: Algorithms and game-theoretic properties". Games and Economic Behavior 70: 84. doi:10.1016/j.geb.2008.11.011.