Extreme value theorems for optimal multidimensional pricing

• 成果类型: Article
• 署名作者: Cai, Yang; Daskalakis, Constantinos
• 署名单位: McGill University; Massachusetts Institute of Technology (MIT)
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2015.02.003
• 发表日期: 2015
• 页码: 266-305
• 关键词: Multidimensional pricing; revenue maximization; extreme value theory

摘要

We provide near-optimal, polynomial-time algorithms for pricing n items to optimize revenue against a unit-demand buyer whose values are independent from known distributions. For any chosen is an element of > 0 and values in [0,1], our algorithm's revenue is optimal up to an additive is an element of. For values sampled from monotone hazard rate (MHR) or regular distributions, we achieve a (1- is an element of)-fraction of the optimal revenue in polynomial time and quasi-polynomial time, respectively. Our algorithm for bounded distributions applies probabilistic techniques to understand the statistical properties of revenue distributions, obtaining a reduction in the algorithm's search space via dynamic programming. Adapting this approach to MHR and regular distributions requires the proof of novel extreme-value theorems for such distributions. As a byproduct, we show that, for all n, a constant or a polylogarithmic (in n) number of distinct prices suffice for near-optimal revenue for MHR and regular distributions, respectively. (C) 2015 Elsevier Inc. All rights reserved.