Parity game
A parity game is an infinite game with perfect information between two players on a directed graph . The nodes of the graph are divided between the players so that each player can decide for his nodes how they should move on. In addition, each node is assigned a natural number as a priority (sometimes also called color) .
The path that is described by the moves of the two players is called a game . The parity of the highest priority of the game determines which of the two players wins the game.
Variants in the definition
Equivalent variants of the definition of parity games are:
- Instead of the highest priority, the lowest priority determines the player. This is called min-parity games. If there is a maximum priority , the priorities of the two variants can be converted into one another.
- It is required that the two players always pull alternately, so that the sets of nodes of the players form a bipartition of the nodes. However, between two nodes of a player, a node of the other player can always be inserted, where the other player has no choice.
Classification within game theory
In game theory, parity games can be characterized by the following properties:
Parity games are ...
- Zero-sum games : if one player wins, the other loses and vice versa.
- sequential: the players take turns moving.
- Games with perfect information .
- infinite.
- discreet.
- random.
Solving a parity game
Solving a parity game means determining for each node of the parity game which of the two players has a winning strategy if a game were to begin at this node. The sets of nodes from which players can win are called the profit ranges . The nodes of a parity game can be broken down into the two profit areas.
There are algorithms that find this decomposition in exponential time . However, it is an unsolved problem in computer science whether there are also algorithms with polynomial running time that can determine these profit ranges.