Consider a market consisting of a set B of buyers and a set A of divisible goods. Assume |A| = n and |B| = n′. We are given for each buyer i the amount ei of money she possesses and for each good j the amount bj of this good. In addition, we are given the utility functions of the buyers. Our critical assumption is that these functions are linear. Let uij denote the utility derived by i on obtaining a unit amount of good j. Thus if the buyer i is given xij units of good j, for 1 ≤ j ≤ n, then the happiness she derives is
∑j=1nuijxij —— (1)
Prices p1, . . . , pn of the goods are said to be market clearing prices if, after each buyer is assigned an optimal basket of goods relative to these prices, there is no surplus or deficiency of any of the goods. So, is it possible to compute such prices in polynomial time?
First observe that without loss of generality, we may assume that each bj is unit – by scaling the uij’s appropriately. The uij’s and ei’s are in general rational; by scaling appropriately, they may be assumed to be integral. By making the mild assumption that each good has a potential buyer, i.e., a buyer who derives nonzero utility from this good. Under this assumption, market clearing prices do exist.
It turns out that equilibrium allocations for Fisher’s linear case are captured as optimal solutions to a remarkable convex program, the Eisenberg–Gale convex program.
A convex program whose optimal solution is an equilibrium allocation must have as constraints the packing constraints on the xij’s. Furthermore, its objective function, which attempts to maximize utilities derived, should satisfy the following:
- If the utilities of any buyer are scaled by a constant, the optimal allocation remains unchanged.
- If the money of a buyer b is split among two new buyers whose utility functions are the same as that of b then sum of the optimal allocations of the new buyers should be an optimal allocation for b.
The money weighted geometric mean of buyers’ utilities satisfies both these conditions:
max (∏i∈Auiei)1/∑iei —– (2)
then, the following objective function is equivalent:
max (∏i∈Auiei) —– (3)
Its log is used in the Eisenberg–Gale convex program:
ui = ∑j=1nuijxij ∀ i ∈ B
∑i=1n’ xij ≤ 1 ∀ j ∈ A
xij ≥ 0 ∀ i ∈ B, j ∈ A —– (4)
where xij is the amount of good j allocated to buyer i. Interpret Lagrangian variables, say pj’s, corresponding to the second set of conditions as prices of goods. Optimal solutions to xij’s and pj’s must satisfy the following:
- ∀ j ∈ A : pj ≥ 0
- ∀ j ∈ A : pj > 0 ⇒ ∑i∈A xij = 1
- ∀ i ∈ B, j ∈ A : uij/pj ≤ ∑j∈Auijxij/ei
- ∀ i ∈ B, j ∈ A : xij > 0 ⇒ uij/pj = ∑j∈Auijxij/ei
From these conditions, one can derive that an optimal solution to convex program (4) must satisfy the market clearing conditions.
For the linear case of Fisher’s model:
- If each good has a potential buyer, equilibrium exists.
- The set of equilibrium allocations is convex.
- Equilibrium utilities and prices are unique.
- If all uij’s and ei’s are rational, then equilibrium allocations and prices are also rational. Moreover, they can be written using polynomially many bits in the length of the instance.
Corresponding to good j there is a buyer i such that uij > 0. By the third condition as stated above,
pj ≥ eiuij/∑juijxij > 0
By the second condition, ∑i∈A xij = 1, implying that prices of all goods are positive and all goods are fully sold. The third and fourth conditions imply that if buyer i gets good j then j must be among the goods that give buyer i maximum utility per unit money spent at current prices. Hence each buyer gets only a bundle consisting of her most desired goods, i.e., an optimal bundle.
The fourth condition is equivalent to
∀ i ∈ B, j ∈ A : eiuijxij/∑j∈Auijxij = pjxij
Summing over all j
∀ i ∈ B : ei∑j uijxij/∑j∈Auijxij = pjxij
⇒ ∀ i ∈ B : ei = ∑jpjxij
Hence the money of each buyer is fully spent completing the proof that market equilibrium exists. Since each equilibrium allocation is an optimal solution to the Eisenberg-Gale convex program, the set of equilibrium allocations must form a convex set. Since log is a strictly concave function, if there is more than one equilibrium, the utility derived by each buyer must be the same in all equilibria. This fact, together with the fourth condition, gives that the equilibrium prices are unique.