Optimal Auctions with Positive Network Externalities

Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Haghpanah, N; Immorlica, N; Mirrokni, V; Munagala, K

Published Date

  • May 2013

Published In

Volume / Issue

  • 1 / 2

Start / End Page

  • 1 - 24

Published By

Electronic International Standard Serial Number (EISSN)

  • 2167-8383

International Standard Serial Number (ISSN)

  • 2167-8375

Digital Object Identifier (DOI)

  • 10.1145/2465769.2465778


  • en