{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:46:36Z","timestamp":1750308396812,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,11,1]],"date-time":"2021-11-01T00:00:00Z","timestamp":1635724800000},"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":[[2021,11]]},"abstract":"<jats:p>\n            We study the communication complexity of incentive compatible auction-protocols between a monopolist seller and a single buyer with a combinatorial valuation function over\n            <jats:italic>n<\/jats:italic>\n            items [Rubinstein and Zhao 2021]. Motivated by the fact that revenue-optimal auctions are randomized [Thanassoulis 2004; Manelli and Vincent 2010; Briest et al. 2010; Pavlov 2011; Hart and Reny 2015] (as well as by an open problem of Babaioff, Gonczarowski, and Nisan [Babaioff et al. 2017]), we focus on the\n            <jats:italic>randomized<\/jats:italic>\n            communication complexity of this problem (in contrast to most prior work on deterministic communication).\n          <\/jats:p>\n          <jats:p>We design simple, incentive compatible, and revenue-optimal auction-protocols whose expected communication complexity is much (in fact infinitely) more efficient than their deterministic counterparts.<\/jats:p>\n          <jats:p>\n            We also give nearly matching lower bounds on the expected communication complexity of approximately-revenue-optimal auctions. These results follow from a simple characterization of incentive compatible auction-protocols that allows us to prove lower bounds against randomized auction-protocols. In particular, our lower bounds give the first approximation-resistant, exponential separation between communication complexity of\n            <jats:italic>incentivizing<\/jats:italic>\n            vs\n            <jats:italic>implementing<\/jats:italic>\n            a Bayesian incentive compatible social choice rule, settling an open question of Fadel and Segal [Fadel and Segal 2009].\n          <\/jats:p>","DOI":"10.1145\/3505156.3505165","type":"journal-article","created":{"date-parts":[[2021,12,6]],"date-time":"2021-12-06T17:05:25Z","timestamp":1638810325000},"page":"75-83","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The randomized communication complexity of revenue maximization"],"prefix":"10.1145","volume":"19","author":[{"given":"Aviad","family":"Rubinstein","sequence":"first","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junyao","family":"Zhao","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,12,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055426"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873650"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897645"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055465"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940756"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.93"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634171"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634170"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764539"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Dobzinski S. 2016. Computational efficiency requires simple taxation. In FOCS.  Dobzinski S. 2016. Computational efficiency requires simple taxation. In FOCS.","DOI":"10.1109\/FOCS.2016.30"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2007.09.015"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00045"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2019.07.006"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.3982\/TE1517"},{"volume":"11316","volume-title":"WINE 2018, Oxford, UK, December 15-17, 2018, Proceedings, G. Christodoulou and T. Harks, Eds. Lecture Notes in Computer Science","author":"Immorlica N.","key":"e_1_2_1_15_1"},{"volume-title":"the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Kothari P.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA8025"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.54"},{"key":"e_1_2_1_19_1","first-page":"3","article-title":"Optimal mechanism for selling two goods","volume":"11","author":"Pavlov G.","year":"2011","journal-title":"Journal of Theoretical Economics"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105448"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451111"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2003.09.002"}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3505156.3505165","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3505156.3505165","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:45:06Z","timestamp":1750268706000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3505156.3505165"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["10.1145\/3505156.3505165"],"URL":"https:\/\/doi.org\/10.1145\/3505156.3505165","relation":{},"ISSN":["1551-9031"],"issn-type":[{"type":"electronic","value":"1551-9031"}],"subject":[],"published":{"date-parts":[[2021,11]]},"assertion":[{"value":"2021-12-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}