{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:50:09Z","timestamp":1757544609674,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,10,16]],"date-time":"2020-10-16T00:00:00Z","timestamp":1602806400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Program for Innovative Research Team of Shanghai University of Finance and Economics"},{"name":"Science and Technology Innovation 2030\u2014\u201cNew Generation of Artificial Intelligence\u201d","award":["2018AAA0100903"],"award-info":[{"award-number":["2018AAA0100903"]}]},{"name":"Innovation Program of Shanghai Municipal Education Commission"},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61922052 and 61932002"],"award-info":[{"award-number":["61922052 and 61932002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2020,11,30]]},"abstract":"<jats:p>In this article, we show a tight approximation guarantee for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with approximation ratio of 2, improving the previous best known result of 3. Our bound is tight with respect to either the optimal offline benchmark or its fractional relaxation. We also present a simple deterministic mechanism with the tight approximation guarantee of 3 against the fractional optimum, improving the best known result of (2+ \u221a 2) for the weaker integral benchmark.<\/jats:p>","DOI":"10.1145\/3417746","type":"journal-article","created":{"date-parts":[[2020,10,16]],"date-time":"2020-10-16T22:24:56Z","timestamp":1602887096000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Optimal Budget-Feasible Mechanisms for Additive Valuations"],"prefix":"10.1145","volume":"8","author":[{"given":"Nick","family":"Gravin","sequence":"first","affiliation":[{"name":"Shanghai University of Finance and Economics, Wujiaochang, Yangpu District, Shanghai, China"}]},{"given":"Yaonan","family":"Jin","sequence":"additional","affiliation":[{"name":"Columbia University, New York City, New York"}]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[{"name":"Shanghai University of Finance and Economics, Wujiaochang, Yangpu District, Shanghai, China"}]},{"given":"Chenhao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, Illinois"}]}],"member":"320","published-online":{"date-parts":[[2020,10,16]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, January 22--26","author":"Aggarwal Gagan","year":"2006","unstructured":"Gagan Aggarwal and Jason D. Hartline . 2006. Knapsack auctions . In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, January 22--26 , 2006 , Miami, Florida. ACM Press, 1083--1092. http:\/\/dl.acm.org\/citation.cfm?id=1109557.1109677 Gagan Aggarwal and Jason D. Hartline. 2006. Knapsack auctions. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, January 22--26, 2006, Miami, Florida. ACM Press, 1083--1092. http:\/\/dl.acm.org\/citation.cfm?id=1109557.1109677"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54110-4_29"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71924-5_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.36"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186810.1186813"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229026"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883032"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764505"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1067275"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.77"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.54"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, January 7--9","author":"Chen Ning","year":"2007","unstructured":"Ning Chen and Anna R. Karlin . 2007. Cheap labor can be expensive . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, January 7--9 , 2007 , New Orleans, LA. Nikhil Bansal, Kirk Pruhs, and Clifford Stein (Eds.). SIAM, 707--715. http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283459. Ning Chen and Anna R. Karlin. 2007. Cheap labor can be expensive. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, January 7--9, 2007, New Orleans, LA. Nikhil Bansal, Kirk Pruhs, and Clifford Stein (Eds.). SIAM, 707--715. http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283459."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993615"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings 8th ACM Conference on Electronic Commerce (EC-2007)","author":"Elkind Edith","year":"2007","unstructured":"Edith Elkind , Leslie Ann Goldberg , and Paul W. Goldberg . 2007. Frugality ratios and improved truthful mechanisms for vertex cover . In Proceedings 8th ACM Conference on Electronic Commerce (EC-2007) , June 11 --15 , 2007 , San Diego, CA. Jeffrey K. MacKie-Mason, David C. Parkes, and Paul Resnick (Eds.). ACM, 336--345. DOI:https:\/\/doi.org\/10.1145\/1250910.1250959 10.1145\/1250910.1250959 Edith Elkind, Leslie Ann Goldberg, and Paul W. Goldberg. 2007. Frugality ratios and improved truthful mechanisms for vertex cover. In Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), June 11--15, 2007, San Diego, CA. Jeffrey K. MacKie-Mason, David C. Parkes, and Paul Resnick (Eds.). ACM, 336--345. DOI:https:\/\/doi.org\/10.1145\/1250910.1250959"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, January 11--14","author":"Elkind Edith","year":"2004","unstructured":"Edith Elkind , Amit Sahai , and Kenneth Steiglitz . 2004 . Frugality in path auctions . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, January 11--14 , 2004, New Orleans, LA. J. Ian Munro (Ed.). SIAM, 701--709. http:\/\/dl.acm.org\/citation.cfm?id=982792.982900. Edith Elkind, Amit Sahai, and Kenneth Steiglitz. 2004. Frugality in path auctions. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, January 11--14, 2004, New Orleans, LA. J. Ian Munro (Ed.). SIAM, 701--709. http:\/\/dl.acm.org\/citation.cfm?id=982792.982900."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 2nd AAAI Conference on Human Computation and Crowdsourcing, HCOMP 2014","author":"Goel Gagan","year":"2014","unstructured":"Gagan Goel , Afshin Nikzad , and Adish Singla . 2014 . Mechanism design for crowdsourcing markets with heterogeneous tasks . In Proceedings of the 2nd AAAI Conference on Human Computation and Crowdsourcing, HCOMP 2014 , November 2 --4 , 2014, Pittsburgh, PA. Jeffrey P. Bigham and David C. Parkes (Eds.). AAAI. http:\/\/www.aaai.org\/ocs\/index.php\/HCOMP\/HCOMP14\/paper\/view\/8968. Gagan Goel, Afshin Nikzad, and Adish Singla. 2014. Mechanism design for crowdsourcing markets with heterogeneous tasks. In Proceedings of the 2nd AAAI Conference on Human Computation and Crowdsourcing, HCOMP 2014, November 2--4, 2014, Pittsburgh, PA. Jeffrey P. Bigham and David C. Parkes (Eds.). AAAI. http:\/\/www.aaai.org\/ocs\/index.php\/HCOMP\/HCOMP14\/paper\/view\/8968."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219229"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 11th Latin American Symposium, LATIN 2014, March 31--","volume":"8392","author":"Horel Thibaut","year":"2014","unstructured":"Thibaut Horel , Stratis Ioannidis , and S. Muthukrishnan . 2014. Budget feasible mechanisms for experimental design . In Proceedings of the 11th Latin American Symposium, LATIN 2014, March 31-- April 4, 2014 , Montevideo, Uruguay. Alberto Pardo and Alfredo Viola (Eds.) , Vol. 8392 . Springer, 719--730. DOI:https:\/\/doi.org\/10.1007\/978-3-642-54423-1_62 10.1007\/978-3-642-54423-1_62 Thibaut Horel, Stratis Ioannidis, and S. Muthukrishnan. 2014. Budget feasible mechanisms for experimental design. In Proceedings of the 11th Latin American Symposium, LATIN 2014, March 31-- April 4, 2014, Montevideo, Uruguay. Alberto Pardo and Alfredo Viola (Eds.), Vol. 8392. Springer, 719--730. DOI:https:\/\/doi.org\/10.1007\/978-3-642-54423-1_62"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.25"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.76"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the14th International Conference, WINE 2018","author":"Jalaly Pooya","year":"2018","unstructured":"Pooya Jalaly Khalilabadi and \u00c9va Tardos. 2018. Simple and efficient budget feasible mechanisms for monotone submodular valuations . In Proceedings of the14th International Conference, WINE 2018 , December 15 --17 , 2018 , Oxford, UK, George Christodoulou and Tobias Harks (Eds.), Vol. 11316. Springer, 246--263. DOI:https:\/\/doi.org\/10.1007\/978-3-030-04612-5_17 10.1007\/978-3-030-04612-5_17 Pooya Jalaly Khalilabadi and \u00c9va Tardos. 2018. Simple and efficient budget feasible mechanisms for monotone submodular valuations. In Proceedings of the14th International Conference, WINE 2018, December 15--17, 2018, Oxford, UK, George Christodoulou and Tobias Harks (Eds.), Vol. 11316. Springer, 246--263. DOI:https:\/\/doi.org\/10.1007\/978-3-030-04612-5_17"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_30"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.78"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124381"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488489"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36494-3_53"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417746","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3417746","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:14Z","timestamp":1750197674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417746"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,16]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,11,30]]}},"alternative-id":["10.1145\/3417746"],"URL":"https:\/\/doi.org\/10.1145\/3417746","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2020,10,16]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}