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

51 Scopus citations

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 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
Pages29-35
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

Other

OtherProceedings of the 4th ACM Conference on Electronic Commerce
Country/TerritoryUnited States
CitySan Diego, CA
Period6/9/036/12/03

Keywords

  • Auctions
  • Competitive analysis

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint

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

Cite this