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

slide_8

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:

  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∈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:

maximize, ∑i=1n’eilogui

subject to

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:

    1. ∀ j ∈ A : p≥ 0
    2. ∀ j ∈ A : p> 0 ⇒ ∑i∈A xij = 1
    3. ∀ i ∈ B, j ∈ A : uij/pj ≤ ∑j∈Auijxij/ei
    4. ∀ 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:

  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 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 : eij 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.

Banach Spaces

lbN6I

Some things in linear algebra are easier to see in infinite dimensions, i.e. in Banach spaces. Distinctions that seem pedantic in finite dimensions clearly matter in infinite dimensions.

The category of Banach spaces considers linear spaces and continuous linear transformations between them. In a finite dimensional Euclidean space, all linear transformations are continuous, but in infinite dimensions a linear transformation is not necessarily continuous.

The dual of a Banach space V is the space of continuous linear functions on V. Now we can see examples of where not only is V* not naturally isomorphic to V, it’s not isomorphic at all.

For any real p > 1, let q be the number such that 1/p  + 1/q = 1. The Banach space Lp is defined to be the set of (equivalence classes of) Lebesgue integrable functions f such that the integral of ||f||p is finite. The dual space of Lp is Lq. If p does not equal 2, then these two spaces are different. (If p does equal 2, then so does qL2 is a Hilbert space and its dual is indeed the same space.)

In the finite dimensional case, a vector space V is isomorphic to its second dual V**. In general, V can be embedded into V**, but V** might be a larger space. The embedding of V in V** is natural, both in the intuitive sense and in the formal sense of natural transformations. We can turn an element of V into a linear functional on linear functions on V as follows.

Let v be an element of V and let f be an element of V*. The action of v on f is simply fv. That is, v acts on linear functions by letting them act on it.

This shows that some elements of V** come from evaluation at elements of V, but there could be more. Returning to the example of Lebesgue spaces above, the dual of L1 is L, the space of essentially bounded functions. But the dual of L is larger than L1. That is, one way to construct a continuous linear functional on bounded functions is to multiply them by an absolutely integrable function and integrate. But there are other ways to construct linear functionals on L.

A Banach space V is reflexive if the natural embedding of V in V** is an isomorphism. For p > 1, the spaces Lp are reflexive.

Suppose that X is a Banach space. For simplicity, we assume that X is a real Banach space, though the results can be adapted to the complex case in the straightforward manner. In the following, B(x0,ε) stands for the closed ball of radius ε centered at x0 while B◦(x0,ε) stands for the open ball, and S(x0,ε) stands for the corresponding sphere.

Let Q be a bounded operator on X. Since we will be interested in the hyperinvariant subspaces of Q, we can assume without loss of generality that Q is one-to-one and has dense range, as otherwise ker Q or Range Q would be hyperinvariant for Q. By {Q}′ we denote the commutant of Q.

Fix a point x0 ≠ 0 in X and a positive real ε<∥x0∥. Let K= Q−1B(x0,ε). Clearly, K is a convex closed set. Note that 0 ∉ K and K≠ ∅ because Q has dense range. Let d = infK||z||, then d > 0. If X is reflexive, then there exists z ∈ K with ||z|| = d, such a vector is called a minimal vector for x0, ε and Q. Even without reflexivity condition, however, one can always find y ∈ K with ||y|| ≤ 2d, such a y will be referred to as a 2-minimal vector for x0, ε and Q.

The set K ∩ B(0, d) is the set of all minimal vectors, in general this set may be empty. If z is a minimal vector, since z ∈ K = Q−1B(x0, ε) then Qz ∈ B(x0, ε). As z is an element of minimal norm in K then, in fact, Qz ∈ S(x0, ε). Since Q is one-to-one, we have

QB(0, d) ∩ B(x0, ε) = Q B(0, d) ∩ K) ⊆ S(x0, ε).

It follows that QB(0,d) and B◦(x0,ε) are two disjoint convex sets. Since one of them has non-empty interior, they can be separated by a continuous linear functional. That is, there exists a functional f with ||f|| = 1 and a positive real c such that f|QB(0,d)  ≤ c and f|B◦(x0,ε) ≥ c. By continuity, f|B(x0,ε) ≥ c. We say that f is a minimal functional for x0, ε, and Q.

We claim that f(x0) ≥ ε. Indeed, for every x with ||x|| ≤ 1 we have x0 − εx ∈ B(x0,ε). It follows that f(x0 − εx) ≥ c, so that f(x0) ≥ c + εf(x). Taking sup over all x with ||x|| ≤ 1 we get f(x0) ≥ c + ε||f|| ≥ ε.

Observe that the hyperplane Qf = c separates K and B(0, d). Indeed, if z ∈ B(0,d), then (Qf)(z) = f(Qz) ≤ c, and if z ∈ K then Qz ∈ B(x0,ε) so that (Q∗f)(z) = f(Qz) ≥ c. For every z with ||z|| ≤ 1

we have dz ∈ B(0,d), so that (Qf)(dz) ≤ c, it follows that Qf ≤ c/d

On the other hand, for every δ > 0 there exists z ∈ K with ||z|| ≤ d+δ, then (Qf)(z) ≥ c ≥ c/(d+δ) ||z||, whence ||Qf|| ≥ c/(d+δ) . It follows that

||Q∗f|| = c/d.

For every z ∈ K we have (Qf)(z) ≥ c = d ||Qf||. In particular, if y is a 2-minimal vector then

(Qf)(y) ≥ 1/2 Qf ||y||….