×

Prior-free multi-unit auctions with ordered bidders. (English) Zbl 1468.91058

Summary: Prior-free auctions are robust auctions that assume no distribution over bidders’ valuations and provide worst-case (input-by-input) approximation guarantees. In contrast to previous work on this topic, we pursue good prior-free auctions with non-identical bidders.
Prior-free auctions can approximate meaningful benchmarks for non-identical bidders only when sufficient qualitative information about the bidder asymmetry is publicly known. We consider digital goods auctions where there is a total ordering of the bidders that is known to the seller, where earlier bidders are in some sense thought to have higher valuations. We use the framework of J. D. Hartline and T. Roughgarden [in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. Victoria, Canada, May 17–20, 2008. New York, NY: Association for Computing Machinery (ACM). 75–84 (2008; Zbl 1231.91117)] to define an appropriate revenue benchmark: the maximum revenue that can be obtained from a bid vector using prices that are nonincreasing in the bidder ordering and bounded above by the second-highest bid. This monotone-price benchmark is always as large as the well-known fixed-price benchmark \(\mathcal{F}^{( 2 )} \), so designing prior-free auctions with good approximation guarantees is only harder. By design, an auction that approximates the monotone-price benchmark satisfies a very strong guarantee: it is, in particular, simultaneously near-optimal for essentially every Bayesian environment in which bidders’ valuation distributions have nonincreasing monopoly prices, or in which the distribution of each bidder stochastically dominates that of the next. Even when there is no distribution over bidders’ valuations, such an auction still provides a quantifiable input-by-input performance guarantee.
In this paper, we design a simple \(O(1)\)-competitive prior-free auction for digital goods with ordered bidders. We also extend the monotone-price benchmark and our \(O(1)\)-competitive prior-free auction to multi-unit settings with limited supply.

MSC:

91B26 Auctions, bargaining, bidding and selling, and other market models
91B03 Mechanism design theory

Citations:

Zbl 1231.91117
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aggarwal, G.; Hartline, J. D., Knapsack auctions, (Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2006)), 1083-1092 · Zbl 1192.91096
[2] Alaei, S.; Malekian, A.; Srinivasan, A., On random sampling auctions for digital goods, (Proceedings of the 10th ACM Conference on Electronic Commerce (EC) (2009)), 187-196
[3] Balcan, M.-F.; Blum, A.; Hartline, J.; Mansour, Y., Mechanism design via machine learning, J. Comput. Syst. Sci., 74, 8, 1245-1270 (2008) · Zbl 1157.68055
[4] Blum, A.; Hartline, J. D., Near-optimal online auctions, (Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2005)), 1156-1163 · Zbl 1297.91075
[5] Bulow, J.; Klemperer, P., Auctions versus negotiations, Am. Econ. Rev., 86, 1, 180-194 (1996)
[6] Chen, J.; Micali, S., Mechanism design with set-theoretic beliefs, (Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science. Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS (2011)), 87-96 · Zbl 1292.91080
[7] Devanur, N.; Hartline, J. D., Limited and online supply and the Bayesian foundations of prior-free mechanism design, (Proceedings of the 10th ACM Conference on Electronic Commerce. Proceedings of the 10th ACM Conference on Electronic Commerce, EC (2009)), 41-50
[8] Devanur, Nikhil R.; Ha, Bach Q.; Hartline, Jason D., Prior-free auctions for budgeted agents, (Proceedings of the 14th ACM Conference on Electronic Commerce. Proceedings of the 14th ACM Conference on Electronic Commerce, EC (2013)), 287-304
[9] Dhangwatnotai, Peerapong; Roughgarden, Tim; Yan, Qiqi, Revenue maximization with a single sample, (Proceedings of the 11th ACM Conference on Electronic Commerce. Proceedings of the 11th ACM Conference on Electronic Commerce, EC (2010)), 129-138 · Zbl 1318.91088
[10] Goldberg, A.; Hartline, J., Envy-free auctions for digital goods, (Proceedings of the 4th ACM Conference on Electronic Commerce. Proceedings of the 4th ACM Conference on Electronic Commerce, EC (2003)), 29-35
[11] Goldberg, A. V.; Hartline, J. D.; Karlin, A.; Saks, M.; Wright, A., Competitive auctions, Games Econ. Behav., 55, 2, 242-269 (2006) · Zbl 1125.91041
[12] Goldberg, A. V.; Hartline, J. D.; Wright, A., Competitive auctions and digital goods (1999), Technical Report STAR-TR-99.09.01, STAR Laboratory, InterTrust Tech. Corp., Santa Clara, CA · Zbl 0988.91024
[13] Ha, Bach Q.; Hartline, Jason D., Mechanism design via consensus estimates, cross checking, and profit extraction, (Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2012)), 887-895 · Zbl 1425.91194
[14] Hartline, J. D., Approximation in Economic Design (2012), book in preparation
[15] Hartline, J. D.; Karlin, A., Profit maximization in mechanism design, (Nisan, N.; Rougarden, T.; Tardos, É.; Vazirani, V. V., Algorithmic Game Theory (2007), Cambridge University Press), 331-362, chapter 13 · Zbl 1151.91418
[16] Hartline, J. D.; Roughgarden, T., Optimal mechanism design and money burning, (Proceedings of the 40th Annual ACM Symposium on Theory of Computing. Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC (2008)), 75-84, Full version last revised August, 2012 · Zbl 1231.91117
[17] Hartline, J. D.; Roughgarden, T., Simple versus optimal mechanisms, (Proceedings of the 10th ACM Conference on Electronic Commerce. Proceedings of the 10th ACM Conference on Electronic Commerce, EC (2009)), 225-234
[18] Hartline, J. D.; Yan, Q., Envy, truth, and optimality, (Proceedings of the 12th ACM Conference on Electronic Commerce. Proceedings of the 12th ACM Conference on Electronic Commerce, EC (2011)), 243-252
[19] Ichiba, T.; Iwama, K., Averaging techniques for competitive auctions, (Proceedings of the Workshop on Analytic Algorithmics and Combinatorics. Proceedings of the Workshop on Analytic Algorithmics and Combinatorics, ANALCO (2010)), 74-81 · Zbl 1431.91167
[20] Lopomo, G.; Rigotti, L.; Shannon, C., Uncertainty in mechanism design (2009), submitted for publication
[21] Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge University Press · Zbl 0849.68039
[22] Myerson, R., Optimal auction design, Math. Oper. Res., 6, 1, 58-73 (1981) · Zbl 0496.90099
[23] Nisan, N., Introduction to mechanism design (for computer scientists), (Nisan, N.; Rougarden, T.; Tardos, É.; Vazirani, V., Algorithmic Game Theory (2007), Cambridge University Press), 209-241, chapter 9 · Zbl 1143.91323
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.