The AUCTEQ.ltx Model

Auctioning Classes to Students - Equilibrium problem

The concept of a broker who maximizes producer-consumer surplus can be applied to auctions. Linear Programming is useful if the auction is complicated by features that might be interpreted as bidders with demand curves. This example is based on a design by R.L. Graves for a course registration system used since 1981 at the University of Chicago, in which students bid on courses.

Suppose there are N types of objects to be solve (e.g., courses), and there are M bidders (students). Bidder i is willing to pay up to b_ij, b_ij >= 0 for one unit of object type j. Further a bidder is interested in at most one unit of each object type. Let S_j be the number of units of object type j available for sale.

There are a variety of ways of holding the auction. Let us suppose that it is a sealed-bid auction and we want to find a single, market-clearing price, p_j, for each object type j, such that:

at most, S_j units of object j are sold;
any bid for j less than p_j does not buy a unit;
p_j = 0 if less than S_j units of j are sold;
any bid for j greater than p_j does buy a unit.

It is easy to determine the equilibrium p_js by simply sorting the bids and allocating each unit to the higher bidder first. Nevertheless, in order to prepare for more complicated auctions, let us consider how to solve this problem as an optimization problem. Again, we take the view of a broker who sells at as high (buys at as low) a price as possible and maximizes profits.

In this example, we want to find a "market clearing" price for each object and an allocation of units to bidders so that each bidder is willing to accept the units awarded to him at the market clearing price. A bidder is satisfied with a particular unit if he cannot find another unit with a bigger difference between his maximum offer price and the market clearing price. This is equivalent to saying that each bidder maximizes his consumer surplus.

Keywords: