The Menu Complexity of “One-and-a-half” Dimensional Mechanism Design

We study the menu complexity of optimal and approximately-optimal auctions in the context of the “FedEx” problem, a so-called “one-and-a-half-dimensional” setting where a single bidder has both a value and a deadline for receiving an [FGKK16]. The menu complexity of an auction is equal to the number of distinct (allocation, price) pairs that a bidder might receive [HN13]. We show the following when the bidder has n possible deadlines:
– Exponential menu complexity is necessary to be exactly optimal: There exist instances where the optimal mechanism has menu complexity is 2n−1. This matches exactly the upper bound provided by Fiat et al.’s algorithm, and resolves one of their open questions [FGKK16].
– Fully polynomial menu complexity is necessary and sufficient for approximation: For all instances, there exists a mechanism guaranteeing a multiplicative (1-epsilon)-approximation to the optimal revenue with menu complexity O(n3/2min{n/ϵ,ln(vmax)}ϵ‾‾‾‾‾‾‾‾‾‾‾‾√)=O(n2/ϵ), where vmax denotes the largest value in the support of integral distributions.
– There exist instances where any mechanism guaranteeing a multiplicative (1−O(1/n2))-approximation to the optimal revenue requires menu complexity Ω(n2).
Our main technique is the polygon approximation of concave functions [Rote19], and our results here should be of independent interest. We further show how our techniques can be used to resolve an open question of [DW17] on the menu complexity of optimal auctions for a budget-constrained buyer.