Department of Management Science
Seminar
At 3 pm on Friday 21st March 2003
in Lecture Theatre C103 Graduate School, Lancaster University
Equilibrium Prices in Markets Modeled with Mixed Integer Programs
Professor Michael H. Rothkopf
Rutgers University
Abstract
Dual variables give useful prices in markets models with LPs. However, many
markets have important economies of scale such as fixed or start up costs.
These markets can be modeled using mixed integer programs (MIPs). Ever since
Gomory and Baumol examined the dual of cutting planes in MIPs in 1960, we have
"known" that there are no economically satisfactory prices for markets modeled
with MIPs. In 1994, Scarf explained and lamented the problem in the widely
circulated Journal of Economic Perspectives.
We have found a simple way to get prices that support an economic equilibrium.
The key is pricing the discrete variables as well as the continuous ones. We
do this in two stages. First we solve the MIP. Then, we add linear
constraints that force the optimal solution and drop the integrality
constraints. We show that the dual variables on the added constraints in the
resulting LP effectively price the integer variables and that the dual prices
support an economic equilibrium. In particular, we exhibit
equilibrium-supporting prices for the example problem used to explain the
problem to economists. In addition to their theoretical importance, our
results have immediate practical relevance to electricity auctions where
generators have start up costs and minimum run level constraints.
This is joint work with Richard P. O'Neill, Paul M. Sotkiewicz, Benjamin F.
Hobbs, and William R. Stewart, Jr.
Copies of the paper can be found on
http://www.lums.lancs.ac.uk/news/Departments/ManSci/120
|