Metraipolis › archive › dc_51366b5ffce9

Parity game — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Parity_game
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T22:58:16.377Z
SHA-256 of the archived text
f81d431f38a8e7d8b9daadae944f0de9c8ddc1d7e71baeba17ccee2a7ef4fc9d
Stable URL of this page
https://metraipolis.com/documento/dc_51366b5ffce9

How to cite

Parity game — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Parity_game (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_51366b5ffce9 (Metraipolis archive dc_51366b5ffce9, sha256 f81d431f38a8e7d8b9daadae944f0de9c8ddc1d7e71baeba17ccee2a7ef4fc9d)
BibTeX
@misc{dc51366b5ffce9,
  title = {Parity game — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Parity_game},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_51366b5ffce9; sha256 f81d431f38a8e7d8b9daadae944f0de9c8ddc1d7e71baeba17ccee2a7ef4fc9d},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Parity_game. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The owner of the node that the token falls on selects the successor node (does the next move). The players keep moving the token, resulting in a (possibly infinite) path, called a play. The winner of a finite play is the player whose opponent is unable to move. The winner of an infinite play is determined by the priorities appearing in the play. Typically, player 0 wins an infinite play if the largest priority that occurs infinitely often in the play is even. Player 1 wins otherwise. This explains the word "parity" in the title. Parity games lie in the third level of the Borel hierarchy, and are consequently determined. Games related to parity games were implicitly used in Rabin's proof of decidability of the monadic second-order theory of n successors (S2S for n = 2), where determinacy of such games was proven. The Knaster–Tarski theorem leads to a relatively simple proof of determinacy of parity games. Moreover, parity games are history-free determined. This means that if a player has a winning strategy then that player has a winning strategy that depends only on the current board position, and not on the history of the play.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «game theory»).
Fonte: Wikipedia in inglese, voce «Parity game» — https://en.wikipedia.org/wiki/Parity_game
Wikidata Q7137537 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q7137537
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Parity_game?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1339223504, consultata il 2026-10-07T22:35:57.026Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 58234cf081047639ba8b268f67b7ff38f4c89512ff11fe474855069db169275a