Equilibrium Market Prices are Unique – Convexity and Concavity Utility Functions on a Linear Case. Note Quote + Didactics.

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 e_i of money she possesses and for each good j the amount b_j of this good. In addition, we are given the utility functions of the buyers. Our critical assumption is that these functions are linear. Let u_ij denote the utility derived by i on obtaining a unit amount of good j. Thus if the buyer i is given x_ij units of good j, for 1 ≤ j ≤ n, then the happiness she derives is

∑_j=1ⁿu_ijx_ij —— (1)

Prices p₁, . . . , p_n 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 b_j is unit – by scaling the u_ij’s appropriately. The u_ij’s and e_i’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 x_ij’s. Furthermore, its objective function, which attempts to maximize utilities derived, should satisfy the following:

1. If the utilities of any buyer are scaled by a constant, the optimal allocation remains unchanged.
2. 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∈Au_i^ei)^1/∑_ie_i —– (2)

then, the following objective function is equivalent:

max (∏_i∈Au_i^ei) —– (3)

Its log is used in the Eisenberg–Gale convex program:

maximize, ∑_i=1^n’e_ilogu_i

subject to

u_i = ∑_j=1ⁿu_ijx_ij ∀ i ∈ B

∑_i=1^n’ x_ij ≤ 1 ∀ j ∈ A

x_ij ≥ 0 ∀ i ∈ B, j ∈ A —– (4)

where x_ij is the amount of good j allocated to buyer i. Interpret Lagrangian variables, say p_j’s, corresponding to the second set of conditions as prices of goods. Optimal solutions to x_ij’s and p_j’s must satisfy the following:

1. 1. ∀ j ∈ A : p_j ≥ 0
   2. ∀ j ∈ A : p_j > 0 ⇒ ∑_i∈A x_ij = 1
   3. ∀ i ∈ B, j ∈ A : u_ij/p_j ≤ ∑_j∈Au_ijx_ij/e_i
   4. ∀ i ∈ B, j ∈ A : x_ij > 0 ⇒ u_ij/p_j = ∑_j∈Au_ijx_ij/e_i

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:

1. If each good has a potential buyer, equilibrium exists.
2. The set of equilibrium allocations is convex.
3. Equilibrium utilities and prices are unique.
4. If all u_ij’s and e_i’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 u_ij > 0. By the third condition as stated above,

p_j ≥ e_iu_ij/∑_ju_ijx_ij > 0

By the second condition, ∑_i∈A x_ij = 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 : e_iu_ijx_ij/∑_j∈Au_ijx_ij = p_jx_ij

Summing over all j

∀ i ∈ B : e_i∑_j u_ijx_ij/∑_j∈Au_ijx_ij = p_jx_ij

⇒ ∀ i ∈ B : e_i = ∑_jp_jx_ij

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.

Advertisement