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


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.


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