TY - GEN
T1 - Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling
AU - Assadi, Sepehr
AU - Kher, Vikram
AU - Li, George
AU - Schvartzman, Ariel
N1 - Publisher Copyright: © 2023 Owner/Author(s).
PY - 2023/7/9
Y1 - 2023/7/9
N2 - Multi-item revenue-optimal mechanisms are known to be extremely complex, often offering buyers randomized lotteries of goods. In the standard buy-one model, it is known that optimal mechanisms can yield revenue infinitely higher than that of any "simple"mechanism - -the ones with size polynomial in the number of items - -even with just two items and a single buyer [Briest et al. 2015; Hart and Nisan 2017].We introduce a new parameterized class of mechanisms, buy-k mechanisms, which smoothly interpolate between the classical buy-one mechanisms and the recently studied buy-many mechanisms [Chawla et al. 2022, 2019, 2020a,b]. Buy-k mechanisms allow the buyer to buy up to k many menu options. We show that restricting the seller to the class of buy-n incentive-compatible mechanisms suffices to overcome the bizarre, infinite revenue properties of the buy-one model. Our main result is that the revenue gap with respect to bundling, an extremely simple mechanism, is bounded by O(n2) for any arbitrarily correlated distribution D over n items for the case of an additive buyer. Our techniques also allow us to prove similar upper bounds for arbitrary monotone valuations, albeit with an exponential factor in the approximation.On the negative side, we show that allowing the buyer to purchase a small number of menu options does not suffice to guarantee sub-exponential approximations, even when we weaken the benchmark to the optimal buy-k deterministic mechanism. If an additive buyer is only allowed to buy k = (n1/2 - ϵ) many menu options, the gap between the revenue-optimal deterministic buy-k mechanism and bundling may be exponential in n. In particular, this implies that no "simple"mechanism can obtain a sub-exponential approximation in this regime. As a complementary result, we show that when [EQUATION], bundling recovers a poly(n) fraction of the optimal deterministic buy-k mechanism's revenue.
AB - Multi-item revenue-optimal mechanisms are known to be extremely complex, often offering buyers randomized lotteries of goods. In the standard buy-one model, it is known that optimal mechanisms can yield revenue infinitely higher than that of any "simple"mechanism - -the ones with size polynomial in the number of items - -even with just two items and a single buyer [Briest et al. 2015; Hart and Nisan 2017].We introduce a new parameterized class of mechanisms, buy-k mechanisms, which smoothly interpolate between the classical buy-one mechanisms and the recently studied buy-many mechanisms [Chawla et al. 2022, 2019, 2020a,b]. Buy-k mechanisms allow the buyer to buy up to k many menu options. We show that restricting the seller to the class of buy-n incentive-compatible mechanisms suffices to overcome the bizarre, infinite revenue properties of the buy-one model. Our main result is that the revenue gap with respect to bundling, an extremely simple mechanism, is bounded by O(n2) for any arbitrarily correlated distribution D over n items for the case of an additive buyer. Our techniques also allow us to prove similar upper bounds for arbitrary monotone valuations, albeit with an exponential factor in the approximation.On the negative side, we show that allowing the buyer to purchase a small number of menu options does not suffice to guarantee sub-exponential approximations, even when we weaken the benchmark to the optimal buy-k deterministic mechanism. If an additive buyer is only allowed to buy k = (n1/2 - ϵ) many menu options, the gap between the revenue-optimal deterministic buy-k mechanism and bundling may be exponential in n. In particular, this implies that no "simple"mechanism can obtain a sub-exponential approximation in this regime. As a complementary result, we show that when [EQUATION], bundling recovers a poly(n) fraction of the optimal deterministic buy-k mechanism's revenue.
KW - buy-many mechanisms
KW - correlated distributions
KW - multi-item settings
KW - revenue-maximization
UR - http://www.scopus.com/inward/record.url?scp=85168082008&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85168082008&partnerID=8YFLogxK
U2 - 10.1145/3580507.3597662
DO - 10.1145/3580507.3597662
M3 - Conference contribution
T3 - EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation
SP - 123
BT - EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation
PB - Association for Computing Machinery, Inc
T2 - 24th ACM Conference on Economics and Computation, EC 2023
Y2 - 9 July 2023 through 12 July 2023
ER -