Tuomas W. Sandholm, University of Massachusetts, USA
Auctions provide an efficient distributed mechanism for solving problems such as task and resource allocation in multiagent systems. In the Vickrey auction--which has been widely advocated for automated auctions--the best bid wins the auction, but at the second best price. In certain settings this promotes truthful bidding and avoids counterspeculation. This paper analyses the circumstances when this protocol is appropriate, and explicates the desirable properties and lack thereof in varied settings. The first part of the paper discusses known deficiencies of the Vickrey auction: bidder collusion, a lying auctioneer, promotion of lying in non-private-value auctions, lower revenue than alternative protocols, and the necessity to reveal sensitive information. The second part of the paper presents our results regarding new limitations of the protocol, which arise especially among computational agents. These include inefficient allocation and lying in sequential auctions of interrelated items, untruthful bidding when a risk averse agent has local uncertainty, and the need for counterspeculation to make deliberation control (or information gathering) decisions when an agent has local uncertainty.