Buy-Many Mechanisms Are Not Much Better Than Item Pricing

Multi-item mechanisms can be very complex offering many different randomized bundles to the buyer. Such complexity is thought to be necessary as the revenue gaps between optimal mechanisms and simple mechanisms are unbounded. Our work shows these gaps do not apply to most natural situations: they require that the mechanism overcharges the buyer for a bundle while selling individual items at much lower prices. We study revenue maximization under the buy-many constraint: the buyer is allowed to purchase any number of (randomized) bundles as he pleases. The revenue of any buy-many mechanism is at most O(log n) times the revenue achievable by item pricing, where n is the number of items. This holds in the most general setting possible, with an arbitrarily correlated distribution of buyer types and arbitrary valuations. No family of mechanisms of subexponential description complexity can achieve better than a logarithmic approximation even for additive valuations.

• Algorithms and Theory

• Economics and Electronic Commerce