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 . The matrix and the RHS vector are all rational. Let be an optimal extreme point solution and the absolute value of the determinant of the optimal basis. Then, must be an integral vector. Equivalently, if in our original linear program we scale the constraints by , the new linear program has an optimal solution that is integral.

Now, apply this to the existence question. Let be a set of agents, a set of distinct goods and the utility that agent enjoys from consuming the bundle . Note, no restrictions on 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 if the bundle is assigned to agent and 0 otherwise. The program is

subject to

If we drop the integer constraints we have an LP. Let 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 such that must be in agent ‘s demand correspondence.

Let be the absolute value of the determinant of the optimal basis. We can write for all and where is an integer. Now construct an enlarged economy as follows.

Scale up the supply of each by a factor of . Replace each agent by 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 if bundle is allocated the clone of agent and zero otherwise. Let be the utility function of the clone of agent . Here is the corresponding integer program.

subject to

Its easy to see a feasible solution is to give for each and such that , the clones in a bundle . 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.

## 2 comments

October 11, 2012 at 4:35 pm

EduardoHi Rakesh,

beautiful argument, its nice to see things from a new angle, and this linear programming approach is may be useful to have in the quiver for the future. We had a result on finite economies that was cut from the paper, but we never considered this linear programming route.

October 13, 2012 at 1:29 pm

rvohraThank you, Eduardo. I suspect the same approach can be used for matching problems with couples or non-substitutable preferences, for example. The difficulty will be to show the existence of a feasible fractional solution to the assignment problem with blocking constraints.

Rakesh

rakesh