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 supplies (usually normalized such that the supply 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}}$.

Each product ${\displaystyle j}$ has a price ${\displaystyle p_{j}}$; the prices are determined by methods described 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 

Related models

• In the Fisher market model, the budget has no intrinsic value - it is useful only for buying products. This is in contrast to a Walrasian market with agents with quasilinear utilities, in which money is itself a product and it has value of its own.
• The Arrow–Debreu market 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.
• Eisenberg–Gale markets are another generalization of the linear Fisher market.[3]

Fisher market with divisible items

Existence of equilibrium

When all items in the market are divisible, a CE always exists. This can be proved using the famous Sperner's lemma.[4]: 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.

Computation of equilibrium

While Sperner's lemma can be used to find a CE,[4] it is very inefficient computationally. There are more efficient methods (see also market equilibrium computation).

Devanur, Papadimitriou, Saberi and Vazirani[5] 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[6] 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))}$.

Chen and Teng[7] proved that, when the agents' utilities can be arbitrary SPLC (Separable piecewise-linear concave) functions, finding a CE is PPAD-hard.

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)[8] and with a mixture of goods and bads.[9] 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[10] 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[11] 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[12] 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[13]), 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[14]: Thm.3  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.[14]: Thm.5 

Fisher markets with indivisible items

When the items in the market are indivisible, a CE is not guaranteed to exist. Deciding whether a CE exist is a computationally hard problem.

Deng et al[15] 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[16] 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,[17] 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[18] 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[19] 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[20] 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[21] recently proved that the computation of approximate-CEEI is PPAD complete).

Barman and Krishnamurthy[22] 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[23] 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.[24]

See also

• General equilibrium

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. 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.
4. Scarf, Herbert (1967). "The Core of an N Person Game". Econometrica. 35 (1): 50–69. doi:10.2307/1909383. JSTOR 1909383.
5. Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V. (2008-11-05). "Market equilibrium via a primal--dual algorithm for a convex program". Journal of the ACM. 55 (5): 22:1–22:18. doi:10.1145/1411509.1411512. ISSN 0004-5411. S2CID 11836728.
6. Orlin, James B. (2010-06-05). "Improved algorithms for computing fisher's market clearing prices". Proceedings of the forty-second ACM symposium on Theory of computing. STOC '10. Cambridge, Massachusetts, USA: Association for Computing Machinery. pp. 291–300. doi:10.1145/1806689.1806731. hdl:1721.1/68009. ISBN 978-1-4503-0050-6. S2CID 8235905.
7. Chen, Xi; Teng, Shang-Hua (2009). Dong, Yingfei; Du, Ding-Zhu; Ibarra, Oscar (eds.). "Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria". Algorithms and Computation. Lecture Notes in Computer Science. 5878. Berlin, Heidelberg: Springer: 647–656. arXiv:0907.4130. doi:10.1007/978-3-642-10631-6_66. ISBN 978-3-642-10631-6. S2CID 7817966.
8. Bogomolnaia, Anna; Moulin, Hervé; Sandomirskiy, Fedor; Yanovskaia, Elena (2019-03-01). "Dividing bads under additive utilities". Social Choice and Welfare. 52 (3): 395–417. doi:10.1007/s00355-018-1157-x. ISSN 1432-217X.
9. Bogomolnaia, Anna; Moulin, Hervé; Sandomirskiy, Fedor; Yanovskaya, Elena (2017). "Competitive Division of a Mixed Manna". Econometrica. 85 (6): 1847–1871. arXiv:1702.00616. doi:10.3982/ECTA14564. ISSN 1468-0262. S2CID 17081755.
10. Brânzei, Simina; Sandomirskiy, Fedor (2019-07-03). "Algorithms for Competitive Division of Chores". arXiv:1907.01766 [cs.GT].
11. Garg, Jugal; McGlaughlin, Peter (2020-05-05). "Computing Competitive Equilibria with Mixed Manna". Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '20. Auckland, New Zealand: International Foundation for Autonomous Agents and Multiagent Systems: 420–428. ISBN 978-1-4503-7518-4.
12. Chaudhury, Bhaskar Ray; Garg, Jugal; McGlaughlin, Peter; Mehta, Ruta (2021-01-01), "Competitive Allocation of a Mixed Manna", Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 1405–1424, arXiv:2008.02753, doi:10.1137/1.9781611976465.85, ISBN 978-1-61197-646-5
13. Chen, Xi; Teng, Shang-Hua (2009). Dong, Yingfei; Du, Ding-Zhu; Ibarra, Oscar (eds.). "Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria". Algorithms and Computation. Lecture Notes in Computer Science. 5878. Berlin, Heidelberg: Springer: 647–656. arXiv:0907.4130. doi:10.1007/978-3-642-10631-6_66. ISBN 978-3-642-10631-6. S2CID 7817966.
14. Chaudhury, Bhaskar Ray; Garg, Jugal; McGlaughlin, Peter; Mehta, Ruta (2020-08-01). "Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores". arXiv:2008.00285 [cs.GT].
15. 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.
16. 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. S2CID 16041218.
17. 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. S2CID 11495811.
18. 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. Vol. 9347. Springer, Berlin, Heidelberg. pp. 244–255. arXiv:1503.06855. doi:10.1007/978-3-662-48433-3_19. ISBN 9783662484326. S2CID 656603.
19. 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. Vol. 9346. Springer, Cham. pp. 521–536. doi:10.1007/978-3-319-23114-3_31. ISBN 9783319231136.
20. 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. S2CID 154703357.
21. 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. S2CID 2780775.
22. Barman, Siddharth; Krishnamurthy, Sanath Kumar (2018-11-21). "On the Proximity of Markets with Integral Equilibria". arXiv:1811.08673 [cs.GT].
23. Talgam-Cohen, Inbal; Nisan, Noam; Babaioff, Moshe (2017-03-23). "Competitive Equilibrium with Indivisible Goods and Generic Budgets". arXiv:1703.08150 [cs.GT].
24. 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. S2CID 210911501.