关于最快的 Vickrey 算法-研究论文

我们研究了 Vickrey-Clarke-Groves 机制在单项情况下的算法性能。 我们为这个框架提供了一个 Vickrey 算法的正式定义，并给出了一些 Vickrey 算法的例子。 我们考虑三个性能标准，一个对应于帕累托标准，一个对应于最坏情况分析，第三个标准与一阶随机优势相关。 我们表明帕累托最优 Vickrey 算法不存在，并且最坏情况分析在区分 Vickrey 算法时没有用处。 对于两个投标人的情况，我们表明根据第三个标准，平分拍卖是最优的。 因此，二等分拍卖在非常强烈的意义上是最优的。