Beyond Buy-One in Approximately Optimal Multi-Item Auctions

Optimal multi-item auctions are known to be complex and hard to characterize. In fact, we know that no finite-sized mechanism can approximate the optimal mechanism when selling two items to a single, additive buyer. This pathological result constructs a valuation and distribution that can be exploited by a highly-tailored mechanism. One reason the revenue of this mechanism is unbounded is that it abuses the fact that the buyer can only interact with the mechanism once. Indeed, a series of recent works show how to get around this pathological construction via so-called buy-many or buy-k mechanisms, where the buyer is allowed to interact with the mechanism any number of times or k times, respectively. These new classes of mechanisms show that, perhaps, the benchmark set by the standard buy-one model is too strong to compare against and thus should be relaxed.