Optimal auctions with positive network externalities

Nima Haghpanah, Nicole Immorlica, Vahab Mirrokni, Kamesh Munagala

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations


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 APX-hard. 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.

Original languageEnglish (US)
Title of host publicationEC'11 - Proceedings of the 12th ACM Conference on Electronic Commerce
Number of pages10
StatePublished - 2011
Event12th ACM Conference on Electronic Commerce, EC'11 - San Jose, CA, United States
Duration: Jun 5 2011Jun 9 2011

Publication series

NameProceedings of the ACM Conference on Electronic Commerce


Other12th ACM Conference on Electronic Commerce, EC'11
Country/TerritoryUnited States
CitySan Jose, CA

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'Optimal auctions with positive network externalities'. Together they form a unique fingerprint.

Cite this