{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,28]],"date-time":"2026-08-28T06:36:34Z","timestamp":1787898994122,"version":"build-2784847793"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T00:00:00Z","timestamp":1616371200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["1435\/14"],"award-info":[{"award-number":["1435\/14"]}]},{"name":"Israel-USA Binational Science Foundation","award":["2014389"],"award-info":[{"award-number":["2014389"]}]},{"name":"European Union's Horizon 2020 research and innovation programme","award":["740282"],"award-info":[{"award-number":["740282"]}]},{"name":"NSF","award":["CCF-1717899"],"award-info":[{"award-number":["CCF-1717899"]}]},{"name":"NSF CAREER","award":["CCF-1942497"],"award-info":[{"award-number":["CCF-1942497"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n                    We consider the sample complexity of revenue maximization for multiple bidders in unrestricted multi-dimensional settings. Specifically, we study the standard model of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>\n                          \n                        <\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    additive bidders whose values for\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>\n                          \n                        <\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    heterogeneous items are drawn independently. For any such instance and any\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>\n                          \n                        <\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , we show that it is possible to learn an\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>\n                          \n                        <\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -Bayesian Incentive Compatible auction whose expected revenue is within\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>\n                          \n                        <\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    of the optimal\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>\n                          \n                        <\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -BIC auction from only polynomially many samples.\n                  <\/jats:p>\n                  <jats:p>\n                    Our fully nonparametric approach is based on ideas that hold quite generally and completely sidestep the difficulty of characterizing optimal (or near-optimal) auctions for these settings. Therefore, our results easily extend to general multi-dimensional settings, including valuations that are not necessarily even\n                    <jats:italic>subadditive<\/jats:italic>\n                    , and arbitrary allocation constraints. For the cases of a single bidder and many goods, or a single parameter (good) and many bidders, our analysis yields exact incentive compatibility (and for the latter also computational efficiency). Although the single-parameter case is already well understood, our corollary for this case extends slightly the state of the art.\n                  <\/jats:p>","DOI":"10.1145\/3439722","type":"journal-article","created":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T12:22:02Z","timestamp":1616415722000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["The Sample Complexity of Up-to-\u03b5 Multi-dimensional Revenue Maximization"],"prefix":"10.1145","volume":"68","author":[{"given":"Yannai A.","family":"Gonczarowski","sequence":"first","affiliation":[{"name":"Microsoft Research, Cambridge, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Matthew","family":"Weinberg","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,3,22]]},"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.1109\/FOCS.2014.11"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0794"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.50"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3157096.3157330"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219217"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133093"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.54"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.88"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897645"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055465"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250946"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806733"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807366"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940756"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591867"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482593"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229042"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897553"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.03.011"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13129-0_22"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055492"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283462"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329648"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188786"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055427"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201918)","author":"Gonczarowski Yannai A.","unstructured":"Yannai A. Gonczarowski and S. Matthew Weinberg . 2018. The sample complexity of up-to- multi-dimensional revenue maximization . In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201918) . 416\u2013426. Yannai A. Gonczarowski and S. Matthew Weinberg. 2018. The sample complexity of up-to- multi-dimensional revenue maximization. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201918). 416\u2013426."},{"key":"e_1_2_1_28_1","volume-title":"Zhihao Gavin Tang, and Xinzhi Zhang","author":"Guo Chenghao","year":"2019","unstructured":"Chenghao Guo , Zhiyi Huang , Zhihao Gavin Tang, and Xinzhi Zhang . 2019 . Generalizing Complex Hypotheses on Product Distributions : Auctions, Prophet Inequalities, and Pandora\u2019s Problem. arXiv:1911.11936. Retrieved from https:\/\/arxiv.org\/abs\/1911.11936. Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang. 2019. Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora\u2019s Problem. arXiv:1911.11936. Retrieved from https:\/\/arxiv.org\/abs\/1911.11936."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229061"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482544"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.3982\/TE1517"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329632"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133094"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764475"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201919)","author":"Kothari Pravesh","unstructured":"Pravesh Kothari , Divyarthi Mohan , Ariel Schvartzman , Sahil Singla , and S. Matthew Weinberg . 2019. Approximation schemes for a buyer with independent items via symmetries . In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201919) . Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, and S. Matthew Weinberg. 2019. Approximation schemes for a buyer with independent items via symmetries. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201919)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/2969239.2969255"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 29th Annual Conference on Neural Information Processing Systems (NIPS\u201915)","author":"Morgenstern Jamie","year":"2015","unstructured":"Jamie Morgenstern and Tim Roughgarden . 2015 . On the pseudo-dimension of nearly optimal auctions . In Proceedings of the 29th Annual Conference on Neural Information Processing Systems (NIPS\u201915) . 136\u2013144. Jamie Morgenstern and Tim Roughgarden. 2015. On the pseudo-dimension of nearly optimal auctions. In Proceedings of the 29th Annual Conference on Neural Information Processing Systems (NIPS\u201915). 136\u2013144."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940723"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764510"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/3295222.3295287"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 31th Annual 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 31th Annual Conference on Neural Information Processing Systems (NIPS\u201917) . 5352\u20135359. Vasilis Syrgkanis. 2017. A sample complexity measure with applications to learning optimal auctions. In Proceedings of the 31th Annual Conference on Neural Information Processing Systems (NIPS\u201917). 5352\u20135359."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722137"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085120"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 18th ACM Conference on Economics and Computation (EC\u201917)","author":"Chi-Chih Yao Andrew","year":"2017","unstructured":"Andrew Chi-Chih Yao . 2017 . Dominant-strategy versus Bayesian multi-item auctions: Maximum revenue determination and comparison . In Proceedings of the 18th ACM Conference on Economics and Computation (EC\u201917) . 3\u201320. Andrew Chi-Chih Yao. 2017. Dominant-strategy versus Bayesian multi-item auctions: Maximum revenue determination and comparison. In Proceedings of the 18th ACM Conference on Economics and Computation (EC\u201917). 3\u201320."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3439722","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3439722","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3439722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:01:52Z","timestamp":1750183312000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3439722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,22]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3439722"],"URL":"https:\/\/doi.org\/10.1145\/3439722","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,22]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}