{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:40Z","timestamp":1750219840696,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"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":[[2022,6,30]]},"abstract":"<jats:p>In this article, we introduce a Bayesian revenue-maximizing mechanism design model where the items have fixed, exogenously given prices. Buyers are unit-demand and have an ordinal ranking over purchasing either one of these items at its given price or purchasing nothing. This model arises naturally from the assortment optimization problem, in that the single-buyer optimization problem over deterministic mechanisms reduces to deciding on an assortment of items to \u201cshow.\u201d We study its multi-buyer generalization in the simplest setting of single-winner auctions or, more broadly, any service-constrained environment. Our main result is that if the buyer rankings are drawn independently from Markov chain choice models, then the optimal mechanism is computationally tractable, and structurally a virtual welfare maximizer. We also show that for ranking distributions not induced by Markov chains, the optimal mechanism may not be a virtual welfare maximizer. Finally, we apply our virtual valuation notion for Markov chains, in conjunction with existing prophet inequalities, to improve algorithmic guarantees for online assortment problems.<\/jats:p>","DOI":"10.1145\/3555045","type":"journal-article","created":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T09:51:54Z","timestamp":1663235514000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Revenue-Optimal Deterministic Auctions for Multiple Buyers with Ordinal Preferences over Fixed-Price Items"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2420-4468","authenticated-orcid":false,"given":"Will","family":"Ma","sequence":"first","affiliation":[{"name":"Columbia University, New York, NY"}]}],"member":"320","published-online":{"date-parts":[[2022,10,16]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.73"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229017"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1754"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0511"},{"key":"e_1_3_3_6_2","article-title":"Improved approximations for free-order prophets and second-price auctions","author":"Beyhaghi Hedyeh","year":"2018","unstructured":"Hedyeh Beyhaghi, Negin Golrezaei, Renato Paes Leme, Martin Pal, and Balasubramanian Sivan. 2018. Improved approximations for free-order prophets and second-price auctions. arXiv preprint arXiv:1807.03435 (2018).","journal-title":"arXiv preprint arXiv:1807.03435"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/978-3-642-22935-0_8","volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques","author":"Bhalgat Anand","year":"2011","unstructured":"Anand Bhalgat, Deeparnab Chakrabarty, and Sanjeev Khanna. 2011. Social welfare in one-sided matching markets without money. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. Springer, 87\u201398."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2016.1505"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554810"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250946"},{"key":"e_1_3_3_11_2","first-page":"311","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing","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. ACM, New York, NY, 311\u2013320."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2012.08.010"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.93"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.03.016"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2018.11.010"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.118"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2018.3230"},{"key":"e_1_3_3_18_2","first-page":"736","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Elkind Edith","year":"2007","unstructured":"Edith Elkind. 2007. Designing and learning optimal finite support auctions. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 736\u2013745."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1120.1610"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2017.1628"},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","unstructured":"Guillermo Gallego and Anran Li. 2017. Attention consideration then selection choice model. SSRN . Retrieved September 24 2022 from https:\/\/ssrn.com\/abstract=2926942.","DOI":"10.2139\/ssrn.2926942"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/2827835.2827840"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.2307\/1911681"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2014.1939"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/3215696.3215703"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01242849"},{"key":"e_1_3_3_27_2","article-title":"When is assortment optimization optimal?","author":"Ma Will","year":"2021","unstructured":"Will Ma. 2021. When is assortment optimization optimal? arXiv preprint arXiv:2105.10433 (2021).","journal-title":"arXiv preprint arXiv:2105.10433"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1957"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2020.3671"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1765(82)90003-9"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2019.3346"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481.012"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(74)90033-0"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.2307\/2938268"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s003550050160"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1030.0147"},{"key":"e_1_3_3_38_2","article-title":"Submodular order functions and assortment optimization","author":"Udwani Rajan","year":"2021","unstructured":"Rajan Udwani. 2021. Submodular order functions and assortment optimization. arXiv preprint arXiv:2107.02743 (2021).","journal-title":"arXiv preprint arXiv:2107.02743"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1050.0194"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555045","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3555045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:49Z","timestamp":1750178809000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3555045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3555045"],"URL":"https:\/\/doi.org\/10.1145\/3555045","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"2021-01-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}