Revenue maximization with nonexcludable goods

Mohammad Hossein Bateni, Nima Haghpanah, Balasubramanian Sivan, Morteza Zadimoghaddam

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

3 Scopus citations


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 optimization problem involved in implementing the revenue optimal mechanism is hard to approximate within a factor of Ω(n 2-ε) (assuming P ≠ NP) even in star graphs, and that even in expectation over the valuation profiles, the problem is APX-hard. However, in a relevant special case 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)
Title of host publicationWeb and Internet Economics - 9th International Conference, WINE 2013, Proceedings
Number of pages14
StatePublished - 2013
Event9th International Conference on Web and Internet Economics, WINE 2013 - Cambridge, MA, United States
Duration: Dec 11 2013Dec 14 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8289 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Conference on Web and Internet Economics, WINE 2013
Country/TerritoryUnited States
CityCambridge, MA

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this