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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s