---
OA_type: closed access
_id: '4555'
abstract:
- lang: eng
  text: Strategies in repeated games can be classified as to whether or not they use
    memory and/or randomization. We consider Markov decision processes and 2-player
    graph games, both of the deterministic and probabilistic varieties. We characterize
    when memory and/or randomization are required for winning with respect to various
    classes of w-regular objectives, noting particularly when the use of memory can
    be traded for the use of randomization. In particular, we show that Markov decision
    processes allow randomized memoryless optimal strategies for all M?ller objectives.
    Furthermore, we show that 2-player probabilistic graph games allow randomized
    memoryless strategies for winning with probability 1 those M?ller objectives which
    are upward-closed. Upward-closure means that if a set α of infinitely repeating
    vertices is winning, then all supersets of α are also winning.
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Luca
  full_name: De Alfaro, Luca
  last_name: De Alfaro
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  ama: 'Chatterjee K, De Alfaro L, Henzinger TA. Trading memory for randomness. In:
    IEEE; 2004:206-217. doi:<a href="https://doi.org/10.1109/QEST.2004.10051">10.1109/QEST.2004.10051</a>'
  apa: 'Chatterjee, K., De Alfaro, L., &#38; Henzinger, T. A. (2004). Trading memory
    for randomness (pp. 206–217). Presented at the QEST: Quantitative Evaluation of
    Systems, Enschede, Netherlands: IEEE. <a href="https://doi.org/10.1109/QEST.2004.10051">https://doi.org/10.1109/QEST.2004.10051</a>'
  chicago: Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “Trading
    Memory for Randomness,” 206–17. IEEE, 2004. <a href="https://doi.org/10.1109/QEST.2004.10051">https://doi.org/10.1109/QEST.2004.10051</a>.
  ieee: 'K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “Trading memory for randomness,”
    presented at the QEST: Quantitative Evaluation of Systems, Enschede, Netherlands,
    2004, pp. 206–217.'
  ista: 'Chatterjee K, De Alfaro L, Henzinger TA. 2004. Trading memory for randomness.
    QEST: Quantitative Evaluation of Systems, 206–217.'
  mla: Chatterjee, Krishnendu, et al. <i>Trading Memory for Randomness</i>. IEEE,
    2004, pp. 206–17, doi:<a href="https://doi.org/10.1109/QEST.2004.10051">10.1109/QEST.2004.10051</a>.
  short: K. Chatterjee, L. De Alfaro, T.A. Henzinger, in:, IEEE, 2004, pp. 206–217.
conference:
  end_date: 2004-09-30
  location: Enschede, Netherlands
  name: 'QEST: Quantitative Evaluation of Systems'
  start_date: 2004-09-27
date_created: 2018-12-11T12:09:27Z
date_published: 2004-09-30T00:00:00Z
date_updated: 2026-05-29T09:05:35Z
day: '30'
doi: 10.1109/QEST.2004.10051
extern: '1'
fulldoi: https://doi.org/10.1109/QEST.2004.10051
language:
- iso: eng
month: '09'
oa_version: None
page: 206 - 217
publication_identifier:
  isbn:
  - '0769521851'
publication_status: published
publisher: IEEE
publist_id: '155'
quality_controlled: '1'
status: public
title: Trading memory for randomness
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2004'
...