{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:26Z","timestamp":1750220666576,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,2]],"date-time":"2020-12-02T00:00:00Z","timestamp":1606867200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGecom Exch."],"published-print":{"date-parts":[[2020,12,2]]},"abstract":"Multi-item mechanisms can be very complex, offering many different bundles to the buyer that could even be randomized. Such complexity is thought to be necessary as the revenue gaps between randomized and deterministic mechanisms, or deterministic and simple mechanisms are huge even for additive valuations. Furthermore, the optimal revenue displays strange properties such as non-continuity: changing valuations by tiny multiplicative amounts can change the optimal revenue by an arbitrarily large multiplicative factor. Our work shows that these strange properties do not apply to most natural situations as they require that the mechanism overcharges the buyer for a bundle while selling individual items at much lower prices. In such cases, the buyer would prefer to break his order into smaller pieces paying a much lower price overall.<\/jats:p>\n \n We advocate studying a new revenue benchmark, namely the optimal revenue achievable by \"buy-many\" mechanisms, that is much better behaved. In a buy-many mechanism, the buyer is allowed to interact with the mechanism multiple times instead of just once. We show that the optimal buy-many revenue for\n any n<\/jats:italic>\n item setting is at most\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n ) times the revenue achievable by item pricing. Furthermore, a mechanism of finite menu-size (\n n<\/jats:italic>\n \/\u03b5)\n \n 2\n \n O<\/jats:italic>\n (\n n<\/jats:italic>\n )\n <\/jats:sup>\n <\/jats:sup>\n suffices to achieve (1 + \u03b5)-approximation to the optimal buy-many revenue. Both these results are tight in a very strong sense, as any family of mechanisms with description complexity sub-doubly-exponential in n cannot achieve better than logarithmic approximation in revenue. In contrast, for buy-one mechanisms, no simple mechanism of finite menu-size can get a finite-approximation in revenue. Moreover, the revenue of buy-one mechanisms can be extremely sensitive to multiplicative changes in values, while as we show optimal buy-many mechanisms satisfy revenue continuity.\n <\/jats:p>","DOI":"10.1145\/3440959.3440963","type":"journal-article","created":{"date-parts":[[2020,12,2]],"date-time":"2020-12-02T23:58:00Z","timestamp":1606953480000},"page":"12-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Buy-many mechanisms"],"prefix":"10.1145","volume":"18","author":[{"given":"Shuchi","family":"Chawla","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison and"}]},{"given":"Yifeng","family":"Teng","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison and"}]},{"given":"Christos","family":"Tzamos","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison"}]}],"member":"320","published-online":{"date-parts":[[2020,12,2]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/3055399.3055426"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/FOCS.2014.11"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/3219166.3219188"},{"doi-asserted-by":"crossref","unstructured":"Briest P. Chawla S. Kleinberg R. and Weinberg S. M. 2015. Pricing lotteries. <i>Journal of Economic Theory 156<\/i> 144-174. Briest P. Chawla S. Kleinberg R. and Weinberg S. M. 2015. Pricing lotteries. <i>Journal of Economic Theory 156<\/i> 144-174.","key":"e_1_2_1_4_1","DOI":"10.1016\/j.jet.2014.04.011"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/3391403.3399541"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/3055399.3055465"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/1250910.1250946"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/1806689.1806733"},{"doi-asserted-by":"crossref","unstructured":"Chawla S. Malec D. and Sivan B. 2015. The power of randomness in bayesian optimal mechanism design. <i>Games and Economic Behavior 91<\/i> 297-317. Chawla S. Malec D. and Sivan B. 2015. The power of randomness in bayesian optimal mechanism design. <i>Games and Economic Behavior 91<\/i> 297-317.","key":"e_1_2_1_9_1","DOI":"10.1016\/j.geb.2012.08.010"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/2940716.2940756"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/3328526.3329583"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/3391403.3399453"},{"doi-asserted-by":"crossref","unstructured":"Daskalakis C. Deckelbaum A. and Tzamos C. 2017. Strong duality for a multiple-good monopolist. <i>Econometrica 85 <\/i> 3 735-767. Daskalakis C. Deckelbaum A. and Tzamos C. 2017. Strong duality for a multiple-good monopolist. <i>Econometrica 85 <\/i> 3 735-767.","key":"e_1_2_1_13_1","DOI":"10.3982\/ECTA12618"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/2229012.2229042"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/3188745.3188786"},{"key":"e_1_2_1_16_1","first-page":"416","article-title":"The sample complexity of up-to-ε multi-dimensional revenue maximization. In <i>2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)<\/i>","author":"Gonczarowski Y. A.","year":"2018","unstructured":"Gonczarowski , Y. A. and Weinberg , S. M. 2018 . The sample complexity of up-to-ε multi-dimensional revenue maximization. In <i>2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)<\/i> . IEEE , 416 - 426 . Gonczarowski, Y. A. and Weinberg, S. M. 2018. The sample complexity of up-to-ε multi-dimensional revenue maximization. In <i>2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)<\/i>. IEEE, 416-426.","journal-title":"IEEE"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/2229012.2229061"},{"doi-asserted-by":"crossref","unstructured":"Hart S. and Nisan N. 2019. Selling multiple correlated goods: Revenue maximization and menu-size complexity. <i>Journal of Economic Theory 183<\/i> 991-1029. Hart S. and Nisan N. 2019. Selling multiple correlated goods: Revenue maximization and menu-size complexity. <i>Journal of Economic Theory 183<\/i> 991-1029.","key":"e_1_2_1_18_1","DOI":"10.1016\/j.jet.2019.07.006"},{"key":"e_1_2_1_19_1","first-page":"220","article-title":"Approximation schemes for a unit-demand buyer with independent items via symmetries. In <i>2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)<\/i>","author":"Kothari P.","year":"2019","unstructured":"Kothari , P. , Singla , S. , Mohan , D. , Schvartzman , A. , and Weinberg , S. M. 2019 . Approximation schemes for a unit-demand buyer with independent items via symmetries. In <i>2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)<\/i> . IEEE , 220 - 232 . Kothari, P., Singla, S., Mohan, D., Schvartzman, A., and Weinberg, S. M. 2019. Approximation schemes for a unit-demand buyer with independent items via symmetries. In <i>2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)<\/i>. IEEE, 220-232.","journal-title":"IEEE"},{"key":"e_1_2_1_20_1","volume-title":"-C","author":"Li X.","year":"2013","unstructured":"Li , X. and Yao , A. C . -C . 2013 . On revenue maximization for selling multiple independently distributed items. <i>Proceedings of the National Academy of Sciences 110,<\/i> 28, 11232-11237. Li, X. and Yao, A. C.-C. 2013. On revenue maximization for selling multiple independently distributed items. <i>Proceedings of the National Academy of Sciences 110,<\/i> 28, 11232-11237."},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/3328526.3329563"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/3105448"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.5555\/2722129.2722137"}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3440959.3440963","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3440959.3440963","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:51Z","timestamp":1750197771000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3440959.3440963"}},"subtitle":["what are they and why should you care?"],"short-title":[],"issued":{"date-parts":[[2020,12,2]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12,2]]}},"alternative-id":["10.1145\/3440959.3440963"],"URL":"https:\/\/doi.org\/10.1145\/3440959.3440963","relation":{},"ISSN":["1551-9031"],"issn-type":[{"type":"electronic","value":"1551-9031"}],"subject":[],"published":{"date-parts":[[2020,12,2]]},"assertion":[{"value":"2020-12-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}