{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T03:36:58Z","timestamp":1777606618176,"version":"3.51.4"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e0 degli Studi di Roma La Sapienza"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivated by many practical applications, in this paper we study <jats:italic>budget feasible mechanisms<\/jats:italic> with the goal of procuring an independent set of a matroid. More specifically, we are given a matroid <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {M}}=(E,{\\mathcal {I}})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>M<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>I<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Each element of the ground set <jats:italic>E<\/jats:italic> is controlled by a selfish agent and the cost of the element is private information of the agent itself. A budget limited buyer has additive valuations over the elements of <jats:italic>E<\/jats:italic>. The goal is to design an incentive compatible budget feasible mechanism which procures an independent set of the matroid of largest possible value. We also consider the more general case of the pair <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {M}}=(E,{\\mathcal {I}})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>M<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>I<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> satisfying only the hereditary property. This includes matroids as well as matroid intersection. We show that, given a polynomial time deterministic algorithm that returns an <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b1<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation to the problem of finding a maximum-value independent set in <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {M}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>M<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, there exists an individually rational, truthful and budget feasible mechanism which is <jats:inline-formula><jats:alternatives><jats:tex-math>$$(3\\alpha +1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:mi>\u03b1<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximated and runs in polynomial time, thus yielding also a 4-approximation for the special case of matroids.<\/jats:p>","DOI":"10.1007\/s00453-020-00781-9","type":"journal-article","created":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T13:03:34Z","timestamp":1605272614000},"page":"1222-1237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Budget Feasible Mechanisms on Matroids"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9809-7191","authenticated-orcid":false,"given":"Stefano","family":"Leonardi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianpiero","family":"Monaco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiang","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"781_CR1","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Birmpas, G., Markakis, E.: Coverage, matching, and beyond: new results on budgeted mechanism design. In: Proceedings of the 12th International Conference on Web and Internet Economics (WINE), pp 414\u2013428 (2016)","DOI":"10.1007\/978-3-662-54110-4_29"},{"key":"781_CR2","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Birmpas, G., Markakis, E.: On budget-feasible mechanism design for symmetric submodular objectives. In: Proceedings of the 13th International Conference on Web and Internet Economics (WINE), pp 1\u201315 (2017)","DOI":"10.1007\/978-3-319-71924-5_1"},{"key":"781_CR3","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 twentieth ACM conference on Economics and Computation (EC), pp 901\u2013919 (2019)","DOI":"10.1145\/3328526.3329622"},{"key":"781_CR4","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: 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp 266\u2013275 (2014)","DOI":"10.1109\/FOCS.2014.36"},{"key":"781_CR5","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.1257\/0002828043052330","volume":"94","author":"LM Ausubel","year":"2004","unstructured":"Ausubel, L.M.: An efficient ascending-bid auction for multiple objects. Am. Econ. Rev. 94, 1452\u20131475 (2004)","journal-title":"Am. Econ. Rev."},{"key":"781_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 Forty-fourth Annual ACM Symposium on Theory of Computing (STOC), pp 449\u2013458 (2012)","DOI":"10.1145\/2213977.2214020"},{"issue":"2","key":"781_CR7","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1287\/opre.1100.0888","volume":"59","author":"S Bikhchandani","year":"2011","unstructured":"Bikhchandani, S., de Vries, S., Schummer, J., Vohra, R.V.: An ascending Vickrey auction for selling bases of a matroid. Oper. Res. 59(2), 400\u2013413 (2011)","journal-title":"Oper. Res."},{"key":"781_CR8","doi-asserted-by":"crossref","unstructured":"Chan, H., Chen, J.: Truthful multi-unit procurements with budgets. In: The proceedings of the 10th International Conference on Web and Internet Economics (WINE), pp 89\u2013105 (2014)","DOI":"10.1007\/978-3-319-13129-0_7"},{"key":"781_CR9","doi-asserted-by":"crossref","unstructured":"Chen, Ning., Gravin, Nick., Lu, Pinyan.: On the approximability of budget feasible mechanisms. In: Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 685\u2013699 (2011)","DOI":"10.1137\/1.9781611973082.54"},{"issue":"1","key":"781_CR10","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01726210","volume":"11","author":"EH Clarke","year":"1971","unstructured":"Clarke, E.H.: Multipart pricing of public goods. Public Choice 11(1), 17\u201333 (1971)","journal-title":"Public Choice"},{"key":"781_CR11","doi-asserted-by":"publisher","first-page":"863","DOI":"10.1086\/261411","volume":"94","author":"G Demange","year":"1986","unstructured":"Demange, G., Gale, D., Sotomayor, M.: Multi-item auctions. J. Polit. Econ. 94, 863\u2013872 (1986)","journal-title":"J. Polit. Econ."},{"issue":"3","key":"781_CR12","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/2757277","volume":"62","author":"G Goel","year":"2015","unstructured":"Goel, G., Mirrokni, V., Leme, R.P.: Polyhedral clinching auctions and the adwords polytope. J. ACM (JACM) 62(3), 18 (2015)","journal-title":"J. ACM (JACM)"},{"key":"781_CR13","doi-asserted-by":"crossref","unstructured":"Goel, G., Nikzad, A., Singla, A.: Allocating tasks to workers with matching constraints: truthful mechanisms for crowdsourcing markets. In: Proceedings of the Companion Publication of the 23rd International Conference on World Wide Web Companion, pp 279\u2013280 (2014)","DOI":"10.1145\/2567948.2577311"},{"key":"781_CR14","doi-asserted-by":"crossref","unstructured":"Gravin, N., Jin, Y., Lu, P., Zhang, C.: Optimal budget-feasible mechanisms for additive valuations. In: Proceedings of the 2019 ACM Conference on Economics and Computation, EC \u201919, pp 887\u2013900, New York, NY, USA, Association for Computing Machinery (2019)","DOI":"10.1145\/3328526.3329586"},{"key":"781_CR15","first-page":"617","volume":"41","author":"T Groves","year":"1973","unstructured":"Groves, T.: Incentives in teams. Econom. J. Econom. Soc. 41, 617\u2013631 (1973)","journal-title":"Econom. J. Econom. Soc."},{"key":"781_CR16","unstructured":"Karlin, A.R., Kempe, D.: Beyond VCG: frugality of truthful mechanisms. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp 615\u2013624. IEEE, (2005)"},{"key":"781_CR17","unstructured":"Khalilabadi, P.J., Tardos, \u00c9.: Simple and efficient budget feasible mechanisms for monotone submodular valuations. In: Proceedings of Web and Internet Economics\u201414th International Conference, WINE 2018, Oxford, UK, December 15\u201317, 2018, pp 246\u2013263 (2018)"},{"key":"781_CR18","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities. In: Proceedings of the Forty-fourth annual ACM symposium on Theory of computing, pp 123\u2013136. ACM, (2012)","DOI":"10.1145\/2213977.2213991"},{"key":"781_CR19","unstructured":"Krysta, P., Zhang, J.: House markets with matroid and knapsack constraints. In: Proceedings of The 43rd International Colloquium on Automata, Languages and Programming (ICALP) (2016)"},{"key":"781_CR20","doi-asserted-by":"crossref","unstructured":"Leonardi, S., Monaco, G., Sankowski, P., Zhang, Q.: Budget feasible mechanisms on matroids. In: Proceedings of the 19th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp 368\u2013379 (2017)","DOI":"10.1007\/978-3-319-59250-3_30"},{"issue":"1","key":"781_CR21","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1287\/moor.6.1.58","volume":"6","author":"RB Myerson","year":"1981","unstructured":"Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58\u201373 (1981)","journal-title":"Math. Oper. Res."},{"key":"781_CR22","volume-title":"Combinatorial Optimization. Algorithms and Combinatorics","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)"},{"key":"781_CR23","doi-asserted-by":"crossref","unstructured":"Singer, Y.: Budget feasible mechanisms. In: 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp 765\u2013774 (2010)","DOI":"10.1109\/FOCS.2010.78"},{"issue":"7","key":"781_CR24","doi-asserted-by":"publisher","first-page":"2796","DOI":"10.1109\/18.737513","volume":"44","author":"DNC Tse","year":"1998","unstructured":"Tse, D.N.C., Hanly, S.V.: Multiaccess fading channels. I. Polymatroid structure, optimal resource allocation and throughput capacities. IEEE Trans. Inf. Theory 44(7), 2796\u20132815 (1998)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"781_CR25","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W Vickrey","year":"1961","unstructured":"Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1), 8\u201337 (1961)","journal-title":"J. Finance"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00781-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00781-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00781-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T10:18:16Z","timestamp":1617877096000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00781-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["781"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00781-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"23 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}