Linear Programming and Vickrey Auctions

Professor Rakesh Vohra

John L. and Helen Kellogg Professor of Managerial

Ecomonics and Decision Science

Kellogg School of Management

Northwestern University

The Vickrey sealed bid auction occupies a central place in auction theory because of its efficiency and incentive properties. Implementing the auction requires the auctioneer to solve $n+1$ optimization problems, where $n$ is the number of bidders.

In this talk we survey various environments (some old and some new) where the payments bidders make under the Vickrey auction correspond to dual variables in certain linear programs.

Thus, in these environments, at most two optimization problems must be solved to determine the Vickrey outcome. Furthermore, primal-dual algorithms for some of these linear programs give rise to ascending auctions that implement the Vickrey outcome.

Based on joint work with:Sushil Bikhchandani, Sven de Vries, James Schummer