{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:06Z","timestamp":1787340606639,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Israeli Ministry of Science"},{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","award":["Center No. 4\/11"],"award-info":[{"award-number":["Center No. 4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1016885"],"award-info":[{"award-number":["CCF-1016885"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1215965"],"award-info":[{"award-number":["CCF-1215965"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We study the problem of setting a price for a potential buyer with a valuation drawn from an unknown distribution $D$. The seller has \u201cdata\u201d about $D$ in the form of $m \\ge 1$ independent and identically distributed samples, and the algorithmic challenge is to use these samples to obtain expected revenue as close as possible to what could be achieved with advance knowledge of $D$. Our first set of results quantifies the number of samples $m$ that are necessary and sufficient to obtain a $(1-\\epsilon)$-approximation. For example, for an unknown distribution that satisfies the monotone hazard rate (MHR) condition, we prove that $\\tilde{\\Theta}(\\epsilon^{-3\/2})$ samples are necessary and sufficient. Remarkably, this uses fewer samples than is necessary to accurately estimate the expected revenue obtained for such a distribution by even a single reserve price. We also prove essentially tight sample complexity bounds for regular distributions, bounded-support distributions, and a wide class of irregular distributions. Our lower bound approach, which applies to all randomized pricing strategies, borrows tools from differential privacy and information theory, and we believe it could find further applications in auction theory. Our second set of results considers the single-sample case. While no deterministic pricing strategy is better than $\\tfrac{1}{2}$-approximate for regular distributions, for MHR distributions we show how to do better: there is a simple deterministic pricing strategy that guarantees expected revenue at least 0.589 times the maximum possible. We also prove that no deterministic pricing strategy achieves an approximation guarantee better than $\\frac{e}{4} \\approx .68$.<\/jats:p>","DOI":"10.1137\/16m1065719","type":"journal-article","created":{"date-parts":[[2018,5,8]],"date-time":"2018-05-08T12:31:34Z","timestamp":1525782694000},"page":"651-674","source":"Crossref","is-referenced-by-count":37,"title":["Making the Most of Your Samples"],"prefix":"10.1137","volume":"47","author":[{"given":"Zhiyi","family":"Huang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,5,8]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"M. Anthony and P. L. Bartlett,\n                      Neural Network Learning: Theoretical Foundations\n                      , Cambridge University Press, Cambridge, 1999.","DOI":"10.1017\/CBO9780511624216"},{"key":"atypb2","first-page":"596","author":"Azar P.","year":"2013","journal-title":"Philadelphia"},{"key":"atypb3","first-page":"432","author":"Baigneres T.","year":"2004","journal-title":"Berlin"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.08.002"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.2202\/1534-5963.1059"},{"key":"atypb6","first-page":"180","volume":"86","author":"Bulow J.","year":"1996","journal-title":"Adv. Theor. Econ."},{"key":"atypb7","first-page":"711","author":"Chawla S.","year":"2014","journal-title":"New York"},{"key":"atypb8","first-page":"34","author":"Chiesa A.","year":"2012","journal-title":"New York"},{"key":"atypb9","first-page":"243","author":"Cole R.","year":"2014","journal-title":"New York"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.2307\/1911240"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.03.011"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"C. Dwork, G. N. Rothblum, and S. Vadhan,\n                      Boosting and differential privacy\n                      , in 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS, IEEE Computer Society, Los Alamitos, CA, 2010, pp. 51-60.","DOI":"10.1109\/FOCS.2010.12"},{"key":"atypb13","first-page":"23","author":"Fu H.","year":"2014","journal-title":"New York"},{"key":"atypb14","first-page":"323","author":"Fu H.","year":"2015","journal-title":"New York"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2006.02.003"},{"key":"atypb17","first-page":"189","author":"Hartline J. D.","year":"2008","journal-title":"NY"},{"key":"atypb18","unstructured":"J. D. Hartline and T. Roughgarden,\n                      Optimal Platform Design\n                      , preprint, arXiv:1412.8518, 2014."},{"key":"atypb19","first-page":"45","author":"Huang Z.","year":"2015","journal-title":"New York"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(03)00005-8"},{"key":"atypb21","first-page":"59","author":"Ostrovsky M.","year":"2011","journal-title":"New York"},{"key":"atypb22","unstructured":"M. S. Pinsker,\n                      Information and Information Stability of Random Variables and Processes\n                      , Holden-Day, San Francisco, 1964."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1257\/000282803322156963"},{"key":"atypb24","first-page":"422","author":"Sivan B.","year":"2013","journal-title":"Berlin"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1065719","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:41:13Z","timestamp":1787337673000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1065719"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1065719"],"URL":"https:\/\/doi.org\/10.1137\/16m1065719","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}