{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:49:35Z","timestamp":1767340175330,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T00:00:00Z","timestamp":1601683200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T00:00:00Z","timestamp":1601683200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M018113\/1"],"award-info":[{"award-number":["EP\/M018113\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009112","name":"Istituto Nazionale di Alta Matematica \u201cFrancesco Severi\u201d","doi-asserted-by":"publisher","award":["Progetti GNCS 2017"],"award-info":[{"award-number":["Progetti GNCS 2017"]}],"id":[{"id":"10.13039\/100009112","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"crossref","award":["PRIN 2017 Project ALGADIMAR"],"award-info":[{"award-number":["PRIN 2017 Project ALGADIMAR"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100007065","name":"Universit\u00e0 degli Studi di Salerno","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007065","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Obvious strategyproofness (OSP) is an appealing concept as it allows to maintain incentive compatibility even in the presence of agents that are not fully rational, i.e., those who struggle with contingent reasoning (Li in Am Econ Rev 107(11):3257\u20133287, 2017). However, it has been shown to impose some limitations, e.g., no OSP mechanism can return a stable matching (Ashlagi and Gonczarowski in J Econ Theory 177:405\u2013425, 2018). We here deepen the study of the limitations of OSP mechanisms by looking at their approximation guarantees for basic optimization problems paradigmatic of the area, i.e., machine scheduling and facility location. We prove a number of bounds on the approximation guarantee of OSP mechanisms, which show that OSP can come at a significant cost. However, rather surprisingly, we prove that OSP mechanisms can return optimal solutions when they use monitoring\u2014a novel mechanism design paradigm that introduces a mild level of scrutiny on agents\u2019 declarations (Kov\u00e1cs et al. in WINE 9470:398\u2013412, 2015).<\/jats:p>","DOI":"10.1007\/s00453-020-00771-x","type":"journal-article","created":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T06:02:31Z","timestamp":1601704951000},"page":"695-725","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximation Guarantee of OSP Mechanisms: The Case of Machine Scheduling and Facility Location"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7962-5200","authenticated-orcid":false,"given":"Diodato","family":"Ferraioli","sequence":"first","affiliation":[]},{"given":"Carmine","family":"Ventre","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,10,3]]},"reference":[{"key":"771_CR1","doi-asserted-by":"crossref","unstructured":"Adamczyk, M., Borodin, A., Ferraioli, D., de Keijzer, B., Leonardi, S.: Sequential posted price mechanisms with correlated valuations. In: WINE 2015, pp. 1\u201315 (2015)","DOI":"10.1007\/978-3-662-48995-6_1"},{"key":"771_CR2","doi-asserted-by":"crossref","unstructured":"Archer, A., Tardos, \u00c9.: Truthful mechanisms for one-parameter agents. In: FOCS 2001, pp. 482\u2013491 (2001)","DOI":"10.1109\/SFCS.2001.959924"},{"key":"771_CR3","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.jet.2018.07.001","volume":"177","author":"I Ashlagi","year":"2018","unstructured":"Ashlagi, I., Gonczarowski, Y.A.: Stable matching mechanisms are not obviously strategy-proof. J. Econ. Theory 177, 405\u2013425 (2018)","journal-title":"J. Econ. Theory"},{"issue":"2","key":"771_CR4","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1287\/moor.1110.0534","volume":"37","author":"I Ashlagi","year":"2012","unstructured":"Ashlagi, I., Dobzinski, S., Lavi, R.: Optimal lower bounds for anonymous scheduling mechanisms. Math. Oper. Res. 37(2), 244\u2013258 (2012)","journal-title":"Math. Oper. Res."},{"key":"771_CR5","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Immorlica, N., Lucier, B., Weinberg, S.M.: A simple and approximately optimal mechanism for an additive buyer. In: FOCS 2014, pp. 21\u201330 (2014)","DOI":"10.1109\/FOCS.2014.11"},{"key":"771_CR6","doi-asserted-by":"crossref","unstructured":"Badem, S., Gonczarowski, Y.A.: Gibbard\u2013Satterthwaite success stories and obvious strategyproofness. In: EC 2017, p. 565 (2017)","DOI":"10.1145\/3033274.3085104"},{"key":"771_CR7","doi-asserted-by":"crossref","unstructured":"Br\u00e2nzei, S., Procaccia, A.D.: Verifiably truthful mechanisms. In: ITCS 2015, pp. 297\u2013306 (2015)","DOI":"10.1145\/2688073.2688098"},{"key":"771_CR8","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Elkind, E., Szegedy, M., Lan, Y.: Mechanism design: from partial to probabilistic verification. In: EC 2012, pp. 266\u2013283 (2012)","DOI":"10.1145\/2229012.2229035"},{"key":"771_CR9","doi-asserted-by":"crossref","unstructured":"Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: STOC 2010, pp. 311\u2013320 (2010)","DOI":"10.1145\/1807406.1807428"},{"issue":"4","key":"771_CR10","doi-asserted-by":"publisher","first-page":"1572","DOI":"10.1137\/120866038","volume":"42","author":"G Christodoulou","year":"2013","unstructured":"Christodoulou, G., Kov\u00e1cs, A.: A deterministic truthful PTAS for scheduling related machines. SIAM J. Comput. 42(4), 1572\u20131595 (2013)","journal-title":"SIAM J. Comput."},{"key":"771_CR11","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Vondr\u00e1k, J.: The computational complexity of truthfulness in combinatorial auctions. In: EC 2012, pp. 405\u2013422 (2012)","DOI":"10.1145\/2229012.2229044"},{"key":"771_CR12","unstructured":"Elkind, E., Sahai, A., Steiglitz, K.: Frugality in path auctions. In: SODA 2004, pp. 701\u2013709 (2004)"},{"key":"771_CR13","doi-asserted-by":"crossref","unstructured":"Ferraioli, D., Ventre, C.: Obvious strategyproofness needs monitoring for good approximations. In: AAAI 2017, pp. 516\u2013522 (2017)","DOI":"10.1609\/aaai.v31i1.10588"},{"key":"771_CR14","doi-asserted-by":"crossref","unstructured":"Ferraioli, D., Ventre, C.: Probabilistic verification for obviously strategyproof mechanisms. In: IJCAI 2018 (2018)","DOI":"10.24963\/ijcai.2018\/33"},{"key":"771_CR15","doi-asserted-by":"crossref","unstructured":"Ferraioli, D., Ventre, C.: Obvious strategyproofness, bounded rationality and approximation: the case of machine scheduling. In: SAGT 2019 (2019)","DOI":"10.1007\/978-3-030-30473-7_6"},{"key":"771_CR16","doi-asserted-by":"crossref","unstructured":"Ferraioli, D., Ventre, C., Aranyi, G.: A mechanism design approach to measure awareness. In: AAAI 2015, pp. 886\u2013892 (2015)","DOI":"10.1609\/aaai.v29i1.9298"},{"key":"771_CR17","unstructured":"Ferraioli, D., Serafino, P., Ventre, C.: What to verify for optimal truthful mechanisms without money. In: AAMAS 2016, pp. 68\u201376 (2016)"},{"key":"771_CR18","unstructured":"Ferraioli, D., Meier, A., Penna, P., Ventre, C.: Obviously strategyproof mechanisms for machine scheduling. In: ESA 2019 (2019)"},{"key":"771_CR19","doi-asserted-by":"crossref","unstructured":"Ferraioli, D., Meier, A., Penna, P., Ventre, C.: Automated optimal OSP mechanisms for set systems\u2014the case of small domains. In: WINE 2019, pp. 171\u2013185 (2019)","DOI":"10.1007\/978-3-030-35389-6_13"},{"issue":"4","key":"771_CR20","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/2665005","volume":"2","author":"D Fotakis","year":"2014","unstructured":"Fotakis, D., Tzamos, C.: On the power of deterministic mechanisms for facility location games. ACM Trans. Econ. Comput. 2(4), 15:1\u201315:37 (2014)","journal-title":"ACM Trans. Econ. Comput."},{"key":"771_CR21","unstructured":"Fotakis, D., Krysta, P., Ventre, C.: Combinatorial auctions without money. In: AAMAS 2014, pp. 1029\u20131036 (2014)"},{"key":"771_CR22","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M.: Approximations of weighted independent set and hereditary subset problems. In: COCOON 1999, pp. 261\u2013270 (1999)","DOI":"10.1007\/3-540-48686-0_26"},{"issue":"3","key":"771_CR23","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"DS Hochbaum","year":"1988","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM J. Comput. 17(3), 539\u2013551 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"771_CR24","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"CAJ Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. 2(1), 68\u201372 (1989)","journal-title":"SIAM J. Discrete Math."},{"key":"771_CR25","unstructured":"Karlin, A.R., Kempe, D.: Beyond vcg: frugality of truthful mechanisms. In: FOCS 2005, pp. 615\u2013624 (2005)"},{"issue":"3","key":"771_CR26","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00224-013-9473-0","volume":"54","author":"E Koutsoupias","year":"2014","unstructured":"Koutsoupias, E.: Scheduling without payments. Theory Comput. Syst. 54(3), 375\u2013387 (2014)","journal-title":"Theory Comput. Syst."},{"key":"771_CR27","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Vidali, A.: A lower bound of $$1+ \\varphi $$ for truthful scheduling mechanisms. In: MFCS 2007, pp. 454\u2013464 (2007)","DOI":"10.1007\/978-3-540-74456-6_41"},{"key":"771_CR28","doi-asserted-by":"crossref","unstructured":"Kov\u00e1cs, A., Meyer, U., Ventre, C.: Mechanisms with monitoring for truthful RAM allocation. In: WINE 2015, pp. 398\u2013412 (2015)","DOI":"10.1007\/978-3-662-48995-6_29"},{"key":"771_CR29","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1613\/jair.4587","volume":"53","author":"P Krysta","year":"2015","unstructured":"Krysta, P., Telelis, O., Ventre, C.: Mechanisms for multi-unit combinatorial auctions with a few distinct goods. J. Artif. Intell. Res. 53, 721\u2013744 (2015)","journal-title":"J. Artif. Intell. Res."},{"key":"771_CR30","unstructured":"Kyropoulou, M., Ventre, C.: Obviously strategyproof mechanisms without money for scheduling. In: AAMAS 2019 (2019)"},{"issue":"5","key":"771_CR31","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1145\/585265.585266","volume":"49","author":"D Lehmann","year":"2002","unstructured":"Lehmann, D., O\u0107allaghan, L.I., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. J. ACM 49(5), 577\u2013602 (2002)","journal-title":"J. ACM"},{"issue":"11","key":"771_CR32","doi-asserted-by":"publisher","first-page":"3257","DOI":"10.1257\/aer.20160425","volume":"107","author":"S Li","year":"2017","unstructured":"Li, S.: Obviously strategy-proof mechanisms. Am. Econ. Rev. 107(11), 3257\u201387 (2017)","journal-title":"Am. Econ. Rev."},{"key":"771_CR33","unstructured":"Mackenzie, A.: A revelation principle for obviously strategy-proof implementation (2017)"},{"key":"771_CR34","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/BF00128122","volume":"35","author":"H Moulin","year":"1980","unstructured":"Moulin, H.: On strategy-proofness and single-peakedness. Public Choice 35, 437\u2013455 (1980)","journal-title":"Public Choice"},{"key":"771_CR35","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.: Algorithmic mechanism design. Games Econ. Behav. 35, 166\u2013196 (2001)","journal-title":"Games Econ. Behav."},{"key":"771_CR36","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.: Optimal collusion-resistant mechanisms with verification. Games Econ. Behav. 86, 491\u2013509 (2014)","journal-title":"Games Econ. Behav."},{"issue":"4","key":"771_CR37","doi-asserted-by":"publisher","first-page":"18:1","DOI":"10.1145\/2542174.2542175","volume":"1","author":"AD Procaccia","year":"2013","unstructured":"Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. ACM Trans. Econ. Comput. 1(4), 18:1\u201318:26 (2013)","journal-title":"ACM Trans. Econ. Comput."},{"key":"771_CR38","doi-asserted-by":"crossref","unstructured":"Pycia, M., Troyan, P.: Obvious dominance and random priority. In: EC 2019 (2019)","DOI":"10.1145\/3328526.3329613"},{"key":"771_CR39","doi-asserted-by":"crossref","unstructured":"Sandholm, T., Gilpin, A.: Sequences of take-it-or-leave-it offers: near-optimal auctions without full valuation revelation. In: AMET 2003, pp. 73\u201391 (2003)","DOI":"10.1007\/978-3-540-25947-3_5"},{"key":"771_CR40","doi-asserted-by":"crossref","unstructured":"Serafino, P., Ventre, C., Vidali, A.: Truthfulness on a budget: trading money for approximation through monitoring. In: AAMAS 2019, pp. 1234\u20131242 (2019)","DOI":"10.1007\/s10458-019-09435-9"},{"key":"771_CR41","doi-asserted-by":"crossref","unstructured":"Talwar, K.: The price of truth: frugality in truthful mechanisms. In: STACS 2003, pp. 608\u2013619 (2003)","DOI":"10.1007\/3-540-36494-3_53"},{"key":"771_CR42","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.tcs.2013.07.034","volume":"518","author":"C Ventre","year":"2014","unstructured":"Ventre, C.: Truthful optimization using mechanisms with verification. Theor. Comput. Sci. 518, 64\u201379 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"771_CR43","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1257\/aer.p20171030","volume":"107","author":"L Zhang","year":"2017","unstructured":"Zhang, L., Levin, D.: Partition obvious preference and mechanism design: theory and experiment. Am. Econ. Rev. 107(5), 235\u201339 (2017)","journal-title":"Am. Econ. Rev."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00771-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00771-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00771-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,22]],"date-time":"2022-11-22T01:22:23Z","timestamp":1669080143000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00771-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,3]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["771"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00771-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,10,3]]},"assertion":[{"value":"28 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}