A play in a parity game is a maximal sequence of nodes following the transition relation. The winner of a finite play of a parity game is the player whose opponent is unable to move. The outcome of an infinite play is determined by the priorities of the occurring positions. Typically, player 0 wins an infinite play if the highest infinitely often occurring priority is even. Player 1 wins otherwise. Whence the name "parity".
Parity games lie in the third level of the borel hierarchy and are as such determined. Games related to parity games were implicitly used in Rabin's proof of decidability of second order theory of n successors, where determinacy of such games was proven. Knaster-Tarski theorem leads to a relatively simple proof of determinacy of parity games.
Moreover, parity games are history-free determined, so that if a player has a winning strategy then she has a winning strategy which depends only on the board position, and not on the history of the play.
The decision problem of a parity game played on a finite graph consists of deciding the winner of a play from a given position. It has been shown that this problem is in NP and Co-NP, as well as UP and co-UP. It remains an open question whether for any parity game the decision problem is solvable in PTime.
Given that parity games are history free determined, the decision problem can be seen as the following rather simple looking graph theory problem. Given a finite colored directed bipartite graph with n vertices , and V colored with colors from 1 to m, is there a choice function selecting a single out-going edge from each vertex of , such that the resulting subgraph has the property that in each cycle the largest occurring color is even.
Note that as opposed to parity games, this game is no more symmetric with respect to players 0 and 1.