On the Fastest Vickrey Algorithm |
| |
Authors: | Elena Grigorieva P Jean-Jacques Herings Rudolf Müller Dries Vermeulen |
| |
Affiliation: | 1. Department of Quantitative Economics, Maastricht University, P.O. Box 616, 6200, MD, Maastricht, The Netherlands 2. Department of Economics, Maastricht University, P.O. Box 616, 6200, MD, Maastricht, The Netherlands
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|