Envy-free auctions for digital goods

Andrew V. Goldberg*, Jason D. Hartline

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

55 Scopus citations


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 digital good 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 auction that is truthful and always gives outcomes are 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.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM Conference on Electronic Commerce
Number of pages7
StatePublished - Nov 19 2003
EventProceedings of the 4th ACM Conference on Electronic Commerce - San Diego, CA, United States
Duration: Jun 9 2003Jun 12 2003


OtherProceedings of the 4th ACM Conference on Electronic Commerce
Country/TerritoryUnited States
CitySan Diego, CA


  • Auctions
  • Competitive analysis

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'Envy-free auctions for digital goods'. Together they form a unique fingerprint.

Cite this