TY - GEN
T1 - A simple and approximately optimal mechanism for an additive Buyer
AU - Babaioff, Moshe
AU - Immorlica, Nicole
AU - Lucier, Brendan
AU - Weinberg, S. Matthew
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/12/7
Y1 - 2014/12/7
N2 - We consider a monopolist seller with n heterogeneousitems, facing a single buyer. The buyer hasa value for each item drawn independently according to(non-identical) distributions, and his value for a set ofitems is additive. The seller aims to maximize his revenue.It is known that an optimal mechanism in this setting maybe quite complex, requiring randomization [19] and menusof infinite size [15]. Hart and Nisan [17] have initiated astudy of two very simple pricing schemes for this setting:item pricing, in which each item is priced at its monopolyreserve; and bundle pricing, in which the entire set ofitems is priced and sold as one bundle. Hart and Nisan [17]have shown that neither scheme can guarantee more thana vanishingly small fraction of the optimal revenue. Insharp contrast, we show that for any distributions, thebetter of item and bundle pricing is a constant-factorapproximation to the optimal revenue. We further discussextensions to multiple buyers and to valuations that arecorrelated across items.
AB - We consider a monopolist seller with n heterogeneousitems, facing a single buyer. The buyer hasa value for each item drawn independently according to(non-identical) distributions, and his value for a set ofitems is additive. The seller aims to maximize his revenue.It is known that an optimal mechanism in this setting maybe quite complex, requiring randomization [19] and menusof infinite size [15]. Hart and Nisan [17] have initiated astudy of two very simple pricing schemes for this setting:item pricing, in which each item is priced at its monopolyreserve; and bundle pricing, in which the entire set ofitems is priced and sold as one bundle. Hart and Nisan [17]have shown that neither scheme can guarantee more thana vanishingly small fraction of the optimal revenue. Insharp contrast, we show that for any distributions, thebetter of item and bundle pricing is a constant-factorapproximation to the optimal revenue. We further discussextensions to multiple buyers and to valuations that arecorrelated across items.
UR - http://www.scopus.com/inward/record.url?scp=84919965141&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84919965141&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2014.11
DO - 10.1109/FOCS.2014.11
M3 - Conference contribution
AN - SCOPUS:84919965141
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 21
EP - 30
BT - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
PB - IEEE Computer Society
T2 - 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014
Y2 - 18 October 2014 through 21 October 2014
ER -