Auctions, Market Mechanisms and Their Applications. First International ICST Conference, AMMA 2009, Boston, MA, USA, May 8-9, 2009, Revised Selected Papers

Research Article

Revenue Submodularity

Download77 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-03821-1_13,
        author={Shaddin Dughmi and Tim Roughgarden and Mukund Sundararajan},
        title={Revenue Submodularity},
        proceedings={Auctions, Market Mechanisms and Their Applications. First International ICST Conference, AMMA 2009, Boston, MA, USA, May 8-9, 2009, Revised Selected Papers},
        proceedings_a={AMMA},
        year={2012},
        month={5},
        keywords={},
        doi={10.1007/978-3-642-03821-1_13}
    }
    
  • Shaddin Dughmi
    Tim Roughgarden
    Mukund Sundararajan
    Year: 2012
    Revenue Submodularity
    AMMA
    Springer
    DOI: 10.1007/978-3-642-03821-1_13
Shaddin Dughmi1,*, Tim Roughgarden1,*, Mukund Sundararajan1,*
  • 1: Stanford University
*Contact email: shaddin@cs.stanford.edu, tim@cs.stanford.edu, mukunds@cs.stanford.edu

Abstract

We introduce , 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 IID 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 IID bidders.