{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T00:08:31Z","timestamp":1778458111296,"version":"3.51.4"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032186591","type":"print"},{"value":"9783032186607","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-18660-7_2","type":"book-chapter","created":{"date-parts":[[2026,5,10]],"date-time":"2026-05-10T23:21:24Z","timestamp":1778455284000},"page":"21-38","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved Budget-Feasible Mechanisms for\u00a0Submodular Valuations: Beating 4 Deterministically in\u00a0Linear Time"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6302-5366","authenticated-orcid":false,"given":"Kai","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-0569-4122","authenticated-orcid":false,"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,1]]},"reference":[{"issue":"3","key":"2_CR1","doi-asserted-by":"publisher","first-page":"2286","DOI":"10.1287\/moor.2021.1208","volume":"47","author":"G Amanatidis","year":"2022","unstructured":"Amanatidis, G., Kleer, P., Sch\u00e4fer, G.: Budget-feasible mechanism design for non-monotone submodular objectives: offline and online. Math. Oper. Res. 47(3), 2286\u20132309 (2022)","journal-title":"Math. Oper. Res."},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Kleer, P., Sch\u00e4fer, G.: Budget-feasible mechanism design for non-monotone submodular objectives: offline and online. In: Proceedings of the 20th ACM Conference on Economics and Computation (EC). pp. 901\u2013919 (2019)","DOI":"10.1145\/3328526.3329622"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Anari, N., Goel, G., Nikzad, A.: Mechanism design for crowdsourcing: an optimal 1-1\/e competitive budget-feasible mechanism for large markets. In: Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS). pp. 266\u2013275 (2014)","DOI":"10.1109\/FOCS.2014.36"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Balkanski, E., Garimidi, P., Gkatzelis, V., Schoepflin, D., Tan, X.: Deterministic budget-feasible clock auctions. In: Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 2940\u20132963 (2022)","DOI":"10.1137\/1.9781611977073.114"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Balkanski, E., Garimidi, P., Gkatzelis, V., Schoepflin, D., Tan, X.: Deterministic budget-feasible clock auctions. Operations Research (2025)","DOI":"10.1287\/opre.2023.0526"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Bei, X., Chen, N., Gravin, N., Lu, P.: Budget feasible mechanism design: from prior-free to bayesian. In: Proceedings of the 44th ACM Symposium on Theory of Computing (STOC). pp. 449\u2013458 (2012)","DOI":"10.1145\/2213977.2214020"},{"issue":"4","key":"2_CR7","doi-asserted-by":"publisher","first-page":"1428","DOI":"10.1137\/16M1067275","volume":"46","author":"X Bei","year":"2017","unstructured":"Bei, X., Chen, N., Gravin, N., Lu, P.: Worst-case mechanism design via Bayesian analysis. SIAM J. Comput. 46(4), 1428\u20131448 (2017)","journal-title":"SIAM J. Comput."},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 1433\u20131452 (2014)","DOI":"10.1137\/1.9781611973402.106"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Chen, N., Gravin, N., Lu, P.: On the approximability of budget feasible mechanisms. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 685\u2013699 (2011)","DOI":"10.1137\/1.9781611973082.54"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Dandekar, P., Fawaz, N., Ioannidis, S.: Privacy auctions for recommender systems. ACM Trans. Econ. Comput. 2(3), 12:1\u201312:22 (2014)","DOI":"10.1145\/2629665"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Papadimitriou, C.H., Singer, Y.: Mechanisms for complement-free procurement. In: Proceedings of the 12th ACM Conference on Electronic Commerce (EC). pp. 273\u2013282 (2011)","DOI":"10.1145\/1993574.1993615"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Goel, G., Nikzad, A., Singla, A.: Mechanism design for crowdsourcing markets with heterogeneous tasks. In: Proceedings of the Second AAAI Conference on Human Computation and Crowdsourcing (HCOMP). pp. 77\u201386 (2014)","DOI":"10.1609\/hcomp.v2i1.13158"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Gravin, N., Jin, Y., Lu, P., Zhang, C.: Optimal budget-feasible mechanisms for additive valuations. ACM Trans. Econ. Comput. 8(4), 21:1\u201321:15 (2020)","DOI":"10.1145\/3417746"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Han, K., Wu, Y., Huang, H., Cui, S.: Triple eagle: Simple, fast and practical budget-feasible mechanisms. In: Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS). vol.\u00a036, pp. 33894\u201333911 (2023)","DOI":"10.52202\/075280-1470"},{"key":"2_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2025.104348","volume":"345","author":"K Han","year":"2025","unstructured":"Han, K., Zhang, H., Cui, S.: Efficient and effective budget-feasible mechanisms for submodular valuations. Artif. Intell. 345, 104348 (2025)","journal-title":"Artif. Intell."},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Huang, H., Han, K., Cui, S., Tang, J.: Randomized pricing with deferred acceptance for revenue maximization with submodular objectives. In: Proceedings of the 2023 ACM Web Conference (WWW). pp. 3530\u20133540 (2023)","DOI":"10.1145\/3543507.3583477"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Jalaly, P., Tardos, \u00c9.: Simple and efficient budget feasible mechanisms for monotone submodular valuations. In: Proceedings of the 14th International Conference on Web and Internet Economics (WINE). pp. 246\u2013263 (2018)","DOI":"10.1007\/978-3-030-04612-5_17"},{"issue":"1","key":"2_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3434421","volume":"9","author":"P Jalaly","year":"2021","unstructured":"Jalaly, P., Tardos, \u00c9.: Simple and efficient budget feasible mechanisms for monotone submodular valuations. ACM Trans. Econ. Comput. (TEAC) 9(1), 1\u201320 (2021)","journal-title":"ACM Trans. Econ. Comput. (TEAC)"},{"issue":"4","key":"2_CR19","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1287\/moor.2013.0592","volume":"38","author":"A Kulik","year":"2013","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Math. Oper. Res. 38(4), 729\u2013739 (2013)","journal-title":"Math. Oper. Res."},{"key":"2_CR20","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103975","volume":"323","author":"X Liu","year":"2023","unstructured":"Liu, X., Chan, H., Li, M., Wu, W., Zhao, Y.: Budget-feasible mechanisms for proportionally selecting agents from groups. Artif. Intell. 323, 103975 (2023)","journal-title":"Artif. Intell."},{"key":"2_CR21","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103538","volume":"299","author":"Y Luo","year":"2021","unstructured":"Luo, Y., Jennings, N.R.: A budget-limited mechanism for category-aware crowdsourcing of multiple-choice tasks. Artif. Intell. 299, 103538 (2021)","journal-title":"Artif. Intell."},{"issue":"1","key":"2_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1086\/704074","volume":"128","author":"P Milgrom","year":"2020","unstructured":"Milgrom, P., Segal, I.: Clock auctions and radio spectrum reallocation. J. Polit. Econ. 128(1), 1\u201331 (2020)","journal-title":"J. Polit. Econ."},{"key":"2_CR23","unstructured":"Neogi, R., Pashkovich, K., Swamy, C.: Budget-feasible mechanism design: Simpler, better mechanisms and general payment constraints. In: Proceedings of the 15th Innovations in Theoretical Computer Science Conference (ITCS). vol.\u00a0287, pp. 84:1\u201384:22 (2024)"},{"key":"2_CR24","unstructured":"Neogi, R., Pashkovich, K., Swamy, C.: An O(log log n)-approximate budget feasible mechanism for subadditive valuations. In: Proceedings of the 26th ACM Conference on Economics and Computation (EC) (2025)"},{"key":"2_CR25","unstructured":"Rubinstein, A., Zhao, J.: Beyond worst-case budget-feasible mechanism design. In: Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS). pp. 93:1\u201393:22 (2023)"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"Singer, Y.: Budget feasible mechanisms. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS). pp. 765\u2013774 (2010)","DOI":"10.1109\/FOCS.2010.78"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Singer, Y.: How to win friends and influence people, truthfully: influence maximization mechanisms for social networks. In: Proceedings of the 5th ACM International Conference on Web Search and Data Mining (WSDM). pp. 733\u2013742 (2012)","DOI":"10.1145\/2124295.2124381"},{"key":"2_CR28","doi-asserted-by":"crossref","unstructured":"Singer, Y., Mittal, M.: Pricing mechanisms for crowdsourcing markets. In: Proceedings of the 22nd International Conference on World Wide Web (WWW). pp. 1157\u20131166 (2013)","DOI":"10.1145\/2488388.2488489"},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"Zhang, J., Wu, Y., Pan, R.: Incentive mechanism for horizontal federated learning based on reputation and reverse auction. In: Proceedings of the 2021 ACM Web Conference (WWW). pp. 947\u2013956 (2021)","DOI":"10.1145\/3442381.3449888"}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-18660-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,10]],"date-time":"2026-05-10T23:21:27Z","timestamp":1778455287000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-18660-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032186591","9783032186607"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-18660-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"1 May 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WINE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Web and Internet Economics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"New Brunswick, NJ","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 December 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 December 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wine2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/wine2025.cs.rutgers.edu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}