Binary Vickrey auction — A robust and efficient multi-unit sealed-bid online auction protocol against buyer multi-identity bidding

摘要

The multi-unit Vickrey–Clark–Groves (VCG) mechanism has two major weaknesses: it has high computational complexity and monotonicity problems [Paul Milgrom. Putting Auction Theory to Work. Cambridge University Press, Cambridge, UK, 2004] such that if goods are not substitutes for all bidders and if a bidder can submit bids under multiple identities, then the VCG is no longer strategy-proof. To address these two weaknesses, we introduce a Binary Vickrey Auction (BVA) where goods are allocated in bundles of sequentially-decreasing power-of-two items in multiple rounds. Because of the discrete allocation operations, the BVA is computationally efficient. It is also robust against buyer multi-identity bidding by discouraging a bidder splitting his single bid for a larger bundle into several bids under multiple bidder identities for smaller bundles because the BVA favors bids for larger bundles with earlier considerations and cheaper prices.