TY - GEN
T1 - On the (in-)approximability of Bayesian Revenue Maximization for a Combinatorial Buyer
AU - Collina, Natalie
AU - Weinberg, S. Matthew
N1 - Publisher Copyright:
© 2020 ACM.
PY - 2020/7/13
Y1 - 2020/7/13
N2 - We consider a revenue-maximizing single seller with mitems for sale to a single buyer whose value v(·) for the items is drawn from a known distribution Dof support k. A series of works by Cai et al. establishes that when each v(·) in the support of Dis additive or unit-demand (or c-demand), the revenue-optimal auction can be found in poly(m,k) time. We show that going barely beyond this, even to matroid-based valuations (a proper subset of Gross Substitutes), results in strong hardness of approximation. Specifically, even on instances with mitems and k ≤ m valuations in the support of D, it is not possible to achieve a 1/m1-ϵ-approximation for any ϵ>0 to the revenue-optimal mechanism for matroid-based valuations in (randomized) poly-time unless NP ĝ† RP (note that a $1/k$-approximation is trivial). Cai et al.'s main technical contribution is a black-box reduction from revenue maximization for valuations in class V to optimizing the difference between two values in class V. Our main technical contribution is a black-box reduction in the other direction (for a wide class of valuation classes), establishing that their reduction is essentially tight.
AB - We consider a revenue-maximizing single seller with mitems for sale to a single buyer whose value v(·) for the items is drawn from a known distribution Dof support k. A series of works by Cai et al. establishes that when each v(·) in the support of Dis additive or unit-demand (or c-demand), the revenue-optimal auction can be found in poly(m,k) time. We show that going barely beyond this, even to matroid-based valuations (a proper subset of Gross Substitutes), results in strong hardness of approximation. Specifically, even on instances with mitems and k ≤ m valuations in the support of D, it is not possible to achieve a 1/m1-ϵ-approximation for any ϵ>0 to the revenue-optimal mechanism for matroid-based valuations in (randomized) poly-time unless NP ĝ† RP (note that a $1/k$-approximation is trivial). Cai et al.'s main technical contribution is a black-box reduction from revenue maximization for valuations in class V to optimizing the difference between two values in class V. Our main technical contribution is a black-box reduction in the other direction (for a wide class of valuation classes), establishing that their reduction is essentially tight.
KW - gross substitutes
KW - optimal mechanism design
KW - reductions
KW - revenue
UR - http://www.scopus.com/inward/record.url?scp=85089269964&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089269964&partnerID=8YFLogxK
U2 - 10.1145/3391403.3399496
DO - 10.1145/3391403.3399496
M3 - Conference contribution
AN - SCOPUS:85089269964
T3 - EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
SP - 477
EP - 497
BT - EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
PB - Association for Computing Machinery
T2 - 21st ACM Conference on Economics and Computation, EC 2020
Y2 - 13 July 2020 through 17 July 2020
ER -