Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:
Contents
Each product
A bundle is affordable for a buyer if the price of that bundle is at most the buyer's budget. I.e, a bundle
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
Market-clearing prices are prices
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. 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:
(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,
The linear-utilities case
A special case of homogeneous utilities is when all buyers have linear utility functions. This means that for every buyer
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
- All prices are non-negative:
p j ≥ 0 . - If a product has a positive price, then all its supply is exhausted:
p j > 0 ⟹ ∑ i = 1 n x i , j = 1 . - 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:
∑ j = 1 m u i , j ⋅ x i , j B d g t i ≥ u i , j p j - 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 ⟹ ∑ j = 1 m u i , j ⋅ x i , j B d g t i = u i , j p j
Assume that every product
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.
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:
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:
There is an algorithm that solves this problem in weakly polynomial time.