Dughmi, Shaddin; Roughgarden, Tim; Sundararajan, Mukund Revenue submodularity. (English) Zbl 1246.91054 Theory Comput. 8, Paper No. 5, 95-119 (2012). Summary: 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. Cited in 13 Documents MSC: 91B26 Auctions, bargaining, bidding and selling, and other market models Keywords:submodularity; revenue; VCG; optimal auctions; monotonicity PDFBibTeX XMLCite \textit{S. Dughmi} et al., Theory Comput. 8, Paper No. 5, 95--119 (2012; Zbl 1246.91054) Full Text: DOI