Research output

On the fastest Vickrey Algorithm

Research output: Contribution to journalArticleAcademicpeer-review

Associated researcher

Associated organisations

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 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 a suitably adjusted version of the bisection algorithm, 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.

    Research areas

  • Single item auctions, Vickrey-Clarke-Groves implementation, Algorithms, Performance analysis, EGALITARIANISM, CONSTRAINTS, COMPLEXITY, GAMES
View graph of relations

Details

Original languageEnglish
Pages (from-to)566-590
Number of pages25
JournalAlgorithmica
Volume58
Issue number3
DOIs
Publication statusPublished - Nov 2010