{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T06:19:14Z","timestamp":1782368354449,"version":"3.54.5"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T00:00:00Z","timestamp":1404172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0728839"],"award-info":[{"award-number":["CCF-0728839"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0720528"],"award-info":[{"award-number":["CNS-0720528"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0626636"],"award-info":[{"award-number":["CNS-0626636"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0426683"],"award-info":[{"award-number":["CNS-0426683"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS 1010789"],"award-info":[{"award-number":["CNS 1010789"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2014,7]]},"abstract":"<jats:p>In the context of auctions for digital goods, an interesting random sampling auction has been proposed by Goldberg et al. [2001]. This auction has been analyzed by Feige et al. [2005], who have shown that it obtains in expectation at least 1\/15 fraction of the optimal revenue, which is substantially better than the previously proven constant bounds but still far from the conjectured lower bound of 1\/4. In this article, we prove that the aforementioned random sampling auction obtains at least 1\/4 fraction of the optimal revenue for a large class of instances where the number of bids above (or equal to) the optimal sale price is at least 6. We also show that this auction obtains at least 1\/4.68 fraction of the optimal revenue for the small class of remaining instances, thus leaving a negligible gap between the lower and upper bound. We employ a mix of probabilistic techniques and dynamic programming to compute these bounds.<\/jats:p>","DOI":"10.1145\/2517148","type":"journal-article","created":{"date-parts":[[2014,7,29]],"date-time":"2014-07-29T12:28:17Z","timestamp":1406636897000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["On Random Sampling Auctions for Digital Goods"],"prefix":"10.1145","volume":"2","author":[{"given":"Saeed","family":"Alaei","sequence":"first","affiliation":[{"name":"University of Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Azarakhsh","family":"Malekian","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.50"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2202\/1534-5963.1059"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566381"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11600930_89"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651330"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 9th Annual European Symposium on Algorithms (ESA\u201901)","author":"Andrew","unstructured":"Andrew V. Goldberg and Jason D. Hartline. 2001. Competitive auctions for multiple digital goods . In Proceedings of the 9th Annual European Symposium on Algorithms (ESA\u201901) . Springer, 416--427. Andrew V. Goldberg and Jason D. Hartline. 2001. Competitive auctions for multiple digital goods. In Proceedings of the 9th Annual European Symposium on Algorithms (ESA\u201901). Springer, 416--427."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2006.02.003"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901)","author":"Goldberg Andrew V.","year":"2001","unstructured":"Andrew V. Goldberg , Jason D. Hartline , and Andrew Wright . 2001 . Competitive auctions and digital goods . In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901) . SIAM, Philadelphia, PA, 735--744. Andrew V. Goldberg, Jason D. Hartline, and Andrew Wright. 2001. Competitive auctions and digital goods. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901). SIAM, Philadelphia, PA, 735--744."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988784"},{"key":"e_1_2_1_10_1","volume-title":"Hartline and Tim Roughgarden","author":"Jason","year":"2008","unstructured":"Jason D. Hartline and Tim Roughgarden . 2008 . Optimal mechansim design and money burning. CoRR abs\/0804.2097. Jason D. Hartline and Tim Roughgarden. 2008. Optimal mechansim design and money burning. CoRR abs\/0804.2097."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1257\/000282803322156963"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2517148","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2517148","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:40Z","timestamp":1750231720000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2517148"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["10.1145\/2517148"],"URL":"https:\/\/doi.org\/10.1145\/2517148","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}