Concurrent Multi-Player Parity Games

Parity games are a powerful framework widely used to address fundamental questions in computer science. In the basic setting they consist of two-player turn-based games, played on directed graphs, whose nodes are labeled with priorities. Solving such a game can be done in time exponential in the number of the priorities (and polynomial in the number of states) and it is a long-standing open question whether a polynomial-time algorithm exists. Precisely this problem resides in the class UP ∩ co-UP. In this paper we introduce and solve efficiently concurrent multi-player parity games where the players, being existential and universal, compete under fixed and strict alternate coalitions. The solution we provide uses an extension of the classic Zielonka Recursive Algorithm. Precisely, we introduce an ad hoc algorithm for the attractor subroutine. Directly from this, we derive that the problem of solving such games is in PSpace. We also address the lower bound and show that the complexity of our algorithm is tight, i. e. we show that the problem is PSpace-hard by providing a reduction from the QBF satisfiability problem.

Authors

• Vadim Malvone
• Aniello Murano
• Loredana Sorrentino

Keywords

• Parity games
• Concurrent multi-player games