Buy-many mechanisms are not much better than item pricing
研究了在买多件约束下，任何机制的收益最多是单品定价收益的O(log n)倍，说明复杂机制相比简单定价优势有限。
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 which allows the buyer to purchase any number of (randomized) bundles as he pleases. We show that the revenue of any buy-many mechanism is at most O(logn) times the revenue achievable by item pricing, where n is the number of items. This holds even with an arbitrarily correlated distribution of buyer types and arbitrary valuations. Furthermore, no family of mechanisms of subexponential description complexity can achieve better than a logarithmic approximation even for additive valuations.