TY - GEN

T1 - Approximation schemes for sequential posted pricing in multi-unit auctions

AU - Chakraborty, Tanmoy

AU - Even-Dar, Eyal

AU - Guha, Sudipto

AU - Mansour, Yishay

AU - Muthukrishnan, S.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=78650877476&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650877476&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17572-5_13

DO - 10.1007/978-3-642-17572-5_13

M3 - Conference contribution

AN - SCOPUS:78650877476

SN - 3642175716

SN - 9783642175718

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 158

EP - 169

BT - Internet and Network Economics - 6th International Workshop, WINE 2010, Proceedings

T2 - 6th International Workshop on Internet and Network Economics, WINE 2010

Y2 - 13 December 2010 through 17 December 2010

ER -