---
res:
bibo_abstract:
- 'We consider concurrent games played by two-players on a finite state graph, where
in every round the players simultaneously choose a move, and the current state
along with the joint moves determine the successor state. We study the most fundamental
objective for concurrent games, namely, mean-payoff or limit-average objective,
where a reward is associated to every transition, and the goal of player 1 is
to maximize the long-run average of the rewards, and the objective of player 2
is strictly the opposite (i.e., the games are zero-sum). The path constraint for
player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or
arbitrarily close to it; or quantitative, i.e., a given threshold between the
minimal and maximal reward. We consider the computation of the almost-sure (resp.
positive) winning sets, where player 1 can ensure that the path constraint is
satisfied with probability 1 (resp. positive probability). Almost-sure winning
with qualitative constraint exactly corresponds to the question whether there
exists a strategy to ensure that the payoff is the maximal reward of the game.
Our main results for qualitative path constraints are as follows: (1) we establish
qualitative determinacy results that show for every state either player 1 has
a strategy to ensure almost-sure (resp. positive) winning against all player-2
strategies or player 2 has a spoiling strategy to falsify almost-sure (resp. positive)
winning against all player-1 strategies; (2) we present optimal strategy complexity
results that precisely characterize the classes of strategies required for almost-sure
and positive winning for both players; and (3) we present quadratic time algorithms
to compute the almost-sure and the positive winning sets, matching the best known
bound of the algorithms for much simpler problems (such as reachability objectives).
For quantitative constraints we show that a polynomial time solution for the almost-sure
or the positive winning set would imply a solution to a long-standing open problem
(of solving the value problem of mean-payoff games) that is not known to be in
polynomial time.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Rasmus
foaf_name: Ibsen-Jensen, Rasmus
foaf_surname: Ibsen-Jensen
foaf_workInfoHomepage: http://www.librecat.org/personId=3B699956-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0003-4783-0389
bibo_doi: 10.15479/AT:IST-2013-126-v1-1
dct_date: 2013^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/2664-1690
dct_language: eng
dct_publisher: IST Austria@
dct_title: Qualitative analysis of concurrent mean-payoff games@
...