Approximation schemes for sequential posted pricing in multi-unit auctions

Tanmoy Chakraborty, Eyal Even-Dar, Sudipto Guha, Yishay Mansour, S. Muthukrishnan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We design algorithms for computing approximately revenue-maximizing sequential posted-pricing mechanisms (SPM) in K-unit auctions, in a standard Bayesian model. A seller has K copies of an item to sell, and there are n buyers, each interested in only one copy, and has some value for the item. The seller posts a price for each buyer, using Bayesian information about buyers' valuations, who arrive in a sequence. An SPM specifies the ordering of buyers and the posted prices, and may be adaptive or non-adaptive in its behavior. The goal is to design SPM in polynomial time to maximize expected revenue. We compare against the expected revenue of optimal SPM, and provide a polynomial time approximation scheme (PTAS) for both non-adaptive and adaptive SPMs. This is achieved by two algorithms: an efficient algorithm that gives a -approximation (and hence a PTAS for sufficiently large K), and another that is a PTAS for constant K. The first algorithm yields a non-adaptive SPM that yields its approximation guarantees against an optimal adaptive SPM - this implies that the adaptivity gap in SPMs vanishes as K becomes larger.

    Original languageEnglish (US)
    Title of host publicationInternet and Network Economics - 6th International Workshop, WINE 2010, Proceedings
    Pages158-169
    Number of pages12
    DOIs
    StatePublished - 2010
    Event6th International Workshop on Internet and Network Economics, WINE 2010 - Stanford, CA, United States
    Duration: Dec 13 2010Dec 17 2010

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume6484 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference6th International Workshop on Internet and Network Economics, WINE 2010
    CountryUnited States
    CityStanford, CA
    Period12/13/1012/17/10

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Approximation schemes for sequential posted pricing in multi-unit auctions'. Together they form a unique fingerprint.

  • Cite this

    Chakraborty, T., Even-Dar, E., Guha, S., Mansour, Y., & Muthukrishnan, S. (2010). Approximation schemes for sequential posted pricing in multi-unit auctions. In Internet and Network Economics - 6th International Workshop, WINE 2010, Proceedings (pp. 158-169). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6484 LNCS). https://doi.org/10.1007/978-3-642-17572-5_13