×

Revenue submodularity. (English) Zbl 1246.91054

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.

MSC:

91B26 Auctions, bargaining, bidding and selling, and other market models
PDFBibTeX XMLCite
Full Text: DOI