{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T02:56:32Z","timestamp":1773802592817,"version":"3.50.1"},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","issue":"20","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAAI"],"abstract":"<jats:p>A safe Pareto improvement (SPI) is a modification of a game that leaves all players better off with certainty. \nSPIs are typically proven under qualitative assumptions about the way different games are played. \nFor example, we assume that strictly dominated strategies can be iteratively removed and that isomorphic games are played isomorphically.\nIn this work, we study SPIs achieved through three types of \\textit{ex post} verifiable commitments -- promises about player behavior from which deviations can be detected by observing the game. \nFirst, we consider disarmament -- commitments not to play certain actions. \nNext, we consider SPIs based on \\textit{token games}. A token game is a game played by simply announcing an action (via cheap talk). As such, its outcome is intrinsically meaningless. However, we assume the players commit in advance to play specific (pure or correlated) strategy profiles in the original game as a function of the token game outcome. Under such commitments, the token game becomes a new, meaningful normal-form game.\nFinally, we consider default-conditional commitment: SPIs in settings where the players' default ways of playing the original game can be credibly revealed and hence the players can commit to act as a function of this default. \nWe characterize the complexity of deciding whether SPIs exist in all three settings, giving a mixture of characterizations and efficient algorithms and \\NP- and \\textsc{Graph Isomorphism}-hardness<\/jats:p>","DOI":"10.1609\/aaai.v40i20.38774","type":"journal-article","created":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T00:48:30Z","timestamp":1773794910000},"page":"17231-17241","source":"Crossref","is-referenced-by-count":0,"title":["Promises Made, Promises Kept: Safe Pareto Improvements via Ex Post Verifiable Commitments"],"prefix":"10.1609","volume":"40","author":[{"given":"Nathaniel","family":"Sauerberg","sequence":"first","affiliation":[]},{"given":"Caspar","family":"Oesterheld","sequence":"additional","affiliation":[]}],"member":"9382","published-online":{"date-parts":[[2026,3,14]]},"container-title":["Proceedings of the AAAI Conference on Artificial Intelligence"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/38774\/42736","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/38774\/42736","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T00:48:30Z","timestamp":1773794910000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/38774"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,14]]},"references-count":0,"journal-issue":{"issue":"20","published-online":{"date-parts":[[2026,3,17]]}},"URL":"https:\/\/doi.org\/10.1609\/aaai.v40i20.38774","relation":{},"ISSN":["2374-3468","2159-5399"],"issn-type":[{"value":"2374-3468","type":"electronic"},{"value":"2159-5399","type":"print"}],"subject":[],"published":{"date-parts":[[2026,3,14]]}}}