Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus
(2013)
*Qualitative Analysis of Concurrent Mean-payoff Games.*
Technical Report.
IST Austria.

Text
soda_full.pdf - Published Version Available under License All rights reserved. [IST-2013-126-v1+1] Download (276Kb) |

## 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.

Item Type: | Monograph (Technical Report) |
---|---|

Subjects: | 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data |

Research Group: | Chatterjee Group |

Depositing User: | Prof Krishnendu Chatterjee |

Date Deposited: | 08 Jul 2013 08:30 |

Last Modified: | 15 Jul 2019 14:45 |

URI: | https://repository.ist.ac.at/id/eprint/126 |

### Actions (login required)

View Item |