finite.works
Results · Finite games and operator-algebra type · The price of perfection

Perfect play has different arithmetical complexity in semifinite and type III algebras

Seth Douglas and Nidhal Mghirbi · version 1.0.0 · Zenodo, · 28 pages · doi:10.5281/zenodo.23925092 · PDF

SupersededConsolidated into A trace costs one quantifier: the exact complexity of perfect play in nonlocal games (doi:10.5281/zenodo.23962890), which supersedes this preprint.

The result

As the paper states it, in briefFor finite rational nonlocal games, existence of perfect normal play in a type II1 algebra, a type II∞ algebra, or any semifinite algebra is Σ⁰₂-complete. For each fixed λ∈[0,1], existence in a type IIIλ factor is equivalent to commuting perfection and is Π⁰₁-complete. Existence of commuting perfect play together with absence of every normal semifinite perfect strategy is Π⁰₂-complete, with hardness on games that are commuting perfect and have finite-dimensional quantum value one. The perfect-play languages for type I and type II1 are incomparable, and both are proper subsets of the type II∞ language.

Labels

This preprint is consolidated into A trace costs one quantifier: the exact complexity of perfect play in nonlocal games, which supersedes it. The checks and the four labels are given there.

Versionsone, each with its own DOI

Every archived version, newest first. Dates are Zenodo publication dates. All versions: 10.5281/zenodo.23925091, which always resolves to the newest.
VersionDateDOINotes
1.0.010.5281/zenodo.23925092 PDF hosted here.

Paper, code and links

PDF

papers/perfect-play-types-v1.0.0.pdf, version 1.0.0, 655,061 bytes, 28 pages.

SHA-256 0fbf418e00e68d790661c931f349c51c2e1dde4944d6d949bead0d350b2b0499

Of paper/main.pdf, 655,061 bytes, in the Zenodo archive; identical in the repository at that commit. The same file is hosted here: papers/perfect-play-types-v1.0.0.pdf.

Commit

b1b8af58a904b8bacb064c8a05cf86411a3d8a10

The commit archived on Zenodo (Apsiape/perfect-play-von-neumann-types, tag v1.0.0). The main branch has since recorded the DOI.

Licence

Paper and documentation CC BY 4.0; scripts MIT or Apache 2.0, at your option.

Corrections

None so far.

All corrections, and what counts as one.

Cite

@misc{douglas2026perfectplaytypes,
  author  = {Douglas, Seth and Mghirbi, Nidhal},
  title   = {Perfect play has different arithmetical complexity in semifinite and type {III} algebras},
  year    = {2026},
  version = {1.0.0},
  doi     = {10.5281/zenodo.23925092},
  url     = {https://doi.org/10.5281/zenodo.23925092}
}

perfect-play-types.bibAll papers as BibTeX