Strategy construction for parity games with imperfect information Journal Article


Author(s): Berwanger, Dietmar; Chatterjee, Krishnendu; De Wulf, Martin; Doyen, Laurent; Henzinger, Thomas A
Article Title: Strategy construction for parity games with imperfect information
Affiliation IST Austria
Abstract: We consider two-player parity games with imperfect information in which strategies rely on observations that provide imperfect information about the history of a play. To solve such games, i.e., to determine the winning regions of players and corresponding winning strategies, one can use the subset construction to build an equivalent perfect-information game. Recently, an algorithm that avoids the inefficient subset construction has been proposed. The algorithm performs a fixed-point computation in a lattice of antichains, thus maintaining a succinct representation of state sets. However, this representation does not allow to recover winning strategies. In this paper, we build on the antichain approach to develop an algorithm for constructing the winning strategies in parity games of imperfect information. One major obstacle in adapting the classical procedure is that the complementation of attractor sets would break the invariant of downward-closedness on which the antichain representation relies. We overcome this difficulty by decomposing problem instances recursively into games with a combination of reachability, safety, and simpler parity conditions. We also report on an experimental implementation of our algorithm: to our knowledge, this is the first implementation of a procedure for solving imperfect-information parity games on graphs.
Journal Title: Information and Computation
Volume: 208
Issue 10
ISSN: 0890-5401
Publisher: Elsevier  
Date Published: 2010-10-01
Start Page: 1206
End Page: 1220
URL:
DOI: 10.1016/j.ic.2009.09.006
Notes: This research was supported in part by the NSF grants CCR-0132780, CNS-0720884, and CCR-0225610, by the Swiss National Science Foundation, by the Deutsche Forschungs- gemeinschaft (DFG), by the European projects Combest, Gasics, Lint, and Quasimodo, by the Belgian PAI program Moves and by the Belgian Federated Center in Verification (CFV) funded by the F.R.S.-FNRS. We thank three anonymous referees for their useful comments.
Open access: yes (repository)
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work