Can I read The Vickrey Auction with a Single Duplicate Bidder Approximates the Optimal Revenue on EtoBox?

The Vickrey Auction with a Single Duplicate Bidder Approximates the Optimal Revenue by Fu, Hu; Liaw, Christopher; Randhawa, Sikander is a scholarly article available to read on EtoBox.

What is The Vickrey Auction with a Single Duplicate Bidder Approximates the Optimal Revenue about?

Bulow and Klemperer's well-known result states that, in a single-item auction where the $n$ bidders' values are independently and identically drawn from a regular distribution, the Vickrey auction with one additional bidder (a duplicate) extracts at least as much revenue as the optimal auction without the duplicate. Hartline and Roughgarden, in their influential 2009 paper, removed the requirement that the distributions be identical, at the cost of allowing the Vickrey auction to recruit $n$ duplicates, one from each distribution, and relaxing its revenue advantage to a $2$-approximation. In this work we restore Bulow and Klemperer's number of duplicates in Hartline and Roughgarden's more general setting with a worse approximation ratio. We show that recruiting a duplicate from one of the distributions suffices for the Vickrey auction to $10$-approximate the optimal revenue. We also show that in a $k$-items unit demand auction, recruiting $k$ duplicates suffices for the VCG auction to $O(1)$-approximate the optimal revenue. As another result, we tighten the analysis for Hartline and Roughgarden's Vickrey auction with $n$ duplicates for the case with two bidders in the auction. We s

Author

Fu, Hu; Liaw, Christopher; Randhawa, Sikander

Published

2019

Language

EN