You are currently browsing the monthly archive for September 2012.

A paper by Azevdo, Weyl and White in a recent issue of Theoretical Economics caught my eye. It establishes existence of Walrasian prices in an economy with indivisible goods, a continuum of agents and quasilinear utility. The proof uses Kakutani’s theorem. Here is an argument based on an observation about extreme points of linear programs. It shows that there is a way to scale up the number of agents and goods, so that in the scaled up economy a Walrasian equilibrium exists.
First, the observation. Consider {\max \{cx: Ax = b, x \geq 0\}}. The matrix {A} and the RHS vector {b} are all rational. Let {x^*} be an optimal extreme point solution and {\Delta} the absolute value of the determinant of the optimal basis. Then, {\Delta x^*} must be an integral vector. Equivalently, if in our original linear program we scale the constraints by {\Delta}, the new linear program has an optimal solution that is integral.

Now, apply this to the existence question. Let {N} be a set of agents, {G} a set of distinct goods and {u_i(S)}the utility that agent {i} enjoys from consuming the bundle {S \subseteq G}. Note, no restrictions on {u} beyond non-negativity and quasi-linearity.

As utilities are quasi-linear we can formulate the problem of finding the efficient allocation of goods to agents as an integer program. Let {x_i(S) = 1} if the bundle {S} is assigned to agent {i} and 0 otherwise. The program is

\displaystyle \max \sum_{i \in N}\sum_{S \subseteq G}u_i(S)x_i(S)

subject to
\displaystyle  \sum_{S \subseteq G}x_i(S) \leq 1\,\, \forall i \in N

\displaystyle \sum_{i \in N}\sum_{S \ni g} x_i(S) \leq 1 \forall g \in G

\displaystyle x_i(S) \in \{0,1\}\,\, \forall i \in N, S \subseteq G

If we drop the integer constraints we have an LP. Let {x^*} be an optimal solution to that LP. Complementary slackness allows us to interpret the dual variables associated with the second constraint as Walrasian prices for the goods. Also, any bundle {S} such that {x_i^*(S) > 0} must be in agent {i}‘s demand correspondence.
Let {\Delta} be the absolute value of the determinant of the optimal basis. We can write {x_i^*(S) = \frac{z_i^*(S)}{\Delta}} for all {i \in N} and {S \subseteq G} where {z_i^*(S)} is an integer. Now construct an enlarged economy as follows.

Scale up the supply of each {g \in G} by a factor of {\Delta}. Replace each agent {i \in N} by {N_i = \sum_{S \subseteq G}z_i^*(S)} clones. It should be clear now where this is going, but lets dot the i’s. To formulate the problem of finding an efficient allocation in this enlarged economy let {y_{ij}(S) = 1} if bundle {S} is allocated the {j^{th}} clone of agent {i} and zero otherwise. Let {u_{ij}(S)} be the utility function of the {j^{th}} clone of agent {i}. Here is the corresponding integer program.

\displaystyle \max \sum_{i \in N}\sum_{j \in N_i}\sum_{S \subseteq G}u_{ij}(S)y_{ij}(S)

subject to
\displaystyle  \sum_{S \subseteq G}y_{ij}(S) \leq 1\,\, \forall i \in N, j \in N_i

\displaystyle \sum_{i \in N}\sum_{j \in N_i}\sum_{S \ni g} y_{ij}(S) \leq \Delta \forall g \in G

\displaystyle y_{ij}(S) \in \{0,1\}\,\, \forall i \in N, j \in N_i, S \subseteq G

Its easy to see a feasible solution is to give for each {i} and {S} such that {z_i^*(S) > 0}, the {z_i^*(S)} clones in {N_i} a bundle {S}. The optimal dual variables from the relaxation of the first program complements this solution which verifies optimality. Thus, Walrasian prices that support the efficient allocation in the augmented economy exist.

Kellogg faculty blogroll