---
_id: '3856'
abstract:
- lang: eng
  text: 'We consider two-player zero-sum games on graphs. These games can be classified
    on the basis of the information of the players and on the mode of interaction
    between them. On the basis of information the classification is as follows: (a)
    partial-observation (both players have partial view of the game); (b) one-sided
    complete-observation (one player has complete observation); and (c) complete-observation
    (both players have complete view of the game). On the basis of mode of interaction
    we have the following classification: (a) concurrent (players interact simultaneously);
    and (b) turn-based (players interact in turn). The two sources of randomness in
    these games are randomness in transition function and randomness in strategies.
    In general, randomized strategies are more powerful than deterministic strategies,
    and randomness in transitions gives more general classes of games. We present
    a complete characterization for the classes of games where randomness is not helpful
    in: (a) the transition function (probabilistic transition can be simulated by
    deterministic transition); and (b) strategies (pure strategies are as powerful
    as randomized strategies). As consequence of our characterization we obtain new
    undecidability results for these games. '
acknowledgement: This research was supported by the European Union project COMBEST
  and the European Network of Excellence ArtistDesign.
alternative_title:
- LNCS
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: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
- first_name: Hugo
  full_name: Gimbert, Hugo
  last_name: Gimbert
- 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, Doyen L, Gimbert H, Henzinger TA. Randomness for free. In: Vol
    6281. Springer; 2010:246-257. doi:<a href="https://doi.org/10.1007/978-3-642-15155-2_23">10.1007/978-3-642-15155-2_23</a>'
  apa: 'Chatterjee, K., Doyen, L., Gimbert, H., &#38; Henzinger, T. A. (2010). Randomness
    for free (Vol. 6281, pp. 246–257). Presented at the MFCS: Mathematical Foundations
    of Computer Science, Brno, Czech Republic: Springer. <a href="https://doi.org/10.1007/978-3-642-15155-2_23">https://doi.org/10.1007/978-3-642-15155-2_23</a>'
  chicago: Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Thomas A Henzinger.
    “Randomness for Free,” 6281:246–57. Springer, 2010. <a href="https://doi.org/10.1007/978-3-642-15155-2_23">https://doi.org/10.1007/978-3-642-15155-2_23</a>.
  ieee: 'K. Chatterjee, L. Doyen, H. Gimbert, and T. A. Henzinger, “Randomness for
    free,” presented at the MFCS: Mathematical Foundations of Computer Science, Brno,
    Czech Republic, 2010, vol. 6281, pp. 246–257.'
  ista: 'Chatterjee K, Doyen L, Gimbert H, Henzinger TA. 2010. Randomness for free.
    MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 6281, 246–257.'
  mla: Chatterjee, Krishnendu, et al. <i>Randomness for Free</i>. Vol. 6281, Springer,
    2010, pp. 246–57, doi:<a href="https://doi.org/10.1007/978-3-642-15155-2_23">10.1007/978-3-642-15155-2_23</a>.
  short: K. Chatterjee, L. Doyen, H. Gimbert, T.A. Henzinger, in:, Springer, 2010,
    pp. 246–257.
conference:
  end_date: 2010-08-27
  location: Brno, Czech Republic
  name: 'MFCS: Mathematical Foundations of Computer Science'
  start_date: 2010-08-23
corr_author: '1'
date_created: 2018-12-11T12:05:32Z
date_published: 2010-09-06T00:00:00Z
date_updated: 2025-09-23T10:32:00Z
day: '06'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-642-15155-2_23
ec_funded: 1
external_id:
  arxiv:
  - '1006.0673'
fulldoi: https://doi.org/10.1007/978-3-642-15155-2_23
intvolume: '      6281'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1006.0673
month: '09'
oa: 1
oa_version: Preprint
page: 246 - 257
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '215543'
  name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '214373'
  name: Design for Embedded Systems
publication_status: published
publisher: Springer
publist_id: '2325'
pubrep_id: '60'
quality_controlled: '1'
related_material:
  record:
  - id: '1731'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Randomness for free
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6281
year: '2010'
...