TY - GEN
T1 - Revenue maximization with nonexcludable goods
AU - Bateni, Mohammad Hossein
AU - Haghpanah, Nima
AU - Sivan, Balasubramanian
AU - Zadimoghaddam, Morteza
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84893118207&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893118207&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-45046-4_5
DO - 10.1007/978-3-642-45046-4_5
M3 - Conference contribution
AN - SCOPUS:84893118207
SN - 9783642450457
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 40
EP - 53
BT - Web and Internet Economics - 9th International Conference, WINE 2013, Proceedings
T2 - 9th International Conference on Web and Internet Economics, WINE 2013
Y2 - 11 December 2013 through 14 December 2013
ER -