# The value 1 problem for concurrent mean-payoff games

Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff games, IST Austria, 49p.

Download

IST-2014-191-v1+1_main_full.pdf
584.37 KB

*Technical Report*|

*Published*|

*English*

Department

Series Title

IST Austria Technical Report

Abstract

We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy).

Publishing Year

Date Published

2014-04-14

Page

49

ISSN

IST-REx-ID

### Cite this

Chatterjee K, Ibsen-Jensen R.

*The Value 1 Problem for Concurrent Mean-Payoff Games*. IST Austria; 2014. doi:10.15479/AT:IST-2014-191-v1-1Chatterjee, K., & Ibsen-Jensen, R. (2014).

*The value 1 problem for concurrent mean-payoff games*. IST Austria. https://doi.org/10.15479/AT:IST-2014-191-v1-1Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen.

*The Value 1 Problem for Concurrent Mean-Payoff Games*. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-191-v1-1.K. Chatterjee and R. Ibsen-Jensen,

*The value 1 problem for concurrent mean-payoff games*. IST Austria, 2014.Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen.

*The Value 1 Problem for Concurrent Mean-Payoff Games*. IST Austria, 2014, doi:10.15479/AT:IST-2014-191-v1-1.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Main File(s)**

File Name

IST-2014-191-v1+1_main_full.pdf
584.37 KB

Access Level

Open Access

Date Uploaded

2018-12-12

MD5 Checksum

49e0fd3e62650346daf7dc04604f7a0a