EUVIMEDEUVIMED entdecken
Crossref

Optimal Auctions with Positive Network Externalities

Nima Haghpanah, Nicole Immorlica, Vahab Mirrokni, Kamesh Munagala

ACM Transactions on Economics and Computation · 2013

DOI: 10.1145/2465769.2465778 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, 2013. Verfasst von Nima Haghpanah und 3 weiteren Autor:innen. Die Arbeit wurde bisher 20-mal zitiert (Crossref) und nennt 30 Literaturangaben. Gefördert von: Alfred P. Sloan Foundation, Microsoft Research, Division of Computing and Communication Foundations.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the problem of designing auctions in social networks for goods that exhibit single-parameter submodular network externalities in which a bidder’s value for an outcome is a fixed private type times a known submodular function of the allocation of his friends. Externalities pose many issues that are hard to address with traditional techniques; our work shows how to resolve these issues in a specific setting of particular interest. We operate in a Bayesian environment and so assume private values are drawn according to known distributions. We prove that the optimal auction is NP-hard to approximate pointwise, and APX-hard on average. Thus we instead design auctions whose revenue approximates that of the optimal auction. Our main result considers step-function externalities in which a bidder’s value for an outcome is either zero, or equal to his private type if at least one friend has the good. For these settings, we provide a e / e + 1-approximation. We also give a 0.25-approximation auction for general single-parameter submodular network externalities, and discuss optimizing over a class of simple pricing strategies.

Förderung

  • Alfred P. Sloan Foundation
  • Microsoft Research
  • Division of Computing and Communication Foundations
  • Division of Information and Intelligent Systems
  • Cisco Systems

Zitieren

APA

Haghpanah, N., Immorlica, N., Mirrokni, V., & Munagala, K. (2013). Optimal Auctions with Positive Network Externalities. ACM Transactions on Economics and Computation. https://doi.org/10.1145/2465769.2465778

Vancouver

Haghpanah N, Immorlica N, Mirrokni V, Munagala K. Optimal Auctions with Positive Network Externalities. ACM Transactions on Economics and Computation. 2013. doi:10.1145/2465769.2465778

BibTeX
@article{Haghpanah2013,
  author = {Haghpanah, Nima and Immorlica, Nicole and Mirrokni, Vahab and Munagala, Kamesh},
  title = {Optimal Auctions with Positive Network Externalities},
  journal = {ACM Transactions on Economics and Computation},
  year = {2013},
  doi = {10.1145/2465769.2465778}
}
Kostenlos starten →