| ABSTRACT Envy-Free Auctions for Digital Goods (2008) | |||||||||||||||
Abstract | |||||||||||||||
| We study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: • Competitive: the auction achieves a constant fraction of the optimal revenue even on worst case inputs. • Truthful: any bidder’s best strategy is to bid the maximum value they are willing to pay. • Envy-free: after the auction is run, no bidder would be happier with the outcome of another bidder (for unlimited supply auctions, this means that there is a single sale price and goods are allocated to all bidders willing to pay this price). Our main result is to show that no constant-competitive truthful auction is envy-free. We consider two relaxations of these requirements, allowing the auction to be untruthful with vanishingly small probability, and allowing the auction to give non-envy-free outcomes with vanishingly small probability. Under both of these relaxations we get competitive auctions. 1. | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||