Revenue maximization with nonexcludable goods

Mohammadhossein Bateni, Nima Haghpanah, Balasubramanian Sivan, Morteza Zadimoghaddam

Research output: Contribution to journalArticlepeer-review


We study the design of revenue-maximizing mechanisms for selling nonexcludable public goods. In particular, we study revenue-maximizing mechanisms in Bayesian settings for facility location problems on graphs where no agent can be excluded from using a facility that has been constructed. We show that the pointwise optimization problem involved in implementing the revenue optimal mechanism, namely, optimizing over arbitrary profiles of virtual values, is hard to approximate within a factor of Ω(n2-∈) (assuming P ≠ NP) even in star graphs. Furthermore, we show that optimizing the expected revenue is APX-hard. However, in a relevant special case, rooted version with identical distributions, we construct polynomial time truthful mechanisms that approximate the optimal expected revenue within a constant factor. We also study the effect of partially mitigating nonexcludability by collecting tolls for using the facilities. We show that such "posted-price" mechanisms obtain significantly higher revenue and often approach the optimal revenue obtainable with full excludability.

Original languageEnglish (US)
Article number18
JournalACM Transactions on Economics and Computation
Issue number4
StatePublished - Jul 1 2015

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Statistics and Probability
  • Economics and Econometrics
  • Marketing
  • Computational Mathematics


Dive into the research topics of 'Revenue maximization with nonexcludable goods'. Together they form a unique fingerprint.

Cite this