The Computational Complexity of Single-Player Imperfect-Recall Games Article Swipe
Emanuel Tewolde
,
Caspar Oesterheld
,
Vincent Conitzer
,
Paul W. Goldberg
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2305.17805
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2305.17805
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.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2305.17805
- https://arxiv.org/pdf/2305.17805
- OA Status
- green
- Cited By
- 1
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4378768610
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4378768610Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2305.17805Digital Object Identifier
- Title
-
The Computational Complexity of Single-Player Imperfect-Recall GamesWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-05-28Full publication date if available
- Authors
-
Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, Paul W. GoldbergList of authors in order
- Landing page
-
https://arxiv.org/abs/2305.17805Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2305.17805Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2305.17805Direct OA link when available
- Concepts
-
Karush–Kuhn–Tucker conditions, Mathematical economics, Rationalizability, Mathematical optimization, Imperfect, Mathematics, Maximization, Game theory, Strategy, Best response, Computer science, Nash equilibrium, Linguistics, PhilosophyTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 1Per-year citation counts (last 5 years)
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4378768610 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2305.17805 |
| ids.doi | https://doi.org/10.48550/arxiv.2305.17805 |
| ids.openalex | https://openalex.org/W4378768610 |
| fwci | |
| type | preprint |
| title | The Computational Complexity of Single-Player Imperfect-Recall Games |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11031 |
| topics[0].field.id | https://openalex.org/fields/18 |
| topics[0].field.display_name | Decision Sciences |
| topics[0].score | 0.9915000200271606 |
| topics[0].domain.id | https://openalex.org/domains/2 |
| topics[0].domain.display_name | Social Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1803 |
| topics[0].subfield.display_name | Management Science and Operations Research |
| topics[0].display_name | Game Theory and Applications |
| topics[1].id | https://openalex.org/T10991 |
| topics[1].field.id | https://openalex.org/fields/20 |
| topics[1].field.display_name | Economics, Econometrics and Finance |
| topics[1].score | 0.9860000014305115 |
| topics[1].domain.id | https://openalex.org/domains/2 |
| topics[1].domain.display_name | Social Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2002 |
| topics[1].subfield.display_name | Economics and Econometrics |
| topics[1].display_name | Game Theory and Voting Systems |
| topics[2].id | https://openalex.org/T12137 |
| topics[2].field.id | https://openalex.org/fields/20 |
| topics[2].field.display_name | Economics, Econometrics and Finance |
| topics[2].score | 0.9437000155448914 |
| topics[2].domain.id | https://openalex.org/domains/2 |
| topics[2].domain.display_name | Social Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2002 |
| topics[2].subfield.display_name | Economics and Econometrics |
| topics[2].display_name | Economic theories and models |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C50454189 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6853443384170532 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q2075125 |
| concepts[0].display_name | Karush–Kuhn–Tucker conditions |
| concepts[1].id | https://openalex.org/C144237770 |
| concepts[1].level | 1 |
| concepts[1].score | 0.5833561420440674 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q747534 |
| concepts[1].display_name | Mathematical economics |
| concepts[2].id | https://openalex.org/C96622800 |
| concepts[2].level | 3 |
| concepts[2].score | 0.5697268843650818 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q2132788 |
| concepts[2].display_name | Rationalizability |
| concepts[3].id | https://openalex.org/C126255220 |
| concepts[3].level | 1 |
| concepts[3].score | 0.5197705626487732 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[3].display_name | Mathematical optimization |
| concepts[4].id | https://openalex.org/C2780310539 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5030555129051208 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q12547192 |
| concepts[4].display_name | Imperfect |
| concepts[5].id | https://openalex.org/C33923547 |
| concepts[5].level | 0 |
| concepts[5].score | 0.4815793037414551 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[5].display_name | Mathematics |
| concepts[6].id | https://openalex.org/C2776330181 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4685477018356323 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q18358244 |
| concepts[6].display_name | Maximization |
| concepts[7].id | https://openalex.org/C177142836 |
| concepts[7].level | 2 |
| concepts[7].score | 0.46191951632499695 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q44455 |
| concepts[7].display_name | Game theory |
| concepts[8].id | https://openalex.org/C88959737 |
| concepts[8].level | 3 |
| concepts[8].score | 0.4191649556159973 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q1546627 |
| concepts[8].display_name | Strategy |
| concepts[9].id | https://openalex.org/C32407928 |
| concepts[9].level | 3 |
| concepts[9].score | 0.4137602746486664 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q2733833 |
| concepts[9].display_name | Best response |
| concepts[10].id | https://openalex.org/C41008148 |
| concepts[10].level | 0 |
| concepts[10].score | 0.36181432008743286 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[10].display_name | Computer science |
| concepts[11].id | https://openalex.org/C46814582 |
| concepts[11].level | 2 |
| concepts[11].score | 0.30985090136528015 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q23389 |
| concepts[11].display_name | Nash equilibrium |
| concepts[12].id | https://openalex.org/C41895202 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q8162 |
| concepts[12].display_name | Linguistics |
| concepts[13].id | https://openalex.org/C138885662 |
| concepts[13].level | 0 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q5891 |
| concepts[13].display_name | Philosophy |
| keywords[0].id | https://openalex.org/keywords/karush–kuhn–tucker-conditions |
| keywords[0].score | 0.6853443384170532 |
| keywords[0].display_name | Karush–Kuhn–Tucker conditions |
| keywords[1].id | https://openalex.org/keywords/mathematical-economics |
| keywords[1].score | 0.5833561420440674 |
| keywords[1].display_name | Mathematical economics |
| keywords[2].id | https://openalex.org/keywords/rationalizability |
| keywords[2].score | 0.5697268843650818 |
| keywords[2].display_name | Rationalizability |
| keywords[3].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[3].score | 0.5197705626487732 |
| keywords[3].display_name | Mathematical optimization |
| keywords[4].id | https://openalex.org/keywords/imperfect |
| keywords[4].score | 0.5030555129051208 |
| keywords[4].display_name | Imperfect |
| keywords[5].id | https://openalex.org/keywords/mathematics |
| keywords[5].score | 0.4815793037414551 |
| keywords[5].display_name | Mathematics |
| keywords[6].id | https://openalex.org/keywords/maximization |
| keywords[6].score | 0.4685477018356323 |
| keywords[6].display_name | Maximization |
| keywords[7].id | https://openalex.org/keywords/game-theory |
| keywords[7].score | 0.46191951632499695 |
| keywords[7].display_name | Game theory |
| keywords[8].id | https://openalex.org/keywords/strategy |
| keywords[8].score | 0.4191649556159973 |
| keywords[8].display_name | Strategy |
| keywords[9].id | https://openalex.org/keywords/best-response |
| keywords[9].score | 0.4137602746486664 |
| keywords[9].display_name | Best response |
| keywords[10].id | https://openalex.org/keywords/computer-science |
| keywords[10].score | 0.36181432008743286 |
| keywords[10].display_name | Computer science |
| keywords[11].id | https://openalex.org/keywords/nash-equilibrium |
| keywords[11].score | 0.30985090136528015 |
| keywords[11].display_name | Nash equilibrium |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2305.17805 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2305.17805 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2305.17805 |
| locations[1].id | doi:10.48550/arxiv.2305.17805 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2305.17805 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5009847680 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-4128-7872 |
| authorships[0].author.display_name | Emanuel Tewolde |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Tewolde, Emanuel |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5008125381 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-4222-7855 |
| authorships[1].author.display_name | Caspar Oesterheld |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Oesterheld, Caspar |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5050903632 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-1899-7884 |
| authorships[2].author.display_name | Vincent Conitzer |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Conitzer, Vincent |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5067662147 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-5436-7890 |
| authorships[3].author.display_name | Paul W. Goldberg |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Goldberg, Paul W. |
| authorships[3].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2305.17805 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | The Computational Complexity of Single-Player Imperfect-Recall Games |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11031 |
| primary_topic.field.id | https://openalex.org/fields/18 |
| primary_topic.field.display_name | Decision Sciences |
| primary_topic.score | 0.9915000200271606 |
| primary_topic.domain.id | https://openalex.org/domains/2 |
| primary_topic.domain.display_name | Social Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1803 |
| primary_topic.subfield.display_name | Management Science and Operations Research |
| primary_topic.display_name | Game Theory and Applications |
| related_works | https://openalex.org/W1518504063, https://openalex.org/W2803931294, https://openalex.org/W2097226409, https://openalex.org/W3124939555, https://openalex.org/W4389370903, https://openalex.org/W2146267939, https://openalex.org/W1985823893, https://openalex.org/W2041287705, https://openalex.org/W2733656312, https://openalex.org/W2981664478 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2305.17805 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2305.17805 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2305.17805 |
| primary_location.id | pmh:oai:arXiv.org:2305.17805 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2305.17805 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2305.17805 |
| publication_date | 2023-05-28 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 45, 61, 77, 83 |
| abstract_inverted_index.We | 0 |
| abstract_inverted_index.as | 9, 29, 44, 60 |
| abstract_inverted_index.of | 76, 82, 95, 116 |
| abstract_inverted_index.on | 102, 113 |
| abstract_inverted_index.or | 14 |
| abstract_inverted_index.to | 33, 79, 93, 108 |
| abstract_inverted_index.we | 105, 124, 132 |
| abstract_inverted_index.For | 19, 119 |
| abstract_inverted_index.One | 36 |
| abstract_inverted_index.Our | 69 |
| abstract_inverted_index.and | 48, 53, 64, 97, 122, 127, 129 |
| abstract_inverted_index.are | 106 |
| abstract_inverted_index.for | 130 |
| abstract_inverted_index.one | 55 |
| abstract_inverted_index.the | 10, 15, 114 |
| abstract_inverted_index.two | 22 |
| abstract_inverted_index.(GT) | 59 |
| abstract_inverted_index.able | 107 |
| abstract_inverted_index.been | 27 |
| abstract_inverted_index.game | 78 |
| abstract_inverted_index.have | 26 |
| abstract_inverted_index.such | 8, 20, 117 |
| abstract_inverted_index.uses | 39, 56 |
| abstract_inverted_index.with | 5, 91 |
| abstract_inverted_index.(GDH) | 43 |
| abstract_inverted_index.(KKT) | 99 |
| abstract_inverted_index.Based | 101 |
| abstract_inverted_index.game. | 18 |
| abstract_inverted_index.games | 4 |
| abstract_inverted_index.study | 1 |
| abstract_inverted_index.these | 103 |
| abstract_inverted_index.those | 72 |
| abstract_inverted_index.three | 73 |
| abstract_inverted_index.(CDT). | 68 |
| abstract_inverted_index.(EDT), | 52 |
| abstract_inverted_index.Beauty | 12 |
| abstract_inverted_index.Driver | 17 |
| abstract_inverted_index.belief | 46, 62 |
| abstract_inverted_index.causal | 65 |
| abstract_inverted_index.double | 41 |
| abstract_inverted_index.games, | 21 |
| abstract_inverted_index.global | 87 |
| abstract_inverted_index.obtain | 125, 133 |
| abstract_inverted_index.points | 90 |
| abstract_inverted_index.relate | 71 |
| abstract_inverted_index.settle | 109 |
| abstract_inverted_index.system | 47, 63 |
| abstract_inverted_index.theory | 51, 67 |
| abstract_inverted_index.another | 54 |
| abstract_inverted_index.concept | 38 |
| abstract_inverted_index.ex-ante | 34, 120 |
| abstract_inverted_index.halving | 42 |
| abstract_inverted_index.natural | 23 |
| abstract_inverted_index.optima, | 88 |
| abstract_inverted_index.optimal | 89 |
| abstract_inverted_index.points. | 100 |
| abstract_inverted_index.problem | 13 |
| abstract_inverted_index.recall, | 7 |
| abstract_inverted_index.respect | 92 |
| abstract_inverted_index.subsets | 94 |
| abstract_inverted_index.various | 110 |
| abstract_inverted_index.Sleeping | 11 |
| abstract_inverted_index.concepts | 25, 32, 75, 81 |
| abstract_inverted_index.decision | 50, 66 |
| abstract_inverted_index.findings | 70 |
| abstract_inverted_index.problem: | 86 |
| abstract_inverted_index.proposed | 28 |
| abstract_inverted_index.results. | 135 |
| abstract_inverted_index.solution | 31, 74, 80 |
| abstract_inverted_index.thirding | 58 |
| abstract_inverted_index.imperfect | 6 |
| abstract_inverted_index.questions | 112 |
| abstract_inverted_index.variables | 96 |
| abstract_inverted_index.evidential | 49 |
| abstract_inverted_index.optimality | 121 |
| abstract_inverted_index.polynomial | 84 |
| abstract_inverted_index.NP-hardness | 126 |
| abstract_inverted_index.alternative | 30 |
| abstract_inverted_index.computation | 115 |
| abstract_inverted_index.equilibrium | 24, 37 |
| abstract_inverted_index.generalized | 40, 57 |
| abstract_inverted_index.optimality. | 35 |
| abstract_inverted_index.strategies. | 118 |
| abstract_inverted_index.Absentminded | 16 |
| abstract_inverted_index.maximization | 85 |
| abstract_inverted_index.single-player | 2 |
| abstract_inverted_index.extensive-form | 3 |
| abstract_inverted_index.CLS-completeness | 134 |
| abstract_inverted_index.correspondences, | 104 |
| abstract_inverted_index.Karush-Kuhn-Tucker | 98 |
| abstract_inverted_index.inapproximability, | 128 |
| abstract_inverted_index.(CDT,GT)-equilibria | 131 |
| abstract_inverted_index.complexity-theoretic | 111 |
| abstract_inverted_index.(EDT,GDH)-equilibria, | 123 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/16 |
| sustainable_development_goals[0].score | 0.7900000214576721 |
| sustainable_development_goals[0].display_name | Peace, Justice and strong institutions |
| citation_normalized_percentile |