Английская Википедия:Fisher market
Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:[1]
- 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 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.[2]Шаблон:Rp
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]
Шаблон:AnchorFisher market with divisible items
When all items in the market are divisible, a CE always exists. This can be proved using the famous Sperner's lemma.[4]Шаблон:Rp
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.
While Sperner's lemma can be used to find a CE, it is very inefficient computationally. There are more efficient methods: see market equilibrium computation.
Шаблон:AnchorFisher 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[5] 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[6] 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,[7] 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[8] 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[9] 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[10] 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[11] recently proved that the computation of approximate-CEEI is PPAD complete).
Barman and Krishnamurthy[12] 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[13] 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.[14]
See also
References
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite Algorithmic Game Theory 2007
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite arXiv
- ↑ Шаблон:Cite arXiv
- ↑ Шаблон:Cite journal
