The Gale-Eisenberg is a nice example were the distributed decisions of buyers and sellers have an equilibrium which solves an optimization problem.
Consider a market. There are buyers indexed by each with a budget , and there are sellers indexed by each selling units of single good. We suppose each seller sells a different good. Suppose that buyer values good by .
The seller sets a price for his good and buyer decides how much of that good she wishes to buy . Let’s consider some reasonable conditions for and to satisfy.
Buyers can’t buy more good than there is stocked, and we can perhaps assume that a good can only be worth something when all that good will be purchased. Thus, for all , the following condition holds
Given the prices set by the sellers, the buyers will attempt to maximize the value of the goods they buy. So, each solves
This is a knap-sack problem. Here a buyer will only purchase an item with the most value per unit of money spent. So, for each and ,
So are there prices and purchases satisfying these conditions ? Let’s consider the optimization
It is a concave optimization and so its solution can be found by the method of Lagrange. Its Lagrangian is
Here we have included slack variables . Certainly an optimal solution is feasible and, since complementary slackness holds: for and , we have the following optimality condition
The conditions on the derivative of our Lagrangian are
Notice if we set , the above conditions state that
So and also for each there is some such that , otherwise in our objective. So . Thus from this, we deduce that
We can now observe that the conditions on and , , are exactly the conditions on and , . So there exists an allocations of goods and prices satisfying our conditions ; moreover, the prices of the goods are given by the Lagrange multiplies of our optimization.