Abstract
In this project we decided to investigate, analyze, and explain the inexplicably well behavior of Gurvich-Karzanov-Khachiyan's (GKK) algorithm (more correctly, its specialization) adapted for solving an innocently-looking

PROBLEM. Bob and Alice alternate moves of a token on a finite directed bi-partite graph on n vertices painted in k colors, without sinks. Bob tries to ensure that in any infinite play the maximal color visited by the token infinitely often is even, whereas Alice tries to ensure it is odd. Is there a polynomial (in n, k) algorithm to decide a winner in such a game?

Besides the fact it is known to have applications (in fact, equivalent) to the so-called propositional modal mu-calculus model checking problem,

"... the most interesting aspect of the Nash equilibrium concept to our community is that it is a most fundamental computational problem whose complexity is wide open. Suppose that two players have finitely many strategies each. Is there a polynomial algorithm for computing a (mixed) Nash equilibrium in such a game? ... Together with factoring, the complexity of finding a Nash equilibrium is in my opinion the most important concrete open question on the boundary of P today." [as mentioned in one of the ACM STOC'2001 invited lectures, after we started the work]

The GKK algorithm was suggested in 1988 to solve the so-called Mean Payoff Games Problem (slightly more general than the parity game between Bob and Alice described above), but remained ignored by the model-checking commutity. Not surprisingly, it is very different in spirit from other known iterative fixpoint algorithms for parity games. Its behavior is somewhat similar the practical behavior of the well known Simplex algorithm (incidentally, L. Khachiyan was the first to demonstrate that Linear Programming is polynomial). The GKK algorithm converges very fast on large randomly generated instances of parity games. Moreover, there are seemingly no known examples of its exponential behavior. In contrast, for other algorithms, including Simplex, such examples are well known or can be easily constructed. Recently the GKK algorithm was proved pseudopolynomial.

In this study a "literate programming" implementation of the GKK algorithm is undertaken, and an extensive experimental study of its behavior on large sets of randomly generated games (with varying parameters as the number of colors and/or bounded outdegrees) is made.

It turns out that the most complicated for the GKKA instances of parity games are generated when the mean vertex outdegree is 2 or 3 (for almost any numbers of colors). Otherwise, the algorithm easily cracks games on 10000 vertices with 5 colors in less than 1600 steps (in our experiments), which is nicely bounded by (pi/2)*n^{3/4} :-)

This talk presents an ongoing work and we plan to continue the detailed presentation/further research in a series of forthcoming SIG meetings.

Welcome,

Emmanuel Beffara,
Sergei Vorobyov
Information Technology/
Computing Science Department
Uppsala University
Box 337
S-751 05 Uppsala
Sweden

ASTEC seminar
September 4, 2001

Place: Information technology, Uppsala University
Room: 1113
Time: 15.15-16.00 (+ discussions)

Room 1113 is in building 1, floor 1, room 13 (in the southern part of the building).

Help on how to find ASTEC Seminars.

There will be an extended period for discussions after the seminar.

Speakers are encouraged to give an short (5 min) introduction to the subject at the begining of the talk.
Listeners are excused if they have to leave after 16.00.