Institute for Logic, Language and Computation

18 December 2009, Computational Social Choice Seminar, Dries Vermeulen

Speaker: Dries Vermeulen
Title: On The Fastest Vickrey Algorithm
Date: Friday 18 December 2009
Time: 15:30
Location: Room A1.06 (<em>changed</em>), Science Park 904, Amsterdam


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 to worst-case analysis, and one related to first-order stochastic dominance. We show that Pareto best 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 that the bisection auction stochastically dominates all Vickrey algorithms. We extend our analysis to the study of weak Vickrey algorithms and winner determination algorithms. For the case of two bidders, we show that the One-Search algorithm stochastically dominates all column monotonic weak Vickrey algorithms and that the WD bisection algorithm stochastically dominates all winner determination algorithms. The WD bisection algorithm Pareto dominates all column monotonic winner determination algorithms in the n bidder case.

For more information, see or contact Ulle Endriss ().

The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X