A sequence of recent studies show that even in the simple setting of a single seller and a single buyer with additive, independent valuations over m items, the revenue-maximizing mechanism is prohibitively complex. This problem has been addressed using two main approaches: • Approximation: the best of two simple mechanisms (sell each item separately, or sell all the items as one bundle) gives 1/6 of the optimal revenue [1]. • Enhanced competition: running the simple VCG mechanism with additional m buyers extracts at least the optimal revenue in the original market [17] . Both approaches, however, suffer from severe drawbacks: On the one hand, losing 83% of the revenue is hardly acceptable in any application. On the other hand, attracting a linear number of new buyers may be prohibitive. We show that by combining the two approaches one can achieve the best of both worlds. Specifically, for any constant ϵ one can obtain a (1 − ϵ ) fraction of the optimal revenue by running simple mechanisms -either selling each item separately or selling all items as a single bundle -with substantially fewer additional buyers: logarithmic, constant, or even none in some cases.
Feldman et al. REF prove that selling separately to ( ln( / )/ ) additional buyers exceeds a (1 − ) fraction of the optimal revenue (without the additional buyers).
99% Revenue via Enhanced Competition
EC '18
Computer Science Mathematics