TY - CONF
AB - A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with omega-regular winning conditions specified as Rabin or Streett objectives. These games are NP-complete and coNP-complete, respectively. The value of the game for a player at a state s given an objective Phi is the maximal probability with which the player can guarantee the satisfaction of Phi from s. We present a strategy-improvement algorithm to compute values in stochastic Rabin games, where an improvement step involves solving Markov decision processes (MDPs) and nonstochastic Rabin games. The algorithm also computes values for stochastic Streett games but does not directly yield an optimal strategy for Streett objectives. We then show how to obtain an optimal strategy for Streett objectives by solving certain nonstochastic Streett games.
AU - Krishnendu Chatterjee
AU - Thomas Henzinger
ID - 3888
TI - Strategy improvement for stochastic Rabin and Streett games
VL - 4137
ER -
TY - CONF
AB - We study observation-based strategies for two-player turn-based games on graphs with omega-regular objectives. An observation-based strategy relies on imperfect information about the history of a play, namely, on the past sequence of observations. Such games occur in the synthesis of a controller that does not see the private state of the plant. Our main results are twofold. First, we give a fixed-point algorithm for computing the set of states from which a player can win with a deterministic observation-based strategy for any omega-regular objective. The fixed point is computed in the lattice of antichains of state sets. This algorithm has the advantages of being directed by the objective and of avoiding an explicit subset construction on the game graph. Second, we give an algorithm for computing the set of states from which a player can win with probability 1 with a randomized observation-based strategy for a Buchi objective. This set is of interest because in the absence of perfect information, randomized strategies are more powerful than deterministic ones. We show that our algorithms are optimal by proving matching lower bounds.
AU - Krishnendu Chatterjee
AU - Doyen, Laurent
AU - Thomas Henzinger
AU - Raskin, Jean-François
ID - 3889
TI - Algorithms for omega-regular games with imperfect information
VL - 4207
ER -
TY - CONF
AB - 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 w-regular objectives expressed as parity conditions can be decided in NP boolean AND 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 boolean AND coNP is the best known bound. While the previous, more restricted NP boolean AND coNP results for graph games relied on the existence of particularly simple (pure memoryless) optimal strategies, in concurrent games with parity objectives optimal strategies may not exist, and epsilon-optimal strategies (which achieve the value of the game within a parameter epsilon > 0) require in general both randomization and infinite memory. Hence our proof must rely on a more detailed analysis of strategies and, in addition to the main result, yields two results that are interesting on their own. First, we show that there exist epsilon-optimal strategies that in the limit coincide with memoryless strategies; this parallels the celebrated result of Mertens-Neyman for concurrent games with limit-average objectives. Second, we complete the characterization of the memory requirements for epsilon-optimal strategies for concurrent games with parity conditions, by showing that memoryless strategies suffice for epsilon-optimality for coBachi conditions.
AU - Krishnendu Chatterjee
AU - de Alfaro, Luca
AU - Thomas Henzinger
ID - 3890
TI - The complexity of quantitative concurrent parity games
ER -
TY - CONF
AB - We study infinite stochastic games played by two-players over a finite state space, with objectives specified by sets of infinite traces. The games are concurrent (players make moves simultaneously and independently), stochastic (the next state is determined by a probability distribution that depends on the current state and chosen moves of the players) and infinite (proceeds for infinite number of rounds). The analysis of concurrent stochastic games can be classified into: quantitative analysis, analyzing the optimum value of the game; and qualitative analysis, analyzing the set of states with optimum value 1. We consider concurrent games with tail objectives, i.e., objectives that are independent of the finite-prefix of traces, and show that the class of tail objectives are strictly richer than the omega-regular objectives. We develop new proof techniques to extend several properties of concurrent games with omega-regular objectives to concurrent games with tail objectives. We prove the positive limit-one property for tail objectives, that states for all concurrent games if the optimum value for a player is positive for a tail objective Phi at some state, then there is a state where the optimum value is 1 for Phi, for the player. We also show that the optimum values of zero-sum (strictly conflicting objectives) games with tail objectives can be related to equilibrium values of nonzero-sum (not strictly conflicting objectives) games with simpler reachability objectives. A consequence of our analysis presents a polynomial time reduction of the quantitative analysis of tail objectives to the qualitative analysis for the sub-class of one-player stochastic games (Markov decision processes).
AU - Krishnendu Chatterjee
ID - 3891
TI - Concurrent games with tail objectives
VL - 4207
ER -
TY - JOUR
AB - It is commonly believed that both the average length and the frequency of microsatellites correlate with genome size. We have estimated the frequency and the average length for 69 perfect dinucleotide microsatellites in an insect with an exceptionally large genome: Chorthippus biguttulus (Orthoptera, Acrididae). Dinucleotide microsatellites are not more frequent in C. biguttulus, but repeat arrays are 1.4 to 2 times longer than in other insect species. The average repeat number in C. biguttulus lies in the range of higher vertebrates. Natural populations are highly variable. At least 30 alleles per locus were found and the expected heterozygosity is above 0.95 at all three loci studied. In contrast, the observed heterozygosity is much lower (≤0.51), which could be caused by long null alleles.
AU - Ustinova, Jana
AU - Achmann, Roland
AU - Cremer, Sylvia
AU - Mayer, Frieder
ID - 3908
IS - 2
JF - Journal of Molecular Evolution
TI - Long repeats in a huge gemome: microsatellite loci in the grasshopper Chorthippus biguttulus
VL - 62
ER -