Jump to content

Talk:Parity game

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

The definition given does not match the notion of a "parity game". To my knowledge, a parity game is a two-player board game where board positions are assigned natural numbers, so called priorities. The winner of a finite play in a parity game is the player whose opponent gets stuck. The winner of an infinite play is determined by the priorities of infinitely often occuring board positions. Typically, player 0 wins an infinite play if the highest priority of an infinitely often occuring positions is even. Whence "parity".

Historyfree (or positional) determinacy that is refered to in the definition is a mere property of parity games that was shown by Mostowski and independently Jutla and Emerson.

Are there conflicting notions in Game Theory that I am not aware of? Is there a source of the definition given in the article?

Christian.kissig 08:37, 2 April 2007 (UTC)[reply]

Note

[edit]

That we need to link to Rabin's tree theorem or something like that once it's written. Tijfo098 (talk) 03:35, 15 November 2012 (UTC)[reply]

Recent quasipolynomial time algorithms

[edit]

There seems to be a consensus now that Parity Games can be solved in quasipolynomial time. See for example the references listed here:

An implementation and comparison with previous approaches is available (classic strategy improvement "wins" on random instances, but gets "slow" on Friedmann’s trap examples):

Jakito (talk) 01:49, 13 March 2017 (UTC)[reply]