Multi-Item Vickrey-Dutch Auction for Unit-Demand Preferences

Abstract

We consider an economy with one seller and m selfish buyers. The seller has n indivisible heterogeneous items to sell and each buyer wants at most one of those items. Buyers have private, independent and known value on the items. We propose an exact Vickrey-Dutch auction, where prices of appropriate items are decreased by unity in each iteration. This auction converges to Vickrey payoff point exactly if valuations are integer. We then introduce an approximate Vickrey-Dutch auction in which prices of appropriate items are decreased by a positive bid decrement ǫ. This auction converges to the Vickrey payoff point approximately. The terminating conditions of both the auctions are related to a concept called Universal Competitive Equilibrium and we show its relationship to Vickrey payoff point in our model. Using simulation, we show that such Vickrey-Dutch auctions have significant advantage in communication complexity over other existing auctions.