The Complexity of Quantitative Concurrent Parity Games

Abstract

We consider two-player infinite games played on graphs. The games are concurrent, in that at each state the players choose their moves simultaneously and independently, and stochastic, in that the moves determine a probability distribution for the successor state. The value of a game is the maximal probability with which a player can guarantee the satisfaction of her objective. We show that the values of concurrent games with omega- regular objectives expressed as parity conditions can be decided in NP-coNP. This result substantially improves the best known previous bound of 3EXPTIME. It also shows that the full class of concurrent parity games is no harder than the special case of turn-based stochastic reachability games, for which NP-coNP is the best known bound.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2006
Accession Number
ADA457139

Entities

People

  • Krishnendu Chatterjee
  • Luca De Alfaro
  • Thomas Henzinger

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Computer Science
  • Information Operations
  • Irrational Numbers
  • Language
  • Matrix Games
  • Notation
  • Numbers
  • Polynomials
  • Precision
  • Probability
  • Probability Distributions
  • Random Variables
  • Sequences
  • Stochastic Processes
  • Theorems
  • Transitions
  • Zero-Sum Games

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Game Theory.
  • Mathematical Modeling and Probability Theory.