Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Envy-Free Auctions for Digital Goods

Andrew V. Goldberg and Jason D. Hartline

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.

Details

Publication typeInproceedings
Published inACM Conference on Electronic Commerce (EC '03)
URLhttp://www.acm.org/
AddressSan Diego, CA
PublisherAssociation for Computing Machinery, Inc.
> Publications > Envy-Free Auctions for Digital Goods