Optimal Dynamic Auctions and Simple Index Rules

• 成果类型: Article
• 署名作者: Pai, Mallesh M.; Vohra, Rakesh
• 署名单位: University of Pennsylvania; Northwestern University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0595
• 发表日期: 2013
• 页码: 682-697
• 关键词: Mechanism design; revenue maximization; knapsack-problem

摘要

A monopolist seller has multiple units of an indivisible good to sell over a discrete, finite time horizon. Buyers with unit demand arrive over time and each buyer privately knows her arrival time, her value for a unit, and her deadline. We study whether the seller's optimal allocation rule is a simple index rule. Each buyer is assigned an index and the allocation rule is calculated by a dynamic knapsack algorithm using those indices. Simple indicates that the index of a buyer depends only on local information, i.e., the distribution information for that time period. If buyer deadlines are public, such simple index rules are optimal if the standard increasing hazard rate condition on the distribution of valuations holds, and, given two buyers with the same deadline, the later-arriving one has a lower hazard rate (implying stochastically higher valuations). When buyer deadlines are private, this condition is neither sufficient nor necessary. If the rule we identify is not feasible, then the optimal allocation rule is not a simple index rule and cannot be calculated by backward induction.