{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:06:04Z","timestamp":1757541964325,"version":"3.41.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T00:00:00Z","timestamp":1664496000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"German Federal Ministry of Education and Research"},{"name":"FCT via LASIGE Research Unit","award":["UIDB\/00408\/2020 and UIDP\/00408\/2020"],"award-info":[{"award-number":["UIDB\/00408\/2020 and UIDP\/00408\/2020"]}]},{"name":"German Research Foundation (DFG) within the Research Training Group AdONE","award":["GRK 2201"],"award-info":[{"award-number":["GRK 2201"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>\n            We study the problem of multi-dimensional revenue maximization when selling\n            <jats:italic>m<\/jats:italic>\n            items to a buyer that has additive valuations for them, drawn from a (possibly correlated) prior distribution. Unlike traditional Bayesian auction design, we assume that the seller has a very restricted knowledge of this prior: they only know the mean \u03bc\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            and an upper bound \u03c3\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            on the standard deviation of each item\u2019s marginal distribution. Our goal is to design mechanisms that achieve good revenue against an ideal optimal auction that has\n            <jats:italic>full<\/jats:italic>\n            knowledge of the distribution in advance. Informally, our main contribution is a tight quantification of the interplay between the dispersity of the priors and the aforementioned robust approximation ratio. Furthermore, this can be achieved by very simple selling mechanisms.\n          <\/jats:p>\n          <jats:p>\n            More precisely, we show that selling the items via separate price lotteries achieves an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>r<\/jats:italic>\n            ) approximation ratio where\n            <jats:italic>r<\/jats:italic>\n            = max\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            (\u03c3\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            \/\u03bc\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            ) is the maximum coefficient of variation across the items. To prove the result, we leverage a price lottery for the single-item case. If forced to restrict ourselves to deterministic mechanisms, this guarantee degrades to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>r<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ). Assuming independence of the item valuations, these ratios can be further improved by pricing the full bundle. For the case of identical means and variances, in particular, we get a guarantee of\n            <jats:italic>O<\/jats:italic>\n            (log (\n            <jats:italic>r\/m<\/jats:italic>\n            )) that converges to optimality as the number of items grows large. We demonstrate the optimality of the preceding mechanisms by providing matching lower bounds. Our tight analysis for the single-item deterministic case resolves an open gap from the work of Azar and Micali (ITCS\u201913).\n          <\/jats:p>\n          <jats:p>\n            As a by-product, we also show how one can directly use our upper bounds to improve and extend previous results related to the\n            <jats:italic>parametric auctions<\/jats:italic>\n            of Azar et\u00a0al. (SODA\u201913).\n          <\/jats:p>","DOI":"10.1145\/3546606","type":"journal-article","created":{"date-parts":[[2022,9,2]],"date-time":"2022-09-02T11:18:10Z","timestamp":1662117490000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Robust Revenue Maximization Under Minimal Statistical Information"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2382-1779","authenticated-orcid":false,"given":"Yiannis","family":"Giannakopoulos","sequence":"first","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg, Bayern, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5474-3614","authenticated-orcid":false,"given":"Diogo","family":"Po\u00e7as","sequence":"additional","affiliation":[{"name":"Universidade de Lisboa, Lisbon, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7558-2215","authenticated-orcid":false,"given":"Alexandros","family":"Tsigonias-Dimitriadis","sequence":"additional","affiliation":[{"name":"Technical University of Munich (TUM), Bayern, Germany"}]}],"member":"320","published-online":{"date-parts":[[2023,2,8]]},"reference":[{"key":"e_1_3_7_2_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2021.2200"},{"key":"e_1_3_7_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.43"},{"key":"e_1_3_7_4_2","volume-title":"Optimal Parametric Auctions","author":"Azar Pablo","year":"2012","unstructured":"Pablo Azar and Silvio Micali. 2012. Optimal Parametric Auctions. Technical Report MIT-CSAIL-TR-2012-015. MIT CSAIL. http:\/\/hdl.handle.net\/1721.1\/70556."},{"key":"e_1_3_7_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422464"},{"key":"e_1_3_7_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.11"},{"key":"e_1_3_7_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2014.0645"},{"key":"e_1_3_7_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971194"},{"key":"e_1_3_7_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.13"},{"key":"e_1_3_7_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2011.10.018"},{"key":"e_1_3_7_11_2","doi-asserted-by":"publisher","DOI":"10.1162\/jeea.2008.6.2-3.560"},{"key":"e_1_3_7_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/290169"},{"key":"e_1_3_7_13_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"issue":"1","key":"e_1_3_7_14_2","first-page":"180","article-title":"Auctions versus negotiations","volume":"86","author":"Bulow Jeremy","year":"1996","unstructured":"Jeremy Bulow and Paul Klemperer. 1996. Auctions versus negotiations. American Economic Review 86, 1 (1996), 180\u2013194. http:\/\/www.jstor.org\/stable\/2118262.","journal-title":"American Economic Review"},{"key":"e_1_3_7_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.54"},{"key":"e_1_3_7_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897645"},{"key":"e_1_3_7_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055465"},{"key":"e_1_3_7_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2018.05.005"},{"key":"e_1_3_7_19_2","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA14165"},{"key":"e_1_3_7_20_2","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-economics-080218-025616"},{"key":"e_1_3_7_21_2","article-title":"Approximate revenue maximization in interdependent value settings","volume":"1408","author":"Chawla Shuchi","year":"2014","unstructured":"Shuchi Chawla, Hu Fu, and Anna R. Karlin. 2014. Approximate revenue maximization in interdependent value settings. CoRR abs\/1408.4424.","journal-title":"CoRR"},{"key":"e_1_3_7_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806733"},{"key":"e_1_3_7_23_2","article-title":"Bayesian auctions with efficient queries","volume":"1804","author":"Chen Jing","year":"2018","unstructured":"Jing Chen, Bo Li, Yingkai Li, and Pinyan Lu. 2018. Bayesian auctions with efficient queries. CoRR abs\/1804.07451.","journal-title":"CoRR"},{"key":"e_1_3_7_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.93"},{"key":"e_1_3_7_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.133"},{"key":"e_1_3_7_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3157083"},{"key":"e_1_3_7_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591867"},{"key":"e_1_3_7_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.96"},{"key":"e_1_3_7_29_2","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA12618"},{"key":"e_1_3_7_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399543"},{"key":"e_1_3_7_31_2","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1016\/j.geb.2014.03.011","article-title":"Revenue maximization with a single sample","volume":"91","author":"Dhangwatnotai Peerapong","year":"2014","unstructured":"Peerapong Dhangwatnotai, Tim Roughgarden, and Qiqi Yan. 2014. Revenue maximization with a single sample. Games and Economic Behavior 91, C (2014), 318\u2013333.","journal-title":"Games and Economic Behavior"},{"key":"e_1_3_7_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13129-0_22"},{"key":"e_1_3_7_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329591"},{"key":"e_1_3_7_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764489"},{"key":"e_1_3_7_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1072218"},{"key":"e_1_3_7_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64946-3_13"},{"key":"e_1_3_7_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434423"},{"key":"e_1_3_7_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3439722"},{"key":"e_1_3_7_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.135"},{"key":"e_1_3_7_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764498"},{"key":"e_1_3_7_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2482540.2482544"},{"key":"e_1_3_7_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2017.09.001"},{"key":"e_1_3_7_43_2","doi-asserted-by":"crossref","unstructured":"Jason D. Hartline. 2013. Mechanism Design and Approximation. Retrieved September 8 2022 from http:\/\/jasonhartline.com\/MDnA\/.","DOI":"10.1561\/9781601986719"},{"key":"e_1_3_7_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566407"},{"key":"e_1_3_7_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467631"},{"key":"e_1_3_7_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1065719"},{"key":"e_1_3_7_47_2","volume-title":"The Advanced Theory of Statistics (4th ed.)","author":"Kendall Maurice G.","year":"1948","unstructured":"Maurice G. Kendall. 1948. The Advanced Theory of Statistics (4th ed.). Vol. I. Charles Griffin."},{"key":"e_1_3_7_48_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2018.3219"},{"key":"e_1_3_7_49_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1309533110"},{"key":"e_1_3_7_50_2","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331877"},{"key":"e_1_3_7_51_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177697276"},{"key":"e_1_3_7_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2006.12.007"},{"key":"e_1_3_7_53_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813825.009"},{"key":"e_1_3_7_54_2","volume-title":"Introduction to the Theory of Statistics (3rd ed.)","author":"Mood A. M.","year":"1974","unstructured":"A. M. Mood, F. A. Graybill, and D. C. Boes. 1974. Introduction to the Theory of Statistics (3rd ed.). McGraw-Hill."},{"key":"e_1_3_7_55_2","first-page":"1298","volume-title":"Proceedings of the 29th Annual Conference on Learning Theory (COLT\u201916)","author":"Morgenstern Jamie","year":"2016","unstructured":"Jamie Morgenstern and Tim Roughgarden. 2016. Learning simple auctions. In Proceedings of the 29th Annual Conference on Learning Theory (COLT\u201916). 1298\u20131318. http:\/\/proceedings.mlr.press\/v49\/morgenstern16.html."},{"key":"e_1_3_7_56_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729542"},{"key":"e_1_3_7_57_2","doi-asserted-by":"publisher","DOI":"10.5555\/211390"},{"key":"e_1_3_7_58_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_3_7_59_2","doi-asserted-by":"publisher","DOI":"10.5555\/1296179"},{"key":"e_1_3_7_60_2","doi-asserted-by":"publisher","DOI":"10.2307\/1884326"},{"key":"e_1_3_7_61_2","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-economics-080218-025607"},{"key":"e_1_3_7_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3105448"},{"key":"e_1_3_7_63_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmateco.2019.02.007"},{"key":"e_1_3_7_64_2","article-title":"An optimal distributionally robust auction","volume":"2006","author":"Suzdaltsev Alex","year":"2020","unstructured":"Alex Suzdaltsev. 2020. An optimal distributionally robust auction. CoRR abs\/2006.05192.","journal-title":"CoRR"},{"key":"e_1_3_7_65_2","first-page":"5352","volume-title":"Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS\u201917)","author":"Syrgkanis Vasilis","year":"2017","unstructured":"Vasilis Syrgkanis. 2017. A sample complexity measure with applications to learning optimal auctions. In Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS\u201917). 5352\u20135359. http:\/\/papers.nips.cc\/paper\/7119-a-sample-complexity-measure-with-applications-to-learning-optimal-auctions.pdf."},{"key":"e_1_3_7_66_2","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/126"},{"key":"e_1_3_7_67_2","doi-asserted-by":"publisher","DOI":"10.1017\/CCOL0521340446.002"},{"key":"e_1_3_7_68_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.8"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3546606","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3546606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:44:02Z","timestamp":1750272242000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3546606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,30]]},"references-count":67,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3546606"],"URL":"https:\/\/doi.org\/10.1145\/3546606","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2022,9,30]]},"assertion":[{"value":"2021-09-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}