Template-type: ReDif-Paper 1.0
Author-Name: Grigorieva Elena 
Author-Name: Herings P. Jean-Jacques 
Author-Name: Müller Rudolf 
Author-Name: Vermeulen Dries 
Author-workplace-name: METEOR
Title: On The Fastest Vickrey Algorithm
Abstract: We investigate the algorithmic performance of Vickrey-Clarke-Groves mechanisms in the single item case. We provide a formal definition of a Vickrey algorithm for this framework, and give a number of examples of Vickrey algorithms. We consider three performance criteria, one corresponding to a Pareto criterion, one corresponding to worst case analysis, and a third criterion related to first-order stochastic dominance. We show that Pareto optimal Vickrey algorithms do not exist and that worst case analysis is of no use in discriminating between Vickrey algorithms. For the case of two bidders, we show the bisection auction to be optimal according to the third criterion. The bisection auction istherefore optimal in a very strong sense. 
Keywords: operations research and management science; 
Series: Research Memoranda
Creation-Date: 2007
Number: 013
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:f19f70ea-ef35-471e-bff4-38efb2c1e369/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 229024
Handle: RePEc:unm:umamet:2007013