Knapsack auctions

ABSTRACT

We consider a game theoretic knapsack problem that has application to auctions for selling advertisements on Internet search engines. Consider n agents each wishing to place an object in the knapsack. Each agent has a private valuation for having their object in the knapsack and each object has a publicly known size. For this setting, we consider the design of auctions in which agents have an incentive to truthfully reveal their private valuations. Following the framework of Goldberg et al. [10], we look to design an auction that obtains a constant fraction of the profit obtainable by a natural optimal pricing algorithm that knows the agents' valuations and object sizes.We give an auction that obtains a constant factor approximation in the non-trivial special case where the knapsack has unlimited capacity. We then reduce the limited capacity version of the problem to the unlimited capacity version via an approximately efficient auction (i.e., one that maximizes the social welfare). This reduction follows from generalizable principles.

REFERENCES

• 1: Zoë Abrams, Revenue maximization when bidders have budgets, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1074-1082, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109676]
• 2: Maria-Florina Balcan , Avrim Blum, Mechanism Design via Machine Learning, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.605-614, October 23-25, 2005 [doi>10.1109/SFCS.2005.50]
• 3: Avrim Blum , Jason D. Hartline, Near-optimal online auctions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 4: Christian Borgs , Jennifer Chayes , Nicole Immorlica , Mohammad Mahdian , Amin Saberi, Multi-unit auctions with budget-constrained bidders, Proceedings of the 6th ACM conference on Electronic commerce, p.44-51, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064014]
• 5: E. H. Clarke. Multipart Pricing of Public Goods. Public Choice, 11:17--33, 1971.
• 6: 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]
• 7: Andrew V. Goldberg , Jason D. Hartline, Envy-free auctions for digital goods, Proceedings of the 4th ACM conference on Electronic commerce, p.29-35, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779932]
• 8: Andrew V. Goldberg , Jason D. Hartline, Collusion-resistant mechanisms for single-parameter agents, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: A. Goldberg, J. Hartline, A. Karlin, M. Saks, and A. Wright. Competitive auctions. Games and Economic Behavior. Submitted for publication. An earlier version available as InterTrust Technical Report STAR-TR-99-01.
• 10: Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
• 11: T. Groves. Incentives in Teams. Econometrica, 41:617--631, 1973.
• 12: Venkatesan Guruswami , Jason D. Hartline , Anna R. Karlin , David Kempe , Claire Kenyon , Frank McSherry, On profit-maximizing envy-free pricing, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and Generalized On-line Matching, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.264-273, October 23-25, 2005 [doi>10.1109/SFCS.2005.12]
• 14: Ahuva Mu'alem , Noam Nisan, Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract, Eighteenth national conference on Artificial intelligence, p.379-384, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 15: R. Myerson. Optimal auction design. Mathematics of Operations Research, 6:58--73, 1981.
• 16: W. Vickrey. Counterspeculation, Auctions, and Competitive Sealed Tenders. J. of Finance, 16:8--37, 1961.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory