{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:45:42Z","timestamp":1767339942890,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T00:00:00Z","timestamp":1650844800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T00:00:00Z","timestamp":1650844800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Obvious strategyproofness (OSP) has recently emerged as the solution concept of interest to study incentive compatibility in presence of agents with a specific form of bounded rationality, i.e., those who have <jats:italic>no<\/jats:italic> contingent reasoning skill whatsoever. We here want to study the relationship between the approximation guarantee of incentive-compatible mechanisms and the <jats:italic>degree<\/jats:italic> of rationality of the agents, intuitively measured in terms of the number of contingencies that they can handle in their reasoning. We weaken the definition of OSP to accommodate for cleverer agents and study the trade-off between approximation and agents\u2019 rationality for two paradigmatic problems: machine scheduling and facility location. We prove that, for both problems, \u201cgood\u201d approximations are possible if and only if the agents\u2019 rationality allows for a significant number of contingencies to be considered, thus showing that OSP is not too restrictive a notion of bounded rationality from the point of view of approximation.<\/jats:p>","DOI":"10.1007\/s00224-022-10071-2","type":"journal-article","created":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T05:02:57Z","timestamp":1650862977000},"page":"696-720","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Obvious Strategyproofness, Bounded Rationality and Approximation"],"prefix":"10.1007","volume":"66","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7962-5200","authenticated-orcid":false,"given":"Diodato","family":"Ferraioli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carmine","family":"Ventre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,25]]},"reference":[{"key":"10071_CR1","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":"10071_CR2","doi-asserted-by":"crossref","unstructured":"Ferraioli, D., Ventre, C.: Obvious strategyproofness, bounded rationality and approximation. In: AAMAS 2019 (2019)","DOI":"10.1007\/978-3-030-30473-7_6"},{"issue":"5","key":"10071_CR3","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. Amer. Econ. Rev. 94(5), 1452\u20131475 (2004)","journal-title":"Amer. Econ. Rev."},{"issue":"11","key":"10071_CR4","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. Amer. Econ. Rev. 107(11), 3257\u201387 (2017)","journal-title":"Amer. Econ. Rev."},{"key":"10071_CR5","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"},{"key":"10071_CR6","doi-asserted-by":"crossref","unstructured":"Pycia, M., Troyan, P.: Obvious dominance and random priority. In: EC 2019 (2019)","DOI":"10.1145\/3328526.3329613"},{"key":"10071_CR7","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":"10071_CR8","unstructured":"Mackenzie, A.: A revelation principle for obviously strategy-proof implementation. Research Memorandum 014, (GSBE) (2017)"},{"issue":"5","key":"10071_CR9","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1257\/aer.p20171030","volume":"107","author":"L Zhang","year":"2017","unstructured":"Zhang, L., Levin, D.: Bounded rationality and robust mechanism design: An axiomatic approach. Amer. Econ. Rev. 107(5), 235\u201339 (2017)","journal-title":"Amer. Econ. Rev."},{"key":"10071_CR10","doi-asserted-by":"crossref","unstructured":"Bade, S., Gonczarowski, Y.A.: Gibbard-Satterthwaite success stories and obvious strategyproofness. In: EC 2017, p 565 (2017)","DOI":"10.1145\/3033274.3085104"},{"key":"10071_CR11","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":"10071_CR12","unstructured":"Ferraioli, D., Meier, A., Penna, P., Ventre, C.: Obviously strategyproof mechanisms for machine scheduling. In: ESA 2019 (2019)"},{"key":"10071_CR13","unstructured":"Kyropoulou, M., Ventre, C.: Obviously strategyproof mechanisms without money for scheduling. In: AAMAS 2019 (2019)"},{"key":"10071_CR14","doi-asserted-by":"crossref","unstructured":"Ferraioli, D., Meier, A., Penna, P., Ventre, C.: Automated optimal osp mechanisms for set systems: The case of small domains. In: WINE 2019 (2019)","DOI":"10.1007\/978-3-030-35389-6_13"},{"key":"10071_CR15","doi-asserted-by":"crossref","unstructured":"Ferraioli, D., Penna, P., Ventre, C.: Two-way greedy: Algorithms for imperfect rationality. In: WINE 2021 (2021)","DOI":"10.1007\/978-3-030-94676-0_1"},{"key":"10071_CR16","unstructured":"De Groot, A.: Thought and choice in chess. Mouton (1978)"},{"issue":"314","key":"10071_CR17","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1080\/14786445008521796","volume":"41","author":"C Shannon","year":"1950","unstructured":"Shannon, C.: Programming a computer for playing chess. Philos. Mag. 41(314), 256\u2013275 (1950)","journal-title":"Philos. Mag."},{"key":"10071_CR18","unstructured":"Pearl, J.: Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley (1984)"},{"key":"10071_CR19","doi-asserted-by":"crossref","unstructured":"Archer, A., Tardos, E.: Truthful mechanisms for one-parameter agents. In: FOCS 2001, pp 482\u2013491 (2001)","DOI":"10.1109\/SFCS.2001.959924"},{"key":"10071_CR20","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":"10071_CR21","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: AMEC 2003, pp 73\u201391 (2003)","DOI":"10.1007\/978-3-540-25947-3_5"},{"key":"10071_CR22","doi-asserted-by":"crossref","unstructured":"Hartline, J., Roughgarden, T.: Simple versus optimal mechanisms. In: EC 2009, pp 225\u2013234 (2009)","DOI":"10.1145\/1566374.1566407"},{"key":"10071_CR23","doi-asserted-by":"crossref","unstructured":"Chawla, S., Hartline, J., Malec, D., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: STOC 2010, pp 311\u2013320 (2010)","DOI":"10.1145\/1807406.1807428"},{"key":"10071_CR24","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":"10071_CR25","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":"10071_CR26","doi-asserted-by":"crossref","unstructured":"Feldman, M., Fiat, A., Roytman, A.: Makespan minimization via posted prices. In: EC 2017, pp 405\u2013422 (2017)","DOI":"10.1145\/3033274.3085129"},{"key":"10071_CR27","doi-asserted-by":"crossref","unstructured":"Eden, A., Feldman, M., Friedler, O., Talgam-Cohen, I., Weinberg, S.M.: A simple and approximately optimal mechanism for a buyer with complements. In: EC 2017, pp 323\u2013323 (2017)","DOI":"10.1145\/3033274.3085116"},{"key":"10071_CR28","doi-asserted-by":"crossref","unstructured":"Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Posted price mechanisms for a random stream of customers. In: EC 2017, pp 169\u2013186 (2017)","DOI":"10.1145\/3033274.3085137"},{"key":"10071_CR29","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":"10071_CR30","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1006\/jeth.1996.0074","volume":"70","author":"J Glazer","year":"1996","unstructured":"Glazer, J., Rubinstein, A.: An extensive game as a guide for solving a normal game. J. Econ. Theory 70, 32\u201342 (1996)","journal-title":"J. Econ. Theory"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10071-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10071-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10071-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,5]],"date-time":"2022-10-05T17:31:52Z","timestamp":1664991112000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10071-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,25]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10071"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10071-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,4,25]]},"assertion":[{"value":"10 January 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2022","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original version of this paper was updated to add the missing compact agreement Open Access funding note.","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}