Detail-free, Posted-Price Mechanisms for Limited Supply Online Auctions

We consider online posted-price mechanisms with limited supply. A seller has k items for sale and is facing n potential buyers (“agents”) that are arriving sequentially. Each agent is interested in buying one item. Each agent’s value for an item is an IID sample from some fixed distribution with support [0,1]. The seller offers a take-it-or-leave-it price to each arriving agent (possibly different for different agents), and aims to maximize his expected revenue.

We focus on mechanisms that do not use any information about the distribution; such mechanisms are called detail-free. They are desirable because knowing the distribution is unrealistic in many practical scenarios. We study how the revenue of such mechanisms compares to the revenue of the optimal offline mechanism that knows the distribution (“offline benchmark”).

We present a detail-free online posted-price mechanism whose revenue is within O((k log n)^2/3), in additive terms, of the offline benchmark, for every distribution that is regular. In fact, this guarantee holds without any assumptions if the benchmark is relaxed to fixed-price mechanisms.

The upper bound can be improved to O(√k log n) for k under a stronger, yet quite common, assumption on the distribution: monotone hazard rate. A strong intuition from prior work suggests that one should not hope for a sufficiently general upper bound that is better than O(√k).