Envy-free auctions for digital goods

ABSTRACT

We study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: item Competitive: the auction achieves a constant fraction of the optimal revenue even on worst case inputs. item Truthful: any bidder's best strategy is to bid the maximum value they are willing to pay. item 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.

REFERENCES

• 1: Aaron Archer , Christos Papadimitriou , Kunal Talwar , Éva Tardos, An approximate truthful mechanism for combinatorial auctions with single parameter agents, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 2: J. Bulow and J. Roberts. The Simple Economics of Optimal Auctions. The Journal of Political Economy, 97:1060--90, 1989.
• 3: Kaustubh Deshmukh , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Truthful and Competitive Double Auctions, Proceedings of the 10th Annual European Symposium on Algorithms, p.361-373, September 17-21, 2002
• 4: Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509921]
• 5: Andrew V. Goldberg , Jason D. Hartline, Competitiveness via consensus, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 6: A. V. Goldberg, J. D. Hartline, A. Karlin, M. Saks, and A. Wright. Competitive auctions and digital goods. Games and Economic Behavior, 2002. Submitted for publication. An earlier version available as InterTrust Technical Report at URL http://www.star-lab.com/tr/tr-99-01.html.
• 7: H. Moulin and S. Shenker. Strategyproof Sharing of Submodular Costs. Economic Theory, to appear.
• 8: R. Myerson. Optimal Auction Design. Mathematics of Operations Research, 6:58--73, 1981.
• 9: R. Radner. Collusive Behavior in Noncooperative Epsilon-Equilibria of Oligopolies with Long but Finite Lives. J. Economic Theory, 22:136--154, 1980.
• 10: J. Schummer. Almost dominant strategy implementation. Technical report, MEDS, Kellogg Graduate School of Management, 2001. Available from http://www.kellogg.nwu.edu/faculty/schummer/ftp/research/esp.ps.
• 11: W. Vickrey. Counterspeculation, Auctions, and Competitive Sealed Tenders. J. of Finance, 16:8--37, 1961.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Economics, Theory

Keywords:
auctions, competitive analysis