The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games

Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus ORCID: 0000-0003-4783-0389 (2015) The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms.

Text finite.pdf - Submitted version Download (552kB)

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

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	06 Dec 2018 09:15
Last Modified:	07 Dec 2024 10:45
DOI:	10.1137/1.9781611973730.69
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3029584