---
_id: '3863'
abstract:
- lang: eng
  text: '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.'
article_processing_charge: No
author:
- first_name: Dietmar
  full_name: Berwanger, Dietmar
  last_name: Berwanger
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Martin
  full_name: De Wulf, Martin
  last_name: De Wulf
- first_name: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  ama: Berwanger D, Chatterjee K, De Wulf M, Doyen L, Henzinger TA. Strategy construction
    for parity games with imperfect information. <i>Information and Computation</i>.
    2010;208(10):1206-1220. doi:<a href="https://doi.org/10.1016/j.ic.2009.09.006">10.1016/j.ic.2009.09.006</a>
  apa: Berwanger, D., Chatterjee, K., De Wulf, M., Doyen, L., &#38; Henzinger, T.
    A. (2010). Strategy construction for parity games with imperfect information.
    <i>Information and Computation</i>. Elsevier. <a href="https://doi.org/10.1016/j.ic.2009.09.006">https://doi.org/10.1016/j.ic.2009.09.006</a>
  chicago: Berwanger, Dietmar, Krishnendu Chatterjee, Martin De Wulf, Laurent Doyen,
    and Thomas A Henzinger. “Strategy Construction for Parity Games with Imperfect
    Information.” <i>Information and Computation</i>. Elsevier, 2010. <a href="https://doi.org/10.1016/j.ic.2009.09.006">https://doi.org/10.1016/j.ic.2009.09.006</a>.
  ieee: D. Berwanger, K. Chatterjee, M. De Wulf, L. Doyen, and T. A. Henzinger, “Strategy
    construction for parity games with imperfect information,” <i>Information and
    Computation</i>, vol. 208, no. 10. Elsevier, pp. 1206–1220, 2010.
  ista: Berwanger D, Chatterjee K, De Wulf M, Doyen L, Henzinger TA. 2010. Strategy
    construction for parity games with imperfect information. Information and Computation.
    208(10), 1206–1220.
  mla: Berwanger, Dietmar, et al. “Strategy Construction for Parity Games with Imperfect
    Information.” <i>Information and Computation</i>, vol. 208, no. 10, Elsevier,
    2010, pp. 1206–20, doi:<a href="https://doi.org/10.1016/j.ic.2009.09.006">10.1016/j.ic.2009.09.006</a>.
  short: D. Berwanger, K. Chatterjee, M. De Wulf, L. Doyen, T.A. Henzinger, Information
    and Computation 208 (2010) 1206–1220.
date_created: 2018-12-11T12:05:35Z
date_published: 2010-10-01T00:00:00Z
date_updated: 2026-05-29T09:53:31Z
day: '01'
ddc:
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1016/j.ic.2009.09.006
ec_funded: 1
external_id:
  isi:
  - '000281830300007'
file:
- access_level: open_access
  checksum: 29d146e4f8049dbb7f80bbf7ea3700ed
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:17:44Z
  date_updated: 2020-07-14T12:46:18Z
  file_id: '5300'
  file_name: IST-2012-58-v1+1_Strategy_construction_for_parity_games_with_imperfect_information.pdf
  file_size: 287496
  relation: main_file
file_date_updated: 2020-07-14T12:46:18Z
has_accepted_license: '1'
intvolume: '       208'
isi: 1
issue: '10'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 1206 - 1220
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '215543'
  name: COMponent-Based Embedded Systems design Techniques
publication: Information and Computation
publication_status: published
publisher: Elsevier
publist_id: '2319'
pubrep_id: '58'
quality_controlled: '1'
related_material:
  record:
  - id: '3880'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Strategy construction for parity games with imperfect information
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 208
year: '2010'
...