Fisher market

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

• A set of ${\displaystyle m}$ divisible products with pre-specified quantities (usually normalized such that the quantity of each good is 1).
• A set of ${\displaystyle n}$ buyers.
• For each buyer ${\displaystyle i=1,\dots ,n}$, there is a pre-specified monetary budget ${\displaystyle B_{i}}$(usually normalized such that the sum of budgets is 1).

In the Fisher model, the budget has no intrinsic value - it is useful only for buying products. This is in contrast to a quasilinear utility model, in which money is itself a product and it has value of its own.

Each product ${\displaystyle j}$ has a price ${\displaystyle 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 ${\displaystyle x=x_{1},\dots ,x_{m}}$, where ${\displaystyle x_{j}}$ is the quantity of product ${\displaystyle j}$. So the price of a bundle ${\displaystyle x}$ is ${\displaystyle 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 ${\displaystyle x}$ is affordable for buyer ${\displaystyle i}$ if ${\displaystyle p(x)\leq B_{i}}$.

Each buyer has a preference relation over bundles, which can be represented by a utility function. The utility function of buyer ${\displaystyle i}$ is denoted by ${\displaystyle u_{i}}$. The demand set of a buyer is the set of affordable bundles that maximize the buyer's utility among all affordable bundles, i.e.:

${\displaystyle {\text{Demand}}_{i}(p):=\arg \max _{p(x)\leq B_{i}}u_{i}(x)}$.

A competitive equilibrium (CE) is a price-vector ${\displaystyle p_{1},\dots ,p_{m}}$in which it is possible to allocate, to each agent, a bundle from his demand-set, such that the total allocation exactly equals the supply of products. The corresponding prices are called market-clearing prices. The main challenge in analyzing Fisher markets is finding a CE.[2]^:103–105

Existence of competitive equilibrium

The existence of a CE can be proved based on the famous Sperner's lemma.[3]^:67

Assume the quantities are normalized so that there is 1 unit per product, and the budgets are normalized so that their sum is 1. Also assume that all products are good, i.e., an agent always strictly prefers to have more of each product, if he can afford it.

Consider the standard simplex with m vertices. Each point in this simplex corresponds to a price-vector, where the sum of all prices is 1; hence the price of all goods together is 1.

In each price-vector p, we can find a demanded set of each agent, then calculate the sum of all demanded sets, then find the total price of this aggregate demand. Since the price of each demanded set is at most the agent's budget, and the sum of budgets is at most 1, the price of the aggregate demand is at most 1. Hence, for each p, there is at least one product for which the total demand is at most 1. Let's call such product an "expensive product" in p.

Triangulate the m-vertex simplex, and label each triangulation-vertex p with an index of an arbitrary expensive-product in p. In each face of the simplex, some products cost 0. Since all products are good, the demand of each agent for a product that costs 0 is always 1; hence a product which costs 0 can never be considered expensive. Hence, the above labeling satisfies Sperner's boundary condition.

By Sperner's lemma, there exists a baby-simplex whose vertices are labeled with m different labels. Since the demand function is continuous, by taking finer and finer triangulations we find a single price-vector p*, in which all products are expensive, i.e., the aggregate demand for every product is at most 1.

But, since the sum of all budgets is 1, the aggregate demand for every product in p* must be exactly 1. Hence p* is a vector of market-clearing prices.

Calculation of competitive equilibrium

While Sperner's lemma can be used to find a CE, it is very inefficient computationally. There are much more efficient methods, which are usually based on convex programming or linear programming.

Homogeneous utilities

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.[4] 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}\geq 0}$

