Frederiksen, Søren Kristoffer Stiil^{2}; Miltersen, Peter Bro^{2}

Editor:

Parosh Aziz Abdulla, Igor Potapov

Affiliations:

^{1} Department of Computer Science, Science and Technology, Aarhus University^{2} Department of Computer Science, Science and Technology, Aarhus University

DOI:

10.1007/978-3-642-41036-9_12

Abstract:

We consider two-player zero-sum finite (but infinite-horizon) stochastic games with limiting average payoffs. We define a family of stationary strategies for Player I parameterized by ε > 0 to be monomial, if for each state k and each action j of Player I in state k except possibly one action, we have that the probability of playing j in k is given by an expression of the form c ε d for some non-negative real number c and some non-negative integer d. We show that for all games, there is a monomial family of stationary strategies that are ε-optimal among stationary strategies. A corollary is that all concurrent reachability games have a monomial family of ε-optimal strategies. This generalizes a classical result of de Alfaro, Henzinger and Kupferman who showed that this is the case for concurrent reachability games where all states have value 0 or 1.

ISBN:

9783642410352, 9783642410369

Type:

Conference paper

Language:

English

Published in:

Lecture Notes in Computer Science: 7th International Workshop, Rp 2013, Uppsala, Sweden, September 24-26, 2013 Proceedings, 2013, p. 122-134

Main Research Area:

Science/technology

Publication Status:

Published

Series:

Lecture Notes in Computer Science

Review type:

Peer Review

Conference:

International Workshop on Reachability Problems, 2013