---
_id: '10796'
abstract:
- lang: eng
  text: '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).'
acknowledgement: "The research was partly supported by FWF Grant No P 23499-N23, FWF
  NFN Grant\r\nNo S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft
  faculty fellows award."
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Rasmus
  full_name: Ibsen-Jensen, Rasmus
  id: 3B699956-F248-11E8-B48F-1D18A9856A87
  last_name: Ibsen-Jensen
  orcid: 0000-0003-4783-0389
citation:
  ama: 'Chatterjee K, Ibsen-Jensen R. The value 1 problem under finite-memory strategies
    for concurrent mean-payoff games. In: <i>Proceedings of the Twenty-Sixth Annual
    ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2015. SIAM; 2015:1018-1029.
    doi:<a href="https://doi.org/10.1137/1.9781611973730.69">10.1137/1.9781611973730.69</a>'
  apa: 'Chatterjee, K., &#38; Ibsen-Jensen, R. (2015). The value 1 problem under finite-memory
    strategies for concurrent mean-payoff games. In <i>Proceedings of the Twenty-Sixth
    Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2015, pp. 1018–1029).
    San Diego, CA, United States: SIAM. <a href="https://doi.org/10.1137/1.9781611973730.69">https://doi.org/10.1137/1.9781611973730.69</a>'
  chicago: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Value 1 Problem under
    Finite-Memory Strategies for Concurrent Mean-Payoff Games.” In <i>Proceedings
    of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2015:1018–29.
    SIAM, 2015. <a href="https://doi.org/10.1137/1.9781611973730.69">https://doi.org/10.1137/1.9781611973730.69</a>.
  ieee: K. Chatterjee and R. Ibsen-Jensen, “The value 1 problem under finite-memory
    strategies for concurrent mean-payoff games,” in <i>Proceedings of the Twenty-Sixth
    Annual ACM-SIAM Symposium on Discrete Algorithms</i>, San Diego, CA, United States,
    2015, vol. 2015, no. 1, pp. 1018–1029.
  ista: 'Chatterjee K, Ibsen-Jensen R. 2015. The value 1 problem under finite-memory
    strategies for concurrent mean-payoff games. Proceedings of the Twenty-Sixth Annual
    ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms
    vol. 2015, 1018–1029.'
  mla: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Value 1 Problem under
    Finite-Memory Strategies for Concurrent Mean-Payoff Games.” <i>Proceedings of
    the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2015,
    no. 1, SIAM, 2015, pp. 1018–29, doi:<a href="https://doi.org/10.1137/1.9781611973730.69">10.1137/1.9781611973730.69</a>.
  short: K. Chatterjee, R. Ibsen-Jensen, in:, Proceedings of the Twenty-Sixth Annual
    ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2015, pp. 1018–1029.
conference:
  end_date: 2015-01-06
  location: San Diego, CA, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2015-01-04
date_created: 2022-02-25T12:18:43Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2022-02-25T12:33:32Z
day: '01'
department:
- _id: KrCh
doi: 10.1137/1.9781611973730.69
ec_funded: 1
external_id:
  arxiv:
  - '1409.6690'
intvolume: '      2015'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: Preprint
page: 1018-1029
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
  name: Microsoft Research Faculty Fellowship
publication: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete
  Algorithms
publication_identifier:
  isbn:
  - 978-161197374-7
publication_status: published
publisher: SIAM
quality_controlled: '1'
scopus_import: '1'
status: public
title: The value 1 problem under finite-memory strategies for concurrent mean-payoff
  games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2015
year: '2015'
...