From optimal limited to unlimited supply auctions

ABSTRACT

We investigate the class of single-round, sealed-bid auctions for a set of identical items to bidders who each desire one unit. We adopt the worst-case competitive framework defined by [9, 5] that compares the profit of an auction to that of an optimal single-price sale of least two items. In this paper, we first derive an optimal auction for three items, answering an open question from [8]. Second, we show that the form of this auction is independent of the competitive framework used. Third, we propose a schema for converting a given limited-supply auction into an unlimited supply auction. Applying this technique to our optimal auction for three items, we achieve an auction with a competitive ratio of 3.25, which improves upon the previously best-known competitive ratio of 3.39 from [7]. Finally, we generalize a result from [8] and extend our understanding of the nature of the optimal competitive auction by showing that the optimal competitive auction occasionally offers prices that are higher than all bid values.

References

1. A. Archer and E. Tardos. Truthful mechanisms for one-parameter agents. In Proc. of the 42nd IEEE Symposium on Foundations of Computer Science, 2001.
2. S. Baliga and R. Vohra. Market research and market design. Advances in Theoretical Economics, 3, 2003.
3. A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
4. J. Bulow and J. Roberts. The Simple Economics of Optimal Auctions. The Journal of Political Economy, 97:1060--90, 1989.
5. A. Fiat, A. V. Goldberg, J. D. Hartline, and A. R. Karlin. Competitive generalized auctions. In Proc. 34th ACM Symposium on the Theory of Computing, pages 72--81. ACM, 2002.
6. A. Goldberg, J. 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. A. V. Goldberg and J. D. Hartline. Competitiveness via consensus. In Proc. 14th Symposium on Discrete Algorithms, pages 215--222. ACM/SIAM, 2003.
8. A. V. Goldberg, J. D. Hartline, A. R. Karlin, and M. E. Saks. A lower bound on the competitive ratio of truthful auctions. In Proc. 21st Symposium on Theoretical Aspects of Computer Science, pages 644--655. Springer, 2004.
9. A. V. Goldberg, J. D. Hartline, and A. Wright. Competitive auctions and digital goods. In Proc. 12th Symposium on Discrete Algorithms, pages 735--744. ACM/SIAM, 2001.
10. D. Lehmann, L. I. O'Callaghan, and Y. Shoham. Truth Revelation in Approximately Efficient Combinatorial Auctions. In Proc. of 1st ACM Conf. on E-Commerce, pages 96--102. ACM Press, New York, 1999.
11. H. Moulin and S. Shenker. Strategyproof Sharing of Submodular Costs: Budget Balance Versus Efficiency. Economic Theory, 18:511--533, 2001.
12. R. Myerson. Optimal Auction Design. Mathematics of Operations Research, 6:58--73, 1981.
13. N. Nisan and A. Ronen. Algorithmic Mechanism Design. In Proc. of 31st Symp. on Theory of Computing, pages 129--140. ACM Press, New York, 1999.
14. I. Segal. Optimal pricing mechanisms with unknown demand. American Economic Review, 16:509-29, 2003.
15. W. Vickrey. Counterspeculation, Auctions, and Competitive Sealed Tenders. J. of Finance, 16:8--37, 1961.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Economics

• Theory of computation

  • Design and analysis of algorithms