{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T13:53:02Z","timestamp":1763041982644,"version":"3.45.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"PNRR project FAIR - Future AI Research","award":["PE00000013"],"award-info":[{"award-number":["PE00000013"]}]},{"name":"UKRI Trustworthy Autonomous Systems Hub","award":["EP\/V00784X\/1"],"award-info":[{"award-number":["EP\/V00784X\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>The realization that selfish interests need to be accounted for in the design of algorithms has produced many interesting and valuable contributions in computer science under the general umbrella of algorithmic mechanism design. Our work stems from the observation that selfishness is different from rationality; agents will attempt to strategize whenever they perceive it to be convenient. Recent work in economics has focused on a particular notion of imperfect rationality, namely absence of contingent reasoning skills, and defined obvious strategyproofness (OSP) as a way to deal with the selfishness of these agents. However, it is not clear to date what algorithmic approaches ought to be used for OSP. In this article, we rather surprisingly show that, for binary allocation problems, OSP is fully captured by a natural combination of two well-known and extensively studied algorithmic techniques: forward and reverse greedy. We call two-way greedy this underdeveloped algorithmic design paradigm. We are then able to import a host of known approximation bounds obtained through greedy algorithms to OSP and strengthen the strategic properties of this family of algorithms. Finally, we begin exploring the full power of two-way greedy (and, in turns, OSP) in the context of set systems.<\/jats:p>\n                  <jats:p\/>","DOI":"10.1145\/3760425","type":"journal-article","created":{"date-parts":[[2025,8,14]],"date-time":"2025-08-14T11:25:27Z","timestamp":1755170727000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Two-way Greedy: Algorithms for Imperfect Rationality"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7962-5200","authenticated-orcid":false,"given":"Diodato","family":"Ferraioli","sequence":"first","affiliation":[{"name":"University of Salerno","place":["Fisciano, Italy"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5959-2421","authenticated-orcid":false,"given":"Paolo","family":"Penna","sequence":"additional","affiliation":[{"name":"IOG","place":["Zurich, Switzerland"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1464-1215","authenticated-orcid":false,"given":"Carmine","family":"Ventre","sequence":"additional","affiliation":[{"name":"King's College London","place":["London, United Kingdom of Great Britain and Northern Ireland"]}]}],"member":"320","published-online":{"date-parts":[[2025,11,13]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875583"},{"key":"e_1_3_3_3_2","volume-title":"Obvious Strategy-proofness with Respect to a Partition","author":"Arribillaga Pablo R.","year":"2023","unstructured":"Pablo R. Arribillaga, Jordi Mass\u00f3, and Alejandro Neme. 2023. Obvious Strategy-proofness with Respect to a Partition. Technical Report."},{"key":"e_1_3_3_4_2","doi-asserted-by":"crossref","unstructured":"R. Pablo Arribillaga Jordi Mass\u00f3 and Alejandro Neme. 2019. All Sequential Allotment Rules Are Obviously Strategy-proof. Theoretical Economics 18 3 (2019) 104992.","DOI":"10.3982\/TE5111"},{"key":"e_1_3_3_5_2","doi-asserted-by":"crossref","DOI":"10.1016\/j.jet.2020.104992","article-title":"On obvious strategy-proofness and single-peakedness","author":"Arribillaga R.","year":"2020","unstructured":"R. Arribillaga, J. Mass\u00f3, and A. Neme. 2020. On obvious strategy-proofness and single-peakedness. Journal of Economic Theory 186, March 2020 (2020), 104992.","journal-title":"Journal of Economic Theory"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2018.07.001"},{"issue":"5","key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"1452","DOI":"10.1257\/0002828043052330","article-title":"An efficient ascending-bid auction for multiple objects","volume":"94","author":"Ausubel Lawrence M.","year":"2004","unstructured":"Lawrence M. Ausubel. 2004. An efficient ascending-bid auction for multiple objects. American Economic Reviews 94, 5 (2004), 1452\u20131475.","journal-title":"American Economic Reviews"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130404"},{"key":"e_1_3_3_9_2","first-page":"565","volume-title":"EC","author":"Bade S.","year":"2017","unstructured":"S. Bade and Y. Gonczarowski. 2017. Gibbard-Satterthwaite success stories and obvious strategyproofness. In EC. 565."},{"key":"e_1_3_3_10_2","doi-asserted-by":"crossref","DOI":"10.1007\/s00453-003-1036-3","article-title":"(Incremental) priority algorithms","volume":"37","author":"Borodin A.","year":"2003","unstructured":"A. Borodin, M.N. Nielsen, and C. Rackoff. 2003. (Incremental) priority algorithms. Algorithmica 37 (2003), 295\u2013326.","journal-title":"Algorithmica"},{"key":"e_1_3_3_11_2","volume-title":"ITCS","author":"Christodoulou Giorgos","year":"2022","unstructured":"Giorgos Christodoulou, Vasilis Gkatzelis, and Daniel Schoepflin. 2022. Optimal deterministic clock auctions and beyond. In ITCS."},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","DOI":"10.1016\/0020-0190(83)90007-8","article-title":"A modification of the greedy algorithm for vertex cover","author":"Clarkson K.","year":"1983","unstructured":"K. Clarkson. 1983. A modification of the greedy algorithm for vertex cover. Information Processing Letters 16, 1 (1983), 23\u201325.","journal-title":"Information Processing Letters"},{"key":"e_1_3_3_13_2","first-page":"71:1\u201371:17","volume-title":"ICALP","author":"Keijzer B. de","year":"2020","unstructured":"B. de Keijzer, M. Kyropoulou, and C. Ventre. 2020. Obviously strategyproof single-minded combinatorial auctions. In ICALP. 71:1\u201371:17."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0835"},{"key":"e_1_3_3_15_2","first-page":"820","volume-title":"EC","author":"Feldman Michal","year":"2022","unstructured":"Michal Feldman, Vasilis Gkatzelis, Nick Gravin, and Daniel Schoepflin. 2022. Bayesian and randomized clock auctions. In EC. 820\u2013845."},{"key":"e_1_3_3_16_2","first-page":"171","volume-title":"WINE","author":"Ferraioli D.","year":"2019","unstructured":"D. Ferraioli, A. Meier, P. Penna, and C. Ventre. 2019. Automated optimal OSP mechanisms for set systems - the case of small domains. In WINE. 171\u2013185."},{"key":"e_1_3_3_17_2","first-page":"46:1\u201346:15","volume-title":"ESA","author":"Ferraioli D.","year":"2019","unstructured":"D. Ferraioli, A. Meier, P. Penna, and C. Ventre. 2019. Obviously strategyproof mechanisms for machine scheduling. In ESA. 46:1\u201346:15."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.1264"},{"key":"e_1_3_3_19_2","first-page":"3","volume-title":"WINE","author":"Ferraioli Diodato","year":"2021","unstructured":"Diodato Ferraioli, Paolo Penna, and Carmine Ventre. 2021. Two-way greedy: Algorithms for imperfect rationality. In WINE. 3\u201321."},{"key":"e_1_3_3_20_2","first-page":"240","volume-title":"IJCAI","author":"Ferraioli D.","year":"2018","unstructured":"D. Ferraioli and C. Ventre. 2018. Probabilistic verification for obviously strategyproof mechanisms. In IJCAI. 240\u2013246."},{"key":"e_1_3_3_21_2","first-page":"77","volume-title":"SAGT","author":"Ferraioli D.","year":"2019","unstructured":"D. Ferraioli and C. Ventre. 2019. Obvious strategyproofness, bounded rationality and approximation. In SAGT. 77\u201391."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00771-x"},{"key":"e_1_3_3_23_2","first-page":"2125","volume-title":"AAMAS","author":"Ferraioli Diodato","year":"2023","unstructured":"Diodato Ferraioli and Carmine Ventre. 2023. Explicit payments for obviously strategyproof mechanisms. In AAMAS. 2125\u20132133."},{"key":"e_1_3_3_24_2","first-page":"657","volume-title":"EC","author":"Ferraioli Diodato","year":"2023","unstructured":"Diodato Ferraioli and Carmine Ventre. 2023. On the connection between greedy algorithms and imperfect rationality. In EC. 657\u2013677."},{"key":"e_1_3_3_25_2","article-title":"An algorithmic theory of simplicity in mechanism design","author":"Ferraioli Diodato","year":"2024","unstructured":"Diodato Ferraioli and Carmine Ventre. 2024. An algorithmic theory of simplicity in mechanism design. In WINE.","journal-title":"WINE"},{"key":"e_1_3_3_26_2","volume-title":"EC","author":"Gkatzelis V.","year":"2017","unstructured":"V. Gkatzelis, E. Markakis, and T. Roughgarden. 2017. Deferred-acceptance auctions for multiple levels of service. In EC."},{"key":"e_1_3_3_27_2","first-page":"416","volume-title":"ESA","author":"Goldberg Andrew V.","year":"2001","unstructured":"Andrew V. Goldberg and Jason D. Hartline. 2001. Competitive auctions for multiple digital goods. In ESA. 416\u2013427."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","unstructured":"D. Hausmann B. Korte and T. A. Jenkyns. 1980. Worst case analysis of greedy type algorithms for independence systems. In Combinatorial Optimization. Mathematical Programming Studies M. W. Padberg (Ed.). Vol 12. Springer Berlin Heidelberg. 10.1007\/BFb0120891","DOI":"10.1007\/BFb0120891"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.2307\/1913557"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_3_3_31_2","first-page":"1574","volume-title":"AAMAS","author":"Kyropoulou M.","year":"2019","unstructured":"M. Kyropoulou and C. Ventre. 2019. Obviously strategyproof mechanisms without money for scheduling. In AAMAS. 1574\u20131581."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585266"},{"issue":"11","key":"e_1_3_3_33_2","article-title":"Obviously strategy-proof mechanisms","volume":"107","author":"Li S.","year":"2017","unstructured":"S. Li. 2017. Obviously strategy-proof mechanisms. American Economic Review 107, 11 (2017), 3257\u201387.","journal-title":"American Economic Review"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2020.09.010"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.econlet.2021.110239"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0014-2921(97)00146-3"},{"key":"e_1_3_3_37_2","doi-asserted-by":"crossref","DOI":"10.1086\/704074","article-title":"Clock auctions and radio spectrum reallocation","author":"Milgrom P.","year":"2020","unstructured":"P. Milgrom and I. Segal. 2020. Clock auctions and radio spectrum reallocation. Journal of Political Economy 128, 1 (2020).","journal-title":"Journal of Political Economy"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2007.12.009"},{"issue":"1","key":"e_1_3_3_39_2","first-page":"359","article-title":"Algorithmic mechanism design","volume":"35","author":"Nisan Noam","year":"2015","unstructured":"Noam Nisan and A. Ronen. 2015. Algorithmic mechanism design. Games and Economic Behavior 35, 1 (2015), 359\u2013379.","journal-title":"Games and Economic Behavior"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.5555\/1296179"},{"key":"e_1_3_3_41_2","first-page":"1","volume-title":"EC","author":"Pycia Marek","year":"2019","unstructured":"Marek Pycia and Peter Troyan. 2019. Obvious dominance and random priority. In EC. 1\u20131."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA16310"},{"key":"e_1_3_3_43_2","first-page":"19","volume-title":"SODA","author":"Ron Shiri","year":"2024","unstructured":"Shiri Ron. 2024. Impossibilities for obviously strategy-proof mechanisms. In SODA. 19\u201340."},{"key":"e_1_3_3_44_2","volume-title":"EC","author":"Saks M.","year":"2005","unstructured":"M. Saks and L. Yu. 2005. Weak monotonicity suffices for truthfulness on convex domains. In EC."},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.78"},{"key":"e_1_3_3_46_2","first-page":"860","volume-title":"EC","author":"Thomas Clayton","year":"2021","unstructured":"Clayton Thomas. 2021. Classification of priorities such that deferred acceptance is OSP implementable. In EC. 860\u2013860."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1111\/iere.12384"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijindorg.2006.10.002"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3760425","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T13:47:17Z","timestamp":1763041637000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3760425"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,13]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3760425"],"URL":"https:\/\/doi.org\/10.1145\/3760425","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,13]]},"assertion":[{"value":"2024-06-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}