피셔 시장

피셔 시장은 어빙 피셔에게 귀속된 경제 모델이다. 이 제품에는 다음과 같은 성분이 있다.^[1]

• $미리{\displaystyle }$ 지정된 공급품과 함께 m ${\displaystyle m}$이(가) 분리할 수 있는 제품 세트(보통 각 재화의 공급이 1이 되도록 정규화됨).
• $n{\displaystyle }$ ${\displaystyle n}$개$$ 구매자 집합.
• ${\displaystyle 각}$ 구매자 $i{\displaystyle }$= ${\displaystyle 1}$, ${\displaystyle \dots ,}$ n ${\displaystyle i=1,\dots,n$에 대해 사전 지정된 통화 예산 ${\displaystyle B_{}}$ i ${\$가 있다$.$

각 제품 $j{\displaystyle }$ ${\displaystyle j}$은(는) 가격 $p{\displaystyle {}_{}}$j {\$displaystyle p_{j}$을(를) 가지고$$ 있으며$,$ 가격은 아래에 설명된 방법에 따라 결정된다. 상품 묶음 가격은 묶음 안에 있는 상품 가격을 합한 값이다. 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

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.

Sperner의 보조정리에는 정점이 m 다른 라벨로 표시된 아기-심플렉스(baby-simplex가 있다. 수요 함수는 연속적이기 때문에, 보다 미세하고 미세한 삼각측량을 통해 우리는 단일 가격-벡터 p*를 찾는데, 모든 제품이 비싸다는 것, 즉, 모든 제품의 총 수요는 최대 1이다.

그러나 모든 예산의 합계가 1이므로 p*의 모든 제품에 대한 총 수요는 정확히 1이어야 한다. 그러므로 p*는 시장을 선점하는 가격의 벡터다.

Sperner의 보조정리기는 CE를 찾는 데 사용될 수 있지만, 그것은 계산적으로 매우 비효율적이다. 더 효율적인 방법이 있다: 시장 균형 계산을 참조하십시오.

분리할 수 없는 품목이 있는 피셔 시장

시장에 있는 품목들이 분리될 수 없을 때, CE는 존재한다고 보장되지 않는다. CE의 존재 여부를 결정하는 것은 계산적으로 어려운 문제다.

덩 외 연구진은^[5] 각 대리인이 (초기소득이 아닌) 최초 기부금을 받고 모든 가치가 부가적인 시장을 연구했다. 그들은 CE의 존재 여부를 결정하는 것은 심지어 3명의 에이전트에도 NP-hard라는 것을 증명했다. 그들은 두 가지 방법으로 CE 조건을 완화시키는 근사 알고리즘을 제시하였다. (1) 각 대리점에 할당된 번들은 주어진 가격에서 최소 1 엡실론(epsilon)의 최적 값으로 평가되며, (2) 수요는 공급량의 최소 1 엡실론(epsilon)이다.

부베렛과 르메트르는^[6] 품목을 공정하게 배분하는 규칙으로 CEEI(동등분)를 공부했다. 그들은 모든 대리인이 부가 가치평가 기능을 가지고 있다고 가정하는 다른 네 가지 공정성 기준과 관련되었다. 그들은 CEEI의 존재 여부를 결정하는 계산상의 복잡성은 무엇인가에 대해 물었다.

이 질문은 곧이어 아지즈에 의해 답되었는데,^[7] 아지즈는 에이전트와 m 아이템이 두 개 있을 때는 약하게 NP-hard이고, n개의 에이전트와 3n 항목이 있을 때는 강하게 NP-hard임을 증명하였다. 그는 또한 CEEI-FRAC라는 더 강력한 조건을 제시했는데, 흥미롭게도, 검증이 더 쉬우며--- 다항식 시간 내에 검증될 수 있다. Miltersen, Hosseini, Branzei는^[8] 주어진 할당량이 CEEI인지 여부를 검증하는 것조차 NP-hard라는 것을 증명했다. 그들은 또한 CEEI를 단심제 에이전트에 대해서도 연구했다. 이 경우 주어진 할당량이 CEEI인지 확인하는 것은 다항식이지만 CEEI 존재여부를 확인하는 것은 공동 NP-완전이다.

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

• General equilibrium

References