Adapting GurvichKarzanovKhachiyan's Algorithm
for Parity Games: Implementation and Experimentation
EMMANUEL BEFFARA
(Ecole Normale Superieure de Lyon, France)
present the results of his exjobb project
(advisor: Sergei Vorobyov, IT/UU)
Tuesday, September 4, 2001, 15:15  16:00, room: 1113
Abstract
In this project we decided to investigate, analyze, and explain the
inexplicably well behavior of GurvichKarzanovKhachiyan's (GKK)
algorithm (more correctly, its specialization) adapted for solving an
innocentlylooking
PROBLEM. Bob and Alice alternate moves of a token on a finite directed
bipartite 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 socalled propositional modal mucalculus 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 socalled Mean
Payoff Games Problem (slightly more general than the parity game
between Bob and Alice described above), but remained ignored by the
modelchecking 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
S751 05 Uppsala
Sweden
Place: Information technology, Uppsala University
Room: 1113
Time: 15.1516.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.
Everyone is welcome !
Updated 31Aug2001 12:05 by Roland Grönroos
email: info at astec.uu.se
Location: http://www.astec.uu.se/Seminars/01/0904.shtml
