Efficient auctions for multiple, indivisible objects are described in terms of the duality theory of linear programming. Because of its well-known incentive properties, the focus is on Vickrey-Clark-Grove auctions. Pricing equilibria, which are optimal solutions to the primal and dual of a linear programming (LP) formulation of the underlying exchange economy, play a key role in the characterization. The exposition is divided into “static” or sealed-bid auctions and “dynamic” or ascending-price auctions. A pricing equilibrium yields the outcome of a Vickrey-Clark-Grove sealed-bid auction if and only if buyers are substitutes.
Algorithms for solving LP problems imply that the static characterization has a dynamic counterpart. Among the methods for solving LP problems, the primal dual algorithm is noteworthy because its informational requirements can be decentralized. The implementor acts as an auctioneer who calls out prices (feasible solutions to the dual) that require little information about buyers’ preferences. By starting the algorithm at zero prices, the primal dual method can be interpreted as an incentive compatible ascending-price auction.
Copyright. All Rights Reserved.