pdf icon
Volume 8 (2012) Article 5 pp. 95-119
Special Issue in Honor of Rajeev Motwani
Revenue Submodularity
Received: August 3, 2010
Published: April 26, 2012
Download article from ToC site:
[PDF (321K)]    [PS (1955K)]    [PS.GZ (454K)]
[Source ZIP]
Keywords: submodularity, revenue, VCG, optimal auctions, monotonicity
ACM Classification: J.4, F.2.3
AMS Classification: 91B26

Abstract: [Plain Text Version]

We introduce revenue submodularity, the property that market expansion has diminishing returns on an auction's expected revenue. We prove that revenue submodularity is generally possible only in matroid markets, that Bayesian-optimal auctions are always revenue-submodular in such markets, and that the VCG mechanism is revenue-submodular in matroid markets with i.i.d. bidders and “sufficient competition.” We also give two applications of revenue submodularity: good approximation algorithms for novel market expansion problems, and approximate revenue guarantees for the VCG mechanism with i.i.d. bidders.