Revenue Submodularity

Shaddin Dughmi; Tim Roughgarden; Mukund Sundararajan

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

Download

645 downloads

Cite: BibTeX Plain Text

@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 Dughmi¹^,*, Tim Roughgarden¹^,*, Mukund Sundararajan¹^,*

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.

Published: 2012-05-16

: http://dx.doi.org/10.1007/978-3-642-03821-1_13

Revenue Submodularity

Abstract

About EAI

Community

Publish with EAI