A parity game is a two-player game on a finite directed graph in which each graph vertex has an owner, a nonnegative integer priority, and at least one outgoing graph edge. The owner of the current graph vertex chooses the next graph edge. In the minimum-priority convention, Even wins an infinite play iff the least priority occurring infinitely often is even; otherwise Odd wins. Equivalently, the maximum-priority convention can be used after renumbering priorities so that their order is reversed and their parity is preserved.
For example, if every reachable graph vertex has an even priority, every infinite play is won by Even. The algorithmic task is to find all starting vertices from which each player can force a win. Jurdziński and Lazić (2018) gave a quasipolynomial time algorithm for this task.
