Revenue maximization with nonexcludable goods

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 Ω(n^2-∈) (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.