EUVIMEDEUVIMED entdecken
Crossref

A Simple and Approximately Optimal Mechanism for an Additive Buyer

Moshe Babaioff, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg

Journal of the ACM · 31.08.2020 · 67 (4) · 1-40

DOI: 10.1145/3398745 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 16.06.2020. Verfasst von Moshe Babaioff und 3 weiteren Autor:innen. Die Arbeit wurde bisher 45-mal zitiert (Crossref) und nennt 61 Literaturangaben. Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and her value for a set of items is additive. The seller aims to maximize his revenue. We suggest using the a priori better of two simple pricing methods: selling the items separately , each at its optimal price, and bundling together , in which the entire set of items is sold as one bundle at its optimal price. We show that for any distribution, this mechanism achieves a constant-factor approximation to the optimal revenue. Beyond its simplicity, this is the first computationally tractable mechanism to obtain a constant-factor approximation for this multi-parameter problem. We additionally discuss extensions to multiple buyers and to valuations that are correlated across items.

Förderung

  • National Science Foundation

Zitieren

APA

Babaioff, M., Immorlica, N., Lucier, B., & Weinberg, S. M. (2020). A Simple and Approximately Optimal Mechanism for an Additive Buyer. Journal of the ACM, 67(4), 1-40. https://doi.org/10.1145/3398745

Vancouver

Babaioff M, Immorlica N, Lucier B, Weinberg SM. A Simple and Approximately Optimal Mechanism for an Additive Buyer. Journal of the ACM. 2020;67(4):1-40. doi:10.1145/3398745

BibTeX
@article{Babaioff2020,
  author = {Babaioff, Moshe and Immorlica, Nicole and Lucier, Brendan and Weinberg, S. Matthew},
  title = {A Simple and Approximately Optimal Mechanism for an Additive Buyer},
  journal = {Journal of the ACM},
  year = {2020},
  volume = {67},
  number = {4},
  pages = {1--40},
  doi = {10.1145/3398745}
}
Kostenlos starten →