The Menu-Size Complexity of Revenue Approximation

We consider a monopolist that is sellingn items to a single additive buyer, where the buyer’s values for the items are drawn according to independent distributions F1,F2,…,Fn that possibly have unbounded support. It is well known that – unlike in the single item case – the revenue-optimal auction (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries. It is also known that simple auctions can extract a constant fraction of the optimal revenue. Nonetheless, the question of the possibility to extract an arbitrarily high fraction of the optimal revenue via a finite menu size remained open.

In this paper, we give an affirmative answer to this open question, showing that for every n and for every ε>0, there exists a complexity bound C=C(n,ε) such that auctions of menu size at most C suffice for obtaining a (1−ε) fraction of the optimal revenue. We prove upper and lower bounds on the revenue approximation complexity C(n,ε).