The computational complexity of single-player imperfect-recall games

Conference item

We study single-player extensive-form games with imperfect recall, such as the Sleeping Beauty problem or the Absentminded Driver game. For such games, two natural equilibrium concepts have been proposed as alternative solution concepts to ex-ante optimality. One equilibrium concept uses generalized double halving (GDH) as a belief system and evidential decision theory (EDT), and another one uses generalized thirding (GT) as a belief system and causal decision theory (CDT). Our findings relate those three solution concepts of a game to solution concepts of a polynomial maximization problem: global optima, optimal points with respect to subsets of variables and Karush-Kuhn-Tucker (KKT) points. Based on these correspondences, we are able to settle various complexity-theoretic questions on the computation of such strategies. For ex-ante optimality and (EDT,GDH)-equilibria, we obtain NP-hardness and inapproximability, and for (CDT,GT)-equilibria we obtain CLS-completeness results.

Authors: Tewolde, E; Oesterheld, C; Conitzer, V; Goldberg, PW

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: International Joint Conferences on Artificial Intelligence
• Host title: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
• Pages: 2878-2887
• Publication date: 2023-08-11
• Acceptance date: 2023-05-19
• Event title: 32nd IJCAI International Joint Conference on Artificial Intelligence (IJCAI 2023)
• Event location: Macao, SAR
• Event website: https://ijcai-23.org/
• Event start date: 2023-08-19
• Event end date: 2023-08-25
• DOI: 10.24963/ijcai.2023/321
• ISSN: 1045-0823
• EISBN: 9781956792034
• Language: English