{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:13Z","timestamp":1750220593099,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T00:00:00Z","timestamp":1611792000000},"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":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>\n            Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product is fixed in advance, and a probabilistic choice function describes which product a customer will choose from any given subset. We introduce the combinatorial assortment problem, where each customer may select a bundle of products. We consider a choice model in which each consumer selects a utility-maximizing bundle subject to a private valuation function, and study the complexity of the resulting optimization problem. Our main result is an exact algorithm for additive\n            <jats:italic>k<\/jats:italic>\n            -demand valuations, under a model of vertical differentiation in which customers agree on the relative value of each pair of items but differ in their absolute willingness to pay. For valuations that are vertically differentiated but not necessarily additive\n            <jats:italic>k<\/jats:italic>\n            -demand, we show how to obtain constant approximations under a \u201cwell-priced\u201d condition, where each product\u2019s price is sufficiently high. We further show that even for a single customer with known valuation, any sub-polynomial approximation to the problem requires exponentially many demand queries when the valuation function is XOS and that no FPTAS exists even when the valuation is succinctly representable.\n          <\/jats:p>","DOI":"10.1145\/3434415","type":"journal-article","created":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T11:47:31Z","timestamp":1611834451000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Combinatorial Assortment Optimization"],"prefix":"10.1145","volume":"9","author":[{"given":"Nicole","family":"Immorlica","sequence":"first","affiliation":[{"name":"Microsoft Research"}]},{"given":"Brendan","family":"Lucier","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]},{"given":"Jieming","family":"Mao","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}]},{"given":"Vasilis","family":"Syrgkanis","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]},{"given":"Christos","family":"Tzamos","sequence":"additional","affiliation":[{"name":"University of Wisconsin\u2014Madison"}]}],"member":"320","published-online":{"date-parts":[[2021,1,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940779"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2015.1459"},{"key":"e_1_2_1_3_1","first-page":"3","article-title":"A column generation algorithm for choice-based network revenue management","volume":"57","author":"Miranda Bront Juan Jos\u00e9","year":"2009","unstructured":"Juan Jos\u00e9 Miranda Bront , Isabel M\u00e9ndez-D\u00edaz , and Gustavo Vulcano . 2009 . A column generation algorithm for choice-based network revenue management . Operat. Res. 57 , 3 (May 2009), 769--784. DOI:https:\/\/doi.org\/10.1287\/opre.1080.0567 10.1287\/opre.1080.0567 Juan Jos\u00e9 Miranda Bront, Isabel M\u00e9ndez-D\u00edaz, and Gustavo Vulcano. 2009. A column generation algorithm for choice-based network revenue management. Operat. Res. 57, 3 (May 2009), 769--784. DOI:https:\/\/doi.org\/10.1287\/opre.1080.0567","journal-title":"Operat. Res."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.88"},{"key":"e_1_2_1_5_1","first-page":"276","article-title":"Dynamic Assortment with Demand Learning for Seasonal Consumer Goods. Manage","volume":"53","author":"Caro Felipe","year":"2007","unstructured":"Felipe Caro and J\u00e9r\u00e9mie Gallien . 2007 . Dynamic Assortment with Demand Learning for Seasonal Consumer Goods. Manage . Sci. 53 , 2 (2007), 276 -- 292 . Felipe Caro and J\u00e9r\u00e9mie Gallien. 2007. Dynamic Assortment with Demand Learning for Seasonal Consumer Goods. Manage. Sci. 53, 2 (2007), 276--292.","journal-title":"Sci."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910)","author":"Chawla Shuchi","year":"2010","unstructured":"Shuchi Chawla , Jason D. Hartline , David L. Malec , and Balasubramanian Sivan . 2010 . Multi-parameter mechanism design and sequential posted pricing . In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910) . ACM, New York, NY, 311--320. DOI:https:\/\/doi.org\/10.1145\/ 1806689.1806733 10.1145\/1806689.1806733 Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910). ACM, New York, NY, 311--320. DOI:https:\/\/doi.org\/10.1145\/1806689.1806733"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2014.1256"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680977"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764498"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085134"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/501158.501161"},{"key":"e_1_2_1_13_1","volume-title":"C","author":"Leme Renato Paes","year":"2017","unstructured":"Renato Paes Leme . 2017. Gross substitutability: An algorithmic survey. Games Econ. Behav. 106 , C ( 2017 ), 294--316. DOI:https:\/\/doi.org\/10.1016\/j.geb.2017.10.016 10.1016\/j.geb.2017.10.016 Renato Paes Leme. 2017. Gross substitutability: An algorithmic survey. Games Econ. Behav. 106, C (2017), 294--316. DOI:https:\/\/doi.org\/10.1016\/j.geb.2017.10.016"},{"key":"e_1_2_1_14_1","volume-title":"Gustavo Vulcano, and Paula Zabala.","author":"M\u00e9ndez-D\u00edaz Isabel","year":"2014","unstructured":"Isabel M\u00e9ndez-D\u00edaz , Juan Jos\u00e9 Miranda-Bront , Gustavo Vulcano, and Paula Zabala. 2014 . A branch-and-cut algorithm for the latent-class logit assortment problem. Discr. Appl. Math . 164 (February 2014), 246--263. DOI:https:\/\/doi.org\/10.1016\/j.dam.2012.03.003 10.1016\/j.dam.2012.03.003 Isabel M\u00e9ndez-D\u00edaz, Juan Jos\u00e9 Miranda-Bront, Gustavo Vulcano, and Paula Zabala. 2014. A branch-and-cut algorithm for the latent-class logit assortment problem. Discr. Appl. Math. 164 (February 2014), 246--263. DOI:https:\/\/doi.org\/10.1016\/j.dam.2012.03.003"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0866"},{"key":"e_1_2_1_16_1","first-page":"15","article-title":"Revenue management under a general discrete choice model of consumer behavior. Manage","volume":"50","author":"Talluri Kalyan","year":"2004","unstructured":"Kalyan Talluri and Garrett van Ryzin . 2004 . Revenue management under a general discrete choice model of consumer behavior. Manage . Sci. 50 , 1 (2004), 15 -- 33 . Kalyan Talluri and Garrett van Ryzin. 2004. Revenue management under a general discrete choice model of consumer behavior. Manage. Sci. 50, 1 (2004), 15--33.","journal-title":"Sci."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1067"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434415","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434415","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:48Z","timestamp":1750195908000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434415"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,28]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3434415"],"URL":"https:\/\/doi.org\/10.1145\/3434415","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2021,1,28]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}