Each buyer has a preference relation over bundles, which can be represented by a utility function.
The demand set of a buyer is the set of affordable bundles that maximize the buyer's utility among all affordable bundles, i.e.: A competitive equilibrium (CE) is a price-vector
The main challenge in analyzing Fisher markets is finding a CE.
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.
While Sperner's lemma can be used to find a CE,[4] it is very inefficient computationally.
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.
maximum flow problems, and thus it runs in time
Orlin[6] gave an improved algorithm for a Fisher market model with linear utilities, running in time
He then improved his algorithm to run in strongly-polynomial time:
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.
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.
This work has led to several works on algorithms of finding CE in such markets: If both n and m are variable, the problem becomes computationally hard: 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.
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.
Miltersen, Hosseini and Branzei[18] proved that even verifying whether a given allocation is CEEI is co-NP-hard.
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.
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.