# Gale-Eisenberg Market

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 $i=1,...,n$ each with a budget $b_i\in{\mathbb R}_+$, and there are sellers indexed by $j=1,...,m$ each selling $s_j$ units of single good. We suppose each seller sells a different good. Suppose that buyer $i$ values good $j$ by $v_{ij}\in{\mathbb R}_+$.

The seller $j$ sets a price $p_j\in{\mathbb R}_+$ for his good and buyer $i$ decides how much of that good she wishes to buy $x_{ij}\in{\mathbb R}_+$. Let’s consider some reasonable conditions for $p=(p_j:j=1,..,m)$ and $x=(x_{ij}:i=1,...,n,j=1,...,m)$ 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 $j$, 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 $i$ 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 $i$ and $j$,

So are there prices $p=(p_j)_j$ and purchases $x=(x_{ij})_{i,j}$ 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 $z=(z_j:j=1,,...m)$. Certainly an optimal solution is feasible and, since complementary slackness holds: $\mu_j z_j=0$ for $z_j=b_j-\sum_i x_{ij}$ and $\mu_j\geq 0$, we have the following optimality condition

The conditions on the derivative of our Lagrangian are

Notice if we set $M_i=\frac{\sum_j v_{ij}x_{ij}}{b_i}$, the above conditions state that

So $M_i\geq \max_j v_{ij}/\mu_j$ and also for each $i$ there is some $j$ such that $x_{ij}>0$, otherwise $b_i\log(0)=-\infty$ in our objective. So $M_i=\max_j v_{ij}/\mu_j$. Thus from this, we deduce that

We can now observe that the conditions on $x$ and $\mu$, , are exactly the conditions on $x$ and $p$, . 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.