nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

A Prior-Independent Revenue-Maximizing Auction for Multiple Additive Bidders

verfasst von : Kira Goldner, Anna R. Karlin

Erschienen in: Web and Internet Economics

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Recent work by Babaioff et al. [1], Yao [30], and Cai et al. [7] shows how to construct an approximately optimal auction for additive bidders, given access to the priors from which the bidders’ values are drawn. In this paper, building on the single sample approach of Dhangwatnotai et al. [15], we show how the auctioneer can obtain approximately optimal expected revenue in this setting without knowing the priors, as long as the item distributions are regular.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Pricing to Maximize Revenue and Welfare Simultaneously in Large Markets

Nächstes Kapitel Optimal Mechanism for Selling Two Items to a Single Buyer Having Uniformly Distributed Valuations

Thus, from the seller’s perspective this value is a random variable \(V_{ij}\).

i.e., revenue-maximizing, in expectation.

This is a reinterpretation of the Bulow-Klemperer Theorem [2].

This guarantees that each item is taken by at most one bidder.

Babaioff, M., Immorlica, N., Lucier, B., Weinberg, S.M.: A simple and approximately optimal mechanism for an additive buyer. In: Proceedings of the 55th Annual Symposium on Foundations of Computer Science, FOCS 2014 (2014). http://arxiv.org/abs/1405.6146

Bulow, J., Klemperer, P.: Auctions vs. negotiations. Technical report, National Bureau of Economic Research (1994)

Cai, Y., Daskalakis, C., Weinberg, S.M.: An algorithmic characterization of multi-dimensional mechanisms. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 459–478. ACM (2012)

Cai, Y., Daskalakis, C., Weinberg, S.M.: Optimal multi-dimensional mechanism design: reducing revenue to welfare maximization. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 130–139. IEEE (2012)

Cai, Y., Daskalakis, C., Weinberg, S.M.: Reducing revenue to welfare maximization: approximation algorithms and other generalizations. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 578–595. SIAM (2013)

Cai, Y., Daskalakis, C., Weinberg, S.M.: Understanding incentives: mechanism design becomes algorithm design. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 618–627. IEEE (2013)

Cai, Y., Devanur, N.R., Weinberg, S.M.: A duality based unified approach to Bayesian mechanism design. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing. ACM (2016)

Chawla, S., Miller, J.B.: Mechanism design for subadditive agents via an ex ante relaxation. In: Proceedings of the 2016 ACM Conference on Economics and Computation, EC 2016, pp. 579–596. ACM, New York (2016). http://doi.acm.org/10.1145/2940716.2940756

Cole, R., Roughgarden, T.: The sample complexity of revenue maximization. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 243–252. ACM (2014)

10.

Daskalakis, C.: Multi-item auctions defying intuition? ACM SIGecom Exch. 14(1), 41–75 (2015)CrossRef

11.

Daskalakis, C., Deckelbaum, A., Tzamos, C.: Mechanism design via optimal transport. In: Proceedings of the 14th ACM Conference on Electronic Commerce, EC 2013, pp. 269–286 (2013). http://doi.acm.org/10.1145/2482540.2482593

12.

Daskalakis, C., Deckelbaum, A., Tzamos, C.: Strong duality for a multiple-good monopolist. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation, pp. 449–450. ACM (2015)

13.

Devanur, N., Hartline, J., Karlin, A., Nguyen, T.: Prior-independent multi-parameter mechanism design. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) WINE 2011. LNCS, vol. 7090, pp. 122–133. Springer, Heidelberg (2011). doi:10.1007/978-3-642-25510-6_11. http://users.eecs.northwestern.edu/~hartline/papers/auctions-WINE-11.pdf

14.

Devanur, N.R., Huang, Z., Psomas, C.A.: The sample complexity of auctions with side information. arXiv preprint arXiv:1511.02296 (2015)

15.

Dhangwatnotai, P., Roughgarden, T., Yan, Q.: Revenue maximization with a single sample. In: Proceedings of the 11th ACM Conference on Electronic Commerce, EC 2010, pp. 129–138. ACM, New York (2010). http://doi.acm.org/10.1145/1807342.1807364

16.

Fiat, A., Goldner, K., Karlin, A.R., Koutsoupias, E.: The FedEx problem. In: Proceedings of the 2016 ACM Conference on Economics and Computation, EC 2016, pp. 21–22. ACM, New York (2016). http://doi.acm.org/10.1145/2940716.2940752

17.

Fu, H., Hartline, J., Hoy, D.: Prior-independent auctions for risk-averse agents. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pp. 471–488. ACM (2013)

18.

Giannakopoulos, Y., Koutsoupias, E.: Duality and optimality of auctions for uniform distributions. In: Proceedings of the 15th ACM Conference on Economics and Computation, EC 2014, pp. 259–276 (2014). http://doi.acm.org/10.1145/2600057.2602883

19.

Giannakopoulos, Y., Koutsoupias, E.: Selling two goods optimally. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 650–662. Springer, Heidelberg (2015). doi:10.1007/978-3-662-47666-6_52

20.

Hart, S., Nisan, N.: Approximate revenue maximization with multiple items. arXiv preprint arXiv:1204.1846 (2012)

21.

Huang, Z., Mansour, Y., Roughgarden, T.: Making the most of your samples. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation, pp. 45–60. ACM (2015)

22.

Li, X., Yao, A.C.C.: On revenue maximization for selling multiple independently distributed items. Proc. Natl. Acad. Sci. 110(28), 11232–11237 (2013). http://dx.doi.org/10.1073/pnas.1309533110 MathSciNetCrossRefMATH

23.

Morgenstern, J., Roughgarden, T.: Learning simple auctions. CoRR abs/1604.03171 (2016). http://arxiv.org/abs/1604.03171

24.

Morgenstern, J.H., Roughgarden, T.: On the pseudo-dimension of nearly optimal auctions. In: Advances in Neural Information Processing Systems, pp. 136–144 (2015)

25.

Roughgarden, T., Talgam-Cohen, I.: Optimal and near-optimal mechanism design with interdependent values. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, EC 2013, pp. 767–784. ACM, New York (2013). http://doi.acm.org/10.1145/2482540.2482606

26.

Roughgarden, T., Talgam-Cohen, I., Yan, Q.: Supply-limiting mechanisms. In: Proceedings of the 13th ACM Conference on Electronic Commerce, pp. 844–861. ACM (2012). http://theory.stanford.edu/~tim/papers/limit_conf.pdf

27.

Rubinstein, A.: On the computational complexity of optimal simple mechanisms. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS 2016, pp. 21–28. ACM, New York (2016). http://doi.acm.org/10.1145/2840728.2840736

28.

Rubinstein, A., Weinberg, S.M.: Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation, pp. 377–394. ACM (2015). http://arxiv.org/abs/1501.07637

29.

Weinberg, S.M.: Algorithms for strategic agents. Ph.D. thesis, Massachusetts Institute of Technology (2014). http://people.csail.mit.edu/smweinberg/thesis.pdf

30.

Yao, A.C.C.: An \(n\)-to-1 bidder reduction for multi-item auctions and its applications. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 92–109 (2015). http://arxiv.org/abs/1406.3278

Titel: A Prior-Independent Revenue-Maximizing Auction for Multiple Additive Bidders
verfasst von: Kira Goldner
Anna R. Karlin
Verlag: Springer Berlin Heidelberg
Buch: Web and Internet Economics
Print ISBN: 978-3-662-54109-8

Electronic ISBN: 978-3-662-54110-4

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-54110-4_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"