Sufficient supplies: For every product ${\displaystyle j}$: ${\displaystyle \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, ${\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.[5]^:141–142

Linear utilities

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

${\displaystyle u_{i}(x_{1},\dots ,x_{j})=\sum _{j=1}^{m}u_{i,j}\cdot x_{j}}$, where ${\displaystyle u_{i,j}\geq 0}$

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 ${\displaystyle x_{i,j}}$ and prices ${\displaystyle p_{j}}$) satisfy the following inequalities:

1. All prices are non-negative: ${\displaystyle p_{j}\geq 0}$.
2. If a product has a positive price, then all its supply is exhausted: ${\displaystyle 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: ${\displaystyle {\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 utility-per-coin equals his utility-per-coin from that product: ${\displaystyle 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 ${\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.[2]^:107

Weakly polynomial-time algorithm

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 ${\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.[2]^:109–121

Fisher markets with indivisible items

While the original model assumed that all products are divisible, there is a variant of Fisher market in which the items are assumed to be indivisible. In this variant, finding a competitive equilibrium is computationally hard.

Deng et al[6] studied a market to which each agent comes with an initial endowment (rather than an initial income) and all valuations are additive. They proved that deciding whether CE exists is NP-hard even with 3 agents. They presented an approximation algorithm which relaxes the CE conditions in two ways: (1) The bundle allocated to each agent is valued at least 1-epsilon of the optimum given the prices, and (2) the demand is at least 1-epsilon times the supply.

Bouveret and Lemaitre[7] studied CE-from-equal-incomes (CEEI) as a rule for fair allocation of items. They related it to four other fairness criteria assuming all agents have additive valuation functions. They asked what is the computational complexity of deciding whether CEEI exists.

This question was answered soon afterwards by Aziz,[8] who proved that the problem is weakly NP-hard when there are two agents and m items, and strongly NP-hard when there are n agents and 3n items. He also presented a stronger condition called CEEI-FRAC which is, interestingly, easier to verify --- it can be verified in polynomial time. Miltersen, Hosseini and Branzei[9] proved that even verifying whether a given allocation is CEEI is co-NP-hard. They studied CEEI also for single-minded agents. In this case, verifying whether a given allocation is CEEI is polynomial but checking if CEEI exists is co-NP-complete.

Heinen et al[10] extended the work of Bouveret and Lemaitre from additive to k-additive utility functions, in which each agent reports a value for bundles containing at most k items, and the values of larger bundles are determined by adding and subtracting the values of the basic bundles.

Budish[11] studied the most general setting in which agents can have arbitrary preference relations over bundles. He invented the mechanism of Approximate Competitive Equilibrium from Equal Incomes, which relaxes the CEEI conditions in two ways: (1) The agents' incomes are not exactly equal, and (2) a small number of items may remain unallocated. He proved that an approximate-CEEI always exists (although Othman et al[12] recently proved that the computation of approximate-CEEI is PPAD complete).

Barman and Krishnamurthy[13] study Fisher markets in which all agents have additive utilities. They show that a fractional CE (where some goods are divided) can always be rounded to an integral CE (where goods remain indivisible), by changing the agents' budgets. The change in each budget can be as high as the largest price of a good in the fractional CE.

Babaioff, Nisan and Talgam-Cohen[14] studied whether CE exists when the incomes are generic, i.e., do not satisfy a finite set of equalities. In other words: whether there exists a CE for almost all income-vectors. They proved existence for three goods, and for four goods and two agents. They proved non-existence for five goods and two agents. Later, it has proved that with four goods and three agents, CE may not exist when the valuations are non-additive, but always exists when the valuations are additive.[15]

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.[16]

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. Scarf, Herbert (1967). "The Core of an N Person Game". Econometrica. 35 (1): 50–69. doi:10.2307/1909383. JSTOR 1909383.
4. Eisenberg, E. (1961). "Aggregation of Utility Functions". Management Science. 7 (4): 337–350. doi:10.1287/mnsc.7.4.337.
5. 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.
6. Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel (2003-09-01). "On the complexity of price equilibria". Journal of Computer and System Sciences. 67 (2): 311–324. doi:10.1016/S0022-0000(03)00011-4. ISSN 0022-0000.
7. Lemaître, Michel; Bouveret, Sylvain (2016-03-01). "Characterizing conflicts in fair division of indivisible goods using a scale of criteria". Autonomous Agents and Multi-Agent Systems. 30 (2): 259–290. doi:10.1007/s10458-015-9287-3. ISSN 1573-7454.
8. Aziz, Haris (2015-11-01). "Competitive equilibrium with equal incomes for allocation of indivisible objects". Operations Research Letters. 43 (6): 622–624. arXiv:1501.06627. Bibcode:2015arXiv150106627A. doi:10.1016/j.orl.2015.10.001. ISSN 0167-6377.
9. Miltersen, Peter Bro; Hosseini, Hadi; Brânzei, Simina (2015-09-28). Characterization and Computation of Equilibria for Indivisible Goods. Algorithmic Game Theory. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. pp. 244–255. arXiv:1503.06855. doi:10.1007/978-3-662-48433-3_19. ISBN 9783662484326.
10. Rothe, Jörg; Nguyen, Nhan-Tam; Heinen, Tobias (2015-09-27). Fairness and Rank-Weighted Utilitarianism in Resource Allocation. Algorithmic Decision Theory. Lecture Notes in Computer Science. Springer, Cham. pp. 521–536. doi:10.1007/978-3-319-23114-3_31. ISBN 9783319231136.
11. Budish, Eric (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy. 119 (6): 1061–1103. CiteSeerX 10.1.1.357.9766. doi:10.1086/664613.
12. Othman, Abraham; Papadimitriou, Christos; Rubinstein, Aviad (2016-08-01). "The Complexity of Fairness Through Equilibrium". ACM Transactions on Economics and Computation. 4 (4): 20:1–20:19. CiteSeerX 10.1.1.747.956. doi:10.1145/2956583. ISSN 2167-8375.
13. Barman, Siddharth; Krishnamurthy, Sanath Kumar (2018-11-21). "On the Proximity of Markets with Integral Equilibria". arXiv:1811.08673 [cs.GT].
14. Talgam-Cohen, Inbal; Nisan, Noam; Babaioff, Moshe (2017-03-23). "Competitive Equilibrium with Indivisible Goods and Generic Budgets". arXiv:1703.08150 [cs.GT].
15. Segal-Halevi, Erel (2020-02-20). "Competitive equilibrium for almost all incomes: existence and fairness". Autonomous Agents and Multi-Agent Systems. 34 (1): 26. arXiv:1705.04212. doi:10.1007/s10458-020-09444-z. ISSN 1573-7454.
16. Jain, Kamal; Vazirani, Vijay V. (2010). "Eisenberg–Gale markets: Algorithms and game-theoretic properties". Games and Economic Behavior. 70: 84–106. doi:10.1016/j.geb.2008.11.011.