View source for Fisher market

'''Fisher market''' is an [[economic model]] attributed to [[Irving Fisher]]. It has the following ingredients:<ref name="m11">{{cite web | url=http://www.tau.ac.il/~mansour/advanced-agt+ml/scribe-10-market-EQ.pdf | title=Lecture 10: Market Equilibrium | work=Advanced Topics in Machine Learning and Algorithmic Game Theory | date=2011| accessdate=15 March 2016 | author=Yishay Mansour}}</ref>
* A set of <math>m</math> divisible products with pre-specified supplies (usually normalized such that the supply of each good is 1).
* A set of <math>n</math> buyers.
* For each buyer <math>i=1,\dots,n</math>, there is a pre-specified monetary budget <math>B_i</math>.

Each product <math>j</math> has a price <math>p_j</math>; 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 <math>x = x_1,\dots,x_m</math>, where <math>x_j</math> is the quantity of product <math>j</math>. So the price of a bundle <math>x</math> is <math>p(x)=\sum_{j=1}^m p_j\cdot x_j</math>.

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

Each buyer has a [[Preference (economics)|preference relation]] over bundles, which can be represented by a utility function. The utility function of buyer <math>i</math> is denoted by <math>u_i</math>.  The ''demand set'' of a buyer is the set of affordable bundles that maximize the buyer's utility among all affordable bundles, i.e.: 

:<math>\text{Demand}_i(p) := \arg\max_{p(x)\leq B_i} u_i(x)</math>.

A '''[[competitive equilibrium]]''' (CE) is a price-vector <math>p_1,\dots,p_m</math>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.<ref name="agt5">{{Cite Algorithmic Game Theory 2007|chapter=Chapter 5: Combinatorial Algorithms for Market Equilibria / Vijay V. Vazirani}}</ref>{{rp|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 model|'''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.<ref>{{Cite journal|last1=Jain|first1=Kamal|last2=Vazirani|first2=Vijay V.|year=2010|title=Eisenberg–Gale markets: Algorithms and game-theoretic properties|journal=Games and Economic Behavior|volume=70|pages=84–106|doi=10.1016/j.geb.2008.11.011}}</ref>

== {{Anchor|indivisible}}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]].<ref name=":0">{{Cite journal|last=Scarf|first=Herbert|date=1967|title=The Core of an N Person Game|jstor=1909383|journal=Econometrica|volume=35|issue=1|pages=50–69|doi=10.2307/1909383}}</ref>{{Rp|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''{{sup|&lowast;}}, 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''{{sup|&lowast;}} must be exactly 1. Hence ''p''{{sup|&lowast;}} is a vector of market-clearing prices.

=== Computation of equilibrium ===
While Sperner's lemma can be used to find a CE,<ref name=":0" /> it is very inefficient computationally. There are more efficient methods (see also [[market equilibrium computation]]).

Devanur, Papadimitriou, Saberi and [[Vijay Vazirani|Vazirani]]<ref>{{Cite journal |last1=Devanur |first1=Nikhil R. |last2=Papadimitriou |first2=Christos H. |last3=Saberi |first3=Amin |last4=Vazirani |first4=Vijay V. |date=2008-11-05 |title=Market equilibrium via a primal--dual algorithm for a convex program |url=https://doi.org/10.1145/1411509.1411512 |journal=Journal of the ACM |volume=55 |issue=5 |pages=22:1–22:18 |doi=10.1145/1411509.1411512 |issn=0004-5411 |s2cid=11836728}}</ref> 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<math>O((n+m)^5\log(u_{\max}) + (n+m)^4\log{B_{\max}})</math> [[Maximum flow problem|maximum flow problems]], and thus it runs in time  <math>O((n+m)^8\log(u_{\max}) + (n+m)^7\log{B_{\max}})</math>, where ''u''<sub>max</sub> and ''B''<sub>max</sub> are the maximum utility and budget, respectively.

Orlin<ref>{{Cite book |last=Orlin |first=James B. |title=Proceedings of the forty-second ACM symposium on Theory of computing |date=2010-06-05 |publisher=Association for Computing Machinery |isbn=978-1-4503-0050-6 |series=STOC '10 |location=Cambridge, Massachusetts, USA |pages=291–300 |chapter=Improved algorithms for computing fisher's market clearing prices |doi=10.1145/1806689.1806731 |hdl=1721.1/68009 |chapter-url=https://doi.org/10.1145/1806689.1806731 |hdl-access=free |s2cid=8235905}}</ref> gave an improved algorithm for a Fisher market model with linear utilities, running in time <math>O((n+m)^4\log(u_{\max}) + (n+m)^3 B_{\max})</math>. He then improved his algorithm to run in [[Strongly polynomial time|strongly-polynomial time]]: <math>O((m+n)^4\log(m+n))</math>.

Chen and Teng<ref name=":2">{{Cite journal |last1=Chen |first1=Xi |last2=Teng |first2=Shang-Hua |date=2009 |editor-last=Dong |editor-first=Yingfei |editor2-last=Du |editor2-first=Ding-Zhu |editor3-last=Ibarra |editor3-first=Oscar |title=Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria |url=https://link.springer.com/chapter/10.1007/978-3-642-10631-6_66 |journal=Algorithms and Computation |series=Lecture Notes in Computer Science |language=en |location=Berlin, Heidelberg |publisher=Springer |volume=5878 |pages=647–656 |arxiv=0907.4130 |doi=10.1007/978-3-642-10631-6_66 |isbn=978-3-642-10631-6 |s2cid=7817966}}</ref> 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)<ref>{{Cite journal |last1=Bogomolnaia |first1=Anna |last2=Moulin |first2=Hervé |last3=Sandomirskiy |first3=Fedor |last4=Yanovskaia |first4=Elena |date=2019-03-01 |title=Dividing bads under additive utilities |journal=Social Choice and Welfare |language=en |volume=52 |issue=3 |pages=395–417 |doi=10.1007/s00355-018-1157-x |issn=1432-217X |doi-access=free}}</ref> and with a mixture of goods and bads.<ref>{{Cite journal |last1=Bogomolnaia |first1=Anna |last2=Moulin |first2=Hervé |last3=Sandomirskiy |first3=Fedor |last4=Yanovskaya |first4=Elena |date=2017 |title=Competitive Division of a Mixed Manna |url=https://onlinelibrary.wiley.com/doi/abs/10.3982/ECTA14564 |journal=Econometrica |language=en |volume=85 |issue=6 |pages=1847–1871 |arxiv=1702.00616 |doi=10.3982/ECTA14564 |issn=1468-0262 |s2cid=17081755}}</ref> 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<ref>{{cite arXiv |eprint=1907.01766 |class=cs.GT |first1=Simina |last1=Brânzei |first2=Fedor |last2=Sandomirskiy |title=Algorithms for Competitive Division of Chores |date=2019-07-03}}</ref> 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 problem|maximum flow]] computation.
* Garg and McGlaughlin<ref>{{Cite journal |last1=Garg |first1=Jugal |last2=McGlaughlin |first2=Peter |date=2020-05-05 |title=Computing Competitive Equilibria with Mixed Manna |url=https://dl.acm.org/doi/abs/10.5555/3398761.3398814 |journal=Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems |series=AAMAS '20 |location=Auckland, New Zealand |publisher=International Foundation for Autonomous Agents and Multiagent Systems |pages=420–428 |doi= |isbn=978-1-4503-7518-4}}</ref> 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<ref>{{Citation |last1=Chaudhury |first1=Bhaskar Ray |title=Competitive Allocation of a Mixed Manna |date=2021-01-01 |work=Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) |pages=1405–1424 |series=Proceedings |publisher=Society for Industrial and Applied Mathematics |arxiv=2008.02753 |doi=10.1137/1.9781611976465.85 |isbn=978-1-61197-646-5 |last2=Garg |first2=Jugal |last3=McGlaughlin |first3=Peter |last4=Mehta |first4=Ruta |doi-access=free}}</ref> 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–Howson algorithm|Lemke]]'s scheme. While its worst-case runtime is not polynomial (the problem is PPAD-hard even with goods<ref name=":22">{{Cite journal |last1=Chen |first1=Xi |last2=Teng |first2=Shang-Hua |date=2009 |editor-last=Dong |editor-first=Yingfei |editor2-last=Du |editor2-first=Ding-Zhu |editor3-last=Ibarra |editor3-first=Oscar |title=Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria |url=https://link.springer.com/chapter/10.1007/978-3-642-10631-6_66 |journal=Algorithms and Computation |series=Lecture Notes in Computer Science |language=en |location=Berlin, Heidelberg |publisher=Springer |volume=5878 |pages=647–656 |arxiv=0907.4130 |doi=10.1007/978-3-642-10631-6_66 |isbn=978-3-642-10631-6 |s2cid=7817966}}</ref>), 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<ref name=":1">{{cite arXiv |eprint=2008.00285 |class=cs.GT |first1=Bhaskar Ray |last1=Chaudhury |first2=Jugal |last2=Garg |title=Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores |date=2020-08-01 |last3=McGlaughlin |first3=Peter |last4=Mehta |first4=Ruta}}</ref>{{Rp|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.<ref name=":1" />{{Rp|Thm.5}}

== {{Anchor|indivisible}}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<ref>{{Cite journal|date=2003-09-01|title=On the complexity of price equilibria|journal=Journal of Computer and System Sciences|language=en|volume=67|issue=2|pages=311–324|doi=10.1016/S0022-0000(03)00011-4|issn=0022-0000|last1=Deng|first1=Xiaotie|last2=Papadimitriou|first2=Christos|last3=Safra|first3=Shmuel|doi-access=free}}</ref> 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<ref>{{Cite journal|last1=Lemaître|first1=Michel|last2=Bouveret|first2=Sylvain|date=2016-03-01|title=Characterizing conflicts in fair division of indivisible goods using a scale of criteria|journal=Autonomous Agents and Multi-Agent Systems|language=en|volume=30|issue=2|pages=259–290|doi=10.1007/s10458-015-9287-3|s2cid=16041218|issn=1573-7454}}</ref> 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,<ref>{{Cite journal|date=2015-11-01|title=Competitive equilibrium with equal incomes for allocation of indivisible objects|journal=Operations Research Letters|language=en|volume=43|issue=6|pages=622–624|doi=10.1016/j.orl.2015.10.001|issn=0167-6377|last1=Aziz|first1=Haris|arxiv=1501.06627|bibcode=2015arXiv150106627A|s2cid=11495811}}</ref> 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 3''n'' 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<ref>{{Cite book|last1=Miltersen|first1=Peter Bro|last2=Hosseini|first2=Hadi|last3=Brânzei|first3=Simina|title=Algorithmic Game Theory |chapter=Characterization and Computation of Equilibria for Indivisible Goods |date=2015-09-28|series=Lecture Notes in Computer Science|volume=9347 |language=en|publisher=Springer, Berlin, Heidelberg|pages=244–255|doi=10.1007/978-3-662-48433-3_19|isbn=9783662484326|arxiv=1503.06855|s2cid=656603}}</ref> 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<ref>{{Cite book|last1=Rothe|first1=Jörg|last2=Nguyen|first2=Nhan-Tam|last3=Heinen|first3=Tobias|title=Algorithmic Decision Theory |chapter=Fairness and Rank-Weighted Utilitarianism in Resource Allocation |date=2015-09-27|series=Lecture Notes in Computer Science|volume=9346 |language=en|publisher=Springer, Cham|pages=521–536|doi=10.1007/978-3-319-23114-3_31|isbn=9783319231136}}</ref> 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<ref>{{Cite journal|doi=10.1086/664613|title = The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes|journal = Journal of Political Economy|volume = 119|issue = 6|pages = 1061–1103|year = 2011|last1 = Budish|first1 = Eric|citeseerx = 10.1.1.357.9766|s2cid = 154703357}}</ref> 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<ref>{{Cite journal|last1=Othman|first1=Abraham|last2=Papadimitriou|first2=Christos|last3=Rubinstein|first3=Aviad|date=2016-08-01|title=The Complexity of Fairness Through Equilibrium|journal= ACM Transactions on Economics and Computation|volume=4|issue=4|pages=20:1–20:19|doi=10.1145/2956583|issn=2167-8375|citeseerx=10.1.1.747.956|s2cid=2780775}}</ref> recently proved that the computation of approximate-CEEI is [[PPAD (complexity)|PPAD complete]]).

Barman and Krishnamurthy<ref>{{cite arXiv|last1=Barman|first1=Siddharth|last2=Krishnamurthy|first2=Sanath Kumar|date=2018-11-21|title=On the Proximity of Markets with Integral Equilibria|eprint=1811.08673|class=cs.GT}}</ref> 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<ref>{{cite arXiv|last1=Talgam-Cohen|first1=Inbal|last2=Nisan|first2=Noam|last3=Babaioff|first3=Moshe|date=2017-03-23|title=Competitive Equilibrium with Indivisible Goods and Generic Budgets|eprint=1703.08150|language=en|class=cs.GT}}</ref> 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.<ref>{{Cite journal|last=Segal-Halevi|first=Erel|date=2020-02-20|title=Competitive equilibrium for almost all incomes: existence and fairness|journal=Autonomous Agents and Multi-Agent Systems|language=en|volume=34|issue=1|pages=26|doi=10.1007/s10458-020-09444-z|issn=1573-7454|arxiv=1705.04212|s2cid=210911501}}</ref>

== See also ==
* [[General equilibrium]]

== References ==
{{reflist}}

[[Category:General equilibrium theory]]
[[Category:Econometric models]]