1
$\begingroup$

The 7th chapter (7.3 section) of "Automata Logics and Infinite Games" by Erich Gradel, Wolfgang Thomas, Thomas Wilke gives a way to convert max parity game to mean payoff game.

I do not understand how to use the solution for mean payoff game i.e $\nu(v)$ to compute the winning region of parity game.

It states "It is our goal to find the values at the vertices efficiently. This immediately gives us the winning region." But there is no further explanation.

Is the winning region those set of vertices for which $\nu(v) \geq 0$ ?

Conversion from parity game to mean payoff game : Suppose our parity game is (A, Ω). W.l.o.g. the priorities are {0, . . . , d − 1}. The mean payoff game uses the same arena. An edge originating at a vertex v with priority i = Ω(v) receives the weight $w(v, u) = (−1)^in^i$. Let ν = 0. Clearly all weights lie in the range $\{−n^{d−1}, . . . , n^{d−1}\}$. This defines our mean payoff game (A, 0, $n^d$, w).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.