Theory of Computing ------------------- Title : Revenue Submodularity Authors : Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan Volume : 8 Number : 5 Pages : 95-119 URL : https://theoryofcomputing.org/articles/v008a005 Abstract -------- 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.