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

$\sum_{i=1}^n x_{ij} \leq s_j, \quad \text{and}\quad p_j>0 \quad\implies \quad \sum_{i=1}^n x_{ij} = s_j.$

Given the prices set by the sellers, the buyers will attempt to maximize the value of the goods they buy. So, each $i$ solves

$\maxi\quad \sum_{j=1}^m v_{ij}x_{ij} \quad\text{subject to}\quad \sum_{j=1}^m p_jx_{ij} \leq b_i \quad\text{over}\quad x_{ij} \geq 0, \quad \forall j=1,...,m.$ 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$ ,

$x_{ij}>0 \quad\implies\quad \frac{v_{ij}}{p_j} \in \argmax_{j'} \frac{v_{i j'}}{p_{j'}}.$

So are there prices $p=(p_j)_j$ and purchases $x=(x_{ij})_{i,j}$ satisfying these conditions ? Let’s consider the optimization

$\maxi\quad \sum_{i=1}^n b_i\log\bigg( \sum_{j=1}^m v_{ij}x_{ij} \bigg) \quad\text{subject to}\quad \sum_{i=1}^n x_{ij} \leq s_j, \quad \forall j=1,..,m \quad\text{over}\quad x_{ij}\geq 0\quad \forall i=1,...,n,\quad j=1,...m.$

It is a concave optimization and so its solution can be found by the method of Lagrange. Its Lagrangian is

$L(x,z;\mu)=\sum_{i=1}^n b_i\log\bigg( \sum_{j=1}^m v_{ij}x_{ij} \bigg) + \sum_{j=1}^m \mu_j\bigg( b_j-\sum_{i=1}^nx_{ij}-z_j \bigg).$

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

$\sum_{i=1}^n x_{ij} \leq s_j,\quad \text{and} \quad \mu_j>0 \implies \sum_{i=1}^n x_{ij} = s_j.$

The conditions on the derivative of our Lagrangian are

$\begin{aligned} \text{if}\quad x_{ij}>0 \quad \text{then}\quad 0=\frac{\partial L}{\partial x_{ij}}=\frac{b_iv_{ij}}{\sum_j v_{ij}x_{ij}}-\mu_j\quad\text{and}\quad \text{if}\quad x_{ij}=0 \quad \text{then}\quad 0\geq\frac{\partial L}{\partial x_{ij}}=\frac{b_iv_{ij}}{\sum_j v_{ij}x_{ij}}-\mu_j. \end{aligned}$ Notice if we set $M_i=\frac{\sum_j v_{ij}x_{ij}}{b_i}$ , the above conditions state that $x_{ij}>0 \implies \frac{v_{ij}}{\mu_j} = M_i,\quad \text{and}\quad x_{ij}=0 \implies \frac{v_{ij}}{\mu_j} \leq M_i.$

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

$x_{ij}>0 \quad\implies\quad \frac{v_{ij}}{\mu_j} \in \argmax_{j'} \frac{v_{i j'}}{\mu_{j'}}.$

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.