Optimal Auctions with Positive Network Externalities
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.
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}
}
EUVIMED