{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:19Z","timestamp":1759638019886,"version":"3.37.3"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,12,4]],"date-time":"2019-12-04T00:00:00Z","timestamp":1575417600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,4]],"date-time":"2019-12-04T00:00:00Z","timestamp":1575417600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s10458-019-09435-9","type":"journal-article","created":{"date-parts":[[2019,12,4]],"date-time":"2019-12-04T16:03:12Z","timestamp":1575475392000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Truthfulness on a budget: trading money for approximation through monitoring"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5366-3153","authenticated-orcid":false,"given":"Paolo","family":"Serafino","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carmine","family":"Ventre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelina","family":"Vidali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,4]]},"reference":[{"key":"9435_CR1","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.1100.0457","volume":"3","author":"N Alon","year":"2010","unstructured":"Alon, N., Feldman, M., Procaccia, A. D., & Tennenholtz, M. (2010). Strategyproof approximation of the minimax on networks. Mathematics of Operations Research, 3, 513\u2013526.","journal-title":"Mathematics of Operations Research"},{"doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Birmpas, G., & Markakis, E. (2017) On budget-feasible mechanism design for symmetric submodular objectives. In Proceedings of 13th international conference on Web and internet economics, WINE 2017, Bangalore, India, December 17-20, 2017 (pp. 1\u201315).","key":"9435_CR2","DOI":"10.1007\/978-3-319-71924-5_1"},{"doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Kleer, P., & Sch\u00e4fer, G. (2019) Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online. In Proceedings of the 2019 ACM conference on economics and computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019. (pp. 901\u2013919).","key":"9435_CR3","DOI":"10.1145\/3328526.3329622"},{"unstructured":"Anastasiadis, E., & Deligkas, A. (2018). Heterogeneous facility location games. AAMAS, pp. 623\u2013631.","key":"9435_CR4"},{"issue":"1","key":"9435_CR5","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/s00453-013-9845-5","volume":"72","author":"J Augustine","year":"2015","unstructured":"Augustine, J., Caragiannis, I., Fanelli, A., & Kalaitzis, C. (2015). Enforcing efficient equilibria in network design games via subsidies. Algorithmica, 72(1), 44\u201382.","journal-title":"Algorithmica"},{"issue":"2","key":"9435_CR6","first-page":"7","volume":"4","author":"M Babaioff","year":"2016","unstructured":"Babaioff, M., Feldman, M., & Tennenholtz, M. (2016). Mechanism design with strategic mediators. ACM Transations on Economics and Computation, 4(2), 7.","journal-title":"ACM Transations on Economics and Computation"},{"issue":"4","key":"9435_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. (2017). Worst-case mechanism design via bayesian analysis. SIAM Journal on Computing, 46(4), 1428\u20131448.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Buchbinder,N., Lewin-Eytan, L., Naor, J., & Orda, A. (2008) Non-cooperative cost sharing games via subsidies. In B. Monien and U.-P. Schroeder (Eds.), Algorithmic Game Theory (pp. 337\u2013349). Berlin: Springer.","key":"9435_CR8","DOI":"10.1007\/978-3-540-79309-0_30"},{"key":"9435_CR9","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.tcs.2014.10.019","volume":"562","author":"G Calinescu","year":"2015","unstructured":"Calinescu, G. (2015). Bounding the payment of approximate truthful mechanisms. Theoretical Computer Science, 562, 419\u2013435.","journal-title":"Theoretical Computer Science"},{"key":"9435_CR10","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.artint.2017.03.001","volume":"248","author":"I Caragiannis","year":"2017","unstructured":"Caragiannis, I., Chatzigeorgiou, X., Kanellopoulos, P., Krimpas, G. A., Protopapas, N., & Voudouris, A. A. (2017). Efficiency and complexity of price competition among single-product vendors. Artificial Intelligence, 248, 9\u201325.","journal-title":"Artificial Intelligence"},{"doi-asserted-by":"crossref","unstructured":"Caragiannis, I., & Voudouris, A. A. (2018) The efficiency of resource allocation mechanisms for budget-constrained users. In Proceedings of the 2018 ACM conference on economics and computation, Ithaca, NY, USA, June 18-22, 2018 (pp. 681\u2013698).","key":"9435_CR11","DOI":"10.1145\/3219166.3219186"},{"doi-asserted-by":"crossref","unstructured":"Chen, N., Elkind, E., Gravin, N., & Petrov, F. (2010) Frugal mechanism design via spectral techniques. In Proceedings of the 2010 IEEE 51st annual symposium on foundations of computer science, FOCS \u201910 (pp. 755\u2013764). Washington: IEEE Computer Society.","key":"9435_CR12","DOI":"10.1109\/FOCS.2010.77"},{"doi-asserted-by":"crossref","unstructured":"Cheng, Y., Gravin, N., Munagala, K., & Wang, K., (2018) A simple mechanism for a budget-constrained buyer. In Proceedings of 14th international conference on web and internet economics, WINE 2018, Oxford, UK, December 15-17, 2018 (pp. 96\u2013110).","key":"9435_CR13","DOI":"10.1007\/978-3-030-04612-5_7"},{"doi-asserted-by":"crossref","unstructured":"Cheng, Y., Yu, W., & Zhang, G. (2011) Mechanisms for obnoxious facility game on a path (pp. 262\u2013271). Berlin: Springer.","key":"9435_CR14","DOI":"10.1007\/978-3-642-22616-8_21"},{"key":"9435_CR15","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.tcs.2011.11.041","volume":"497","author":"Y Cheng","year":"2013","unstructured":"Cheng, Y., Yu, W., & Zhang, G. (2013). Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Computer Science, 497, 154\u2013163. Combinatorial Algorithms and Applications.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Papadimitriou, C. H., & Singer, Y. (2011) Mechanisms for complement-free procurement. In Proceedings of the 12th ACM conference on electronic commerce, EC \u201911 (pp. 273\u2013282). New York: ACM.","key":"9435_CR16","DOI":"10.1145\/1993574.1993615"},{"doi-asserted-by":"crossref","unstructured":"Dokow, E., Feldman, M., Meir, R., & Nehama, I. (2012). Mechanism design on discrete lines and cycles. ACM EC, pp. 423\u2013440.","key":"9435_CR17","DOI":"10.1145\/2229012.2229045"},{"doi-asserted-by":"crossref","unstructured":"Elkind, E., Goldberg, L. A., & Goldberg, P. W. (2007) Frugality ratios and improved truthful mechanisms for vertex cover. In Proceedings of the 8th ACM conference on electronic commerce, EC \u201907 (pp. 336\u2013345). New York: ACM.","key":"9435_CR18","DOI":"10.1145\/1250910.1250959"},{"unstructured":"Elkind, E., Sahai, A., & Steiglitz, K. (2004). Frugality in path auctions. SODA, pp. 701\u2013709.","key":"9435_CR19"},{"unstructured":"Ferraioli, D., Serafino, P., & Ventre, C. (2016) What to verify for optimal truthful mechanisms without money. In Proceedings of the 2016 international conference on autonomous agents & multiagent systems, Singapore, May 9-13, 2016, pp. 68\u201376.","key":"9435_CR20"},{"unstructured":"Fotakis, D., Krysta, P., & Ventre, C. Equal-cost mechanism design with monitoring. Submitted.","key":"9435_CR21"},{"doi-asserted-by":"crossref","unstructured":"Fotakis, D., & Tzamos, C. (2013) On the power of deterministic mechanisms for facility location games. In Proceedings of 40th international colloquium automata, languages, and programming, ICALP 2013, Riga, Latvia, July 8\u201312, 2013, Part I (pp. 449\u2013460).","key":"9435_CR22","DOI":"10.1007\/978-3-642-39206-1_38"},{"doi-asserted-by":"crossref","unstructured":"Giannakopoulos, Y., Koutsoupias, E., & Kyropoulou, M. (2016). The anarchy of scheduling without money. SAGT (pp. 302\u2013314).","key":"9435_CR23","DOI":"10.1007\/978-3-662-53354-3_24"},{"unstructured":"Golomb, I., & Tzamos, C., (2017) Truthful facility location with additive errors. CoRR, arXiv:1701.00529.","key":"9435_CR24"},{"doi-asserted-by":"crossref","unstructured":"Gravin, N., Jin, Y., Lu, P., & Zhang, C. (2019) Optimal budget-feasible mechanisms for additive valuations. In Proceedings of the 2019 ACM conference on economics and computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019 (pp. 887\u2013900).","key":"9435_CR25","DOI":"10.1145\/3328526.3329586"},{"doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Khani, M. R., & Seddighin, S. (2018) Frugal auction design for set systems: Vertex cover and knapsack. In Proceedings of the 2018 ACM conference on economics and computation, EC \u201918, (pp. 645\u2013662.) New York: ACM.","key":"9435_CR26","DOI":"10.1145\/3219166.3219229"},{"doi-asserted-by":"crossref","unstructured":"Ibara, K., & Nagamochi, H. (2012) Characterizing mechanisms in obnoxious facility game. In Proceedings of 6th international conference on combinatorial optimization and applications, COCOA 2012, Banff, AB, Canada, August 5-9, 2012 (pp. 301\u2013311).","key":"9435_CR27","DOI":"10.1007\/978-3-642-31770-5_27"},{"unstructured":"Karlin, A. R., Kempe, D., & Tamir, T. (2005) Beyond VCG: frugality of truthful mechanisms. In Proceedings of 46th annual IEEE symposium on foundations of computer science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA (pp. 615\u2013626).","key":"9435_CR28"},{"doi-asserted-by":"crossref","unstructured":"Kempe, D., Salek, M., & Moore, C. (2010) Frugal and truthful auctions for vertex covers, flows and cuts. In Proceedings of the 2010 IEEE 51st annual symposium on foundations of computer science, FOCS \u201910 (pp. 745\u2013754), Washington: IEEE Computer Society.","key":"9435_CR29","DOI":"10.1109\/FOCS.2010.76"},{"doi-asserted-by":"crossref","unstructured":"Khalilabadi, P. J., & Tardos, \u00c9. (2018) Simple and efficient budget feasible mechanisms for monotone submodular valuations. In Proceedings of 14th international conference web and internet economics, WINE 2018, Oxford, UK, December 15-17, 2018 (pp. 246\u2013263).","key":"9435_CR30","DOI":"10.1007\/978-3-030-04612-5_17"},{"key":"9435_CR31","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.jet.2012.09.012","volume":"148","author":"N Kos","year":"2012","unstructured":"Kos, N., & Messner, M. (2012). Extremal incentive compatible transfers. Journal of Economic Theory, 148, 134\u2013164.","journal-title":"Journal of Economic Theory"},{"doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., (2011) Scheduling without payments. In Proceedings of SAGT, volume 6982 of LNCS (pp. 143\u2013153).","key":"9435_CR32","DOI":"10.1007\/978-3-642-24829-0_14"},{"doi-asserted-by":"crossref","unstructured":"Kov\u00e1cs, A., Meyer, U., & Ventre, C. (2015) Mechanisms with monitoring for truthful RAM allocation. In WINE, volume 9470 of Lecture notes in computer science (pp. 398\u2013412). Springer.","key":"9435_CR33","DOI":"10.1007\/978-3-662-48995-6_29"},{"doi-asserted-by":"crossref","unstructured":"Kyropoulou, M., Ventre, C., & Zhang, X. (2019) Mechanism design for constrained heterogeneous facility location. In SAGT 2019 (in press).","key":"9435_CR34","DOI":"10.1007\/978-3-030-30473-7_5"},{"doi-asserted-by":"crossref","unstructured":"Lu, P., Sun, X., Wang, Y., & Zhu, Z. A. (2010). Asymptotically optimal strategy-proof mechanisms for two-facility games. ACM EC, pp. 315\u2013324.","key":"9435_CR35","DOI":"10.1145\/1807342.1807393"},{"doi-asserted-by":"crossref","unstructured":"Lu, P., Wang, Y., & Zhou, Y. (2009). Tighter bounds for facility games. WINE, pp. 137\u2013148.","key":"9435_CR36","DOI":"10.1007\/978-3-642-10841-9_14"},{"key":"9435_CR37","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.artint.2012.03.008","volume":"186","author":"R Meir","year":"2012","unstructured":"Meir, R., Procaccia, A. D., & Rosenschein, J. S. (2012). Algorithms for strategyproof classification. Artificial Intelligence, 186, 123\u2013156.","journal-title":"Artificial Intelligence"},{"key":"9435_CR38","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/BF00128122","volume":"35","author":"H Moulin","year":"1980","unstructured":"Moulin, H. (1980). On strategy-proofness and single-peakedness. Public Choice, 35, 437\u2013455.","journal-title":"Public Choice"},{"key":"9435_CR39","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/game.1999.0790","volume":"35","author":"N Nisan","year":"2001","unstructured":"Nisan, N., & Ronen, A. (2001). Algorithmic mechanism design. Games and Economic Behavior, 35, 166\u2013196.","journal-title":"Games and Economic Behavior"},{"volume-title":"Algorithmic game theory","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. V. (Eds.). (2007). Algorithmic game theory. New York: Cambridge University Press.","key":"9435_CR40"},{"key":"9435_CR41","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/j.geb.2012.09.002","volume":"86","author":"P Penna","year":"2014","unstructured":"Penna, P., & Ventre, C. (2014). Optimal collusion-resistant mechanisms with verification. Games and Economic Behavior, 86, 491\u2013509.","journal-title":"Games and Economic Behavior"},{"issue":"4","key":"9435_CR42","first-page":"18","volume":"1","author":"AD Procaccia","year":"2013","unstructured":"Procaccia, A. D., & Tennenholtz, M. (2013). Approximate mechanism design without money. ACM Transations on Economics and Computation, 1(4), 18.","journal-title":"ACM Transations on Economics and Computation"},{"key":"9435_CR43","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1006\/jeth.2001.2807","volume":"104","author":"J Schummer","year":"2002","unstructured":"Schummer, J., & Vohra, R. V. (2002). Strategy-proof location on a network. Journal of Economic Theory, 104, 405\u2013428.","journal-title":"Journal of Economic Theory"},{"unstructured":"Serafino, P., & Ventre, C. (2014). Heterogeneous facility location without money on the line. ECAI - Including PAIS (pp. 807\u2013812).","key":"9435_CR44"},{"doi-asserted-by":"crossref","unstructured":"Serafino, P., & Ventre, C. (2015). Truthful mechanisms without money for non-utilitarian heterogeneous facility location. AAAI (pp. 1029\u20131035).","key":"9435_CR45","DOI":"10.1609\/aaai.v29i1.9307"},{"key":"9435_CR46","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2016.04.033","volume":"636","author":"P Serafino","year":"2016","unstructured":"Serafino, P., & Ventre, C. (2016). Heterogeneous facility location without money. Theoretical Computer Science, 636, 27\u201346.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Singer, Y. (2010). Budget feasible mechanisms. FOCS (pp. 765\u2013774).","key":"9435_CR47","DOI":"10.1109\/FOCS.2010.78"},{"doi-asserted-by":"crossref","unstructured":"Talwar, K. (2003) The price of truth: Frugality in truthful mechanisms. In Proceedings of 20th annual symposium on theoretical aspects of computer science STACS 2003, Berlin, Germany, February 27\u2013March 1, 2003 (pp. 608\u2013619).","key":"9435_CR48","DOI":"10.1007\/3-540-36494-3_53"},{"unstructured":"Zou, S., & Li, M., (2015). Facility location games with dual preference. AAMAS (pp. 615\u2013623).","key":"9435_CR49"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-019-09435-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10458-019-09435-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-019-09435-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,7]],"date-time":"2022-10-07T17:51:21Z","timestamp":1665165081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10458-019-09435-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,4]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["9435"],"URL":"https:\/\/doi.org\/10.1007\/s10458-019-09435-9","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"type":"print","value":"1387-2532"},{"type":"electronic","value":"1573-7454"}],"subject":[],"published":{"date-parts":[[2019,12,4]]},"assertion":[{"value":"4 December 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"5"}}