TL;DR
This paper investigates the "menu complexity" (the number of distinct options offered to a buyer) in the "FedEx problem," a scenario where a buyer has both a value for an item and a deadline to receive it. The authors prove that while extracting the exactly optimal revenue requires an exponentially large menu of options, you can achieve near-optimal revenue ($1-\epsilon$ approximation) with a menu size that scales polynomially. Along the way, they develop a novel mathematical technique for approximating concave functions that is of independent interest.
What Problem Does This Paper Address?
In algorithmic game theory, mechanism design usually falls into two buckets: single-dimensional settings (which are well-understood and yield simple optimal auctions) and multi-dimensional settings (which are notoriously chaotic, often requiring randomized auctions with infinite options).
This paper looks at a "one-and-a-half-dimensional" setting known as the FedEx problem. Here, a single buyer wants an item and has two private parameters: a value $v$ and a deadline $i$ (out of $n$ possible days). If they get the item by day $i$, they get value $v$; otherwise, they get 0.
A key metric for the simplicity of an auction is its menu complexity—the number of distinct (allocation, price) pairs the seller offers. Previous work provided an algorithm to find the optimal auction for the FedEx problem, but it produced a menu with $2^n - 1$ options. The authors tackle two main questions: Is this exponential menu complexity strictly necessary to get optimal revenue? And if we are willing to accept a tiny loss in revenue, can we drastically shrink the menu size?
Methods
To bound the menu complexity of approximate auctions, the authors map the economic problem to a classic geometry problem: polygon approximation of concave functions.
In the FedEx problem, the optimal revenue achievable on a given day can be represented as a concave "revenue curve." The authors show that creating a simplified menu with $k$ options is mathematically equivalent to approximating this concave curve using a piecewise-linear function (a polygon) with $k$ segments.
Standard polygon approximation techniques guarantee an additive error but require a number of segments that scales linearly with the maximum possible value ($v_{max}$). To keep the menu complexity strictly polynomial, the authors develop a novel "hybrid additive-multiplicative" polygon approximation. This new technique cleverly bounds the error such that the number of required line segments scales only logarithmically with $v_{max}$ (i.e., $\ln(v_{max})$), a massive theoretical improvement.
Datasets
Not discussed in the paper. (This is a theoretical computer science paper focused on mathematical proofs and algorithmic bounds, so no empirical datasets are used).
Key Insights and Ideas
- Exponential menus are unavoidable for perfection: The authors construct a worst-case FedEx instance where the optimal auction inherently forces prices to "split" at every deadline. This proves that the $2^n - 1$ menu complexity isn't just a quirk of previous algorithms; it is mathematically required to squeeze out every last cent of optimal revenue.
- Approximation collapses complexity: By relaxing the goal from exact optimality to a $(1-\epsilon)$-approximation, the required menu complexity plummets from exponential to fully polynomial.
- Geometry meets Economics: The direct reduction from menu complexity to the number of line segments needed to approximate a concave function is a powerful conceptual bridge. It implies that low menu complexity is exactly equivalent to piecewise-linear utility curves with few segments.
- "Regularity" doesn't guarantee simplicity here: In standard 1D auctions, a statistical condition called "regularity" guarantees that the optimal auction is simple and deterministic. The authors construct an instance showing that in 1.5D settings, regular distributions can still result in complex, randomized optimal mechanisms, resolving an open question in the field.
Key Results
- Exact Lower Bound: There exist instances of the FedEx problem on $n$ days where the optimal mechanism requires a menu complexity of exactly $2^n - 1$.
- Approximation Upper Bound: For all instances, there exists a mechanism guaranteeing a $(1-\epsilon)$-approximation to the optimal revenue with a polynomial menu complexity of $O(n^{3/2} \sqrt{\min\{n/\epsilon, \ln(v_{max})\}/\epsilon})$, which simplifies to roughly $O(n^2/\epsilon)$.
- Approximation Lower Bound: The authors prove their approximation scheme is nearly tight. They show that any mechanism guaranteeing a $(1 - O(1/n^2))$-approximation requires a menu complexity of at least $\Omega(n^2)$.
- Mathematical Contribution: They prove a tight bound for their new hybrid polygon approximation: a concave function can be approximated with the desired hybrid error using $\Theta(\sqrt{\ln(v_{max})/\epsilon})$ segments.
Limitations and Future Work
The authors note a small theoretical gap of $\sqrt{n \log n}$ between their upper and lower bounds for the approximate menu complexity. Additionally, the upper bound still has a logarithmic dependence on the maximum value ($v_{max}$). They suggest future work could investigate whether this dependence can be entirely removed or replaced with a parameter like $\log(n/\epsilon)$.
More broadly, the authors highlight two major frontiers:
- Multi-bidder 1.5D settings: The current work (and all existing work in this specific niche) is limited to a single bidder. Expanding this to multiple competing bidders is a pressing next step.
- Truly multi-dimensional settings: The authors hope their polygon approximation approach can be generalized to higher-dimensional utility curves to close the massive gaps between known upper (exponential) and lower (polynomial) bounds for menu complexity in fully multi-dimensional mechanism design.
Summary updated