Optimal Dynamic Auctions and Simple Index Rules

Abstract

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.