---
_id: '4422'
abstract:
- lang: eng
  text: "Behavioral properties of open systems can be formalized as objectives in
    two-player games. Turn-based games model asynchronous interaction between the
    players (the system and its environment) by interleaving their moves. Concurrent
    games model synchronous interaction: the players always move simultaneously. Infinitary
    winning criteria are considered: Büchi, co-Büchi, and more general parity conditions.
    A generalization of determinacy for parity games to concurrent parity games demands
    probabilistic (mixed) strategies: either player 1 has a mixed strategy to win
    with probability 1 (almost-sure winning), or player 2 has a mixed strategy to
    win with positive probability.\r\nThis work provides efficient reductions of concurrent
    probabilistic Büchi and co-Büchi games to turn-based games with Büchi condition
    and parity winning condition with three priorities, respectively. From a theoretical
    point of view, the latter reduction shows that one can trade the probabilistic
    nature of almost-sure winning for a more general parity (fairness) condition.
    The reductions improve understanding of concurrent games and provide an alternative
    simple proof of determinacy of concurrent Büchi and co-Büchi games. From a practical
    point of view, the reductions turn solvers of turn-based games into solvers of
    concurrent probabilistic games. Thus improvements in the well-studied algorithms
    for the former carry over immediately to the latter. In particular, a recent improvement
    in the complexity of solving turn-based parity games yields an improvement in
    time complexity of solving concurrent probabilistic co-Büchi games from cubic
    to quadratic."
acknowledgement: This research was supported in part by the Polish KBN grant 7-T11C-027-20,
  the AFOSR MURI grant F49620-00-1-0327, and the NSF Theory grant CCR-9988172.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Marcin
  full_name: Jurdziński, Marcin
  last_name: Jurdziński
- first_name: Orna
  full_name: Kupferman, Orna
  last_name: Kupferman
- 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: 'Jurdziński M, Kupferman O, Henzinger TA. Trading probability for fairness.
    In: <i>Proceedings of the 16th International Workshop on Computer Science Logic</i>.
    Vol 2471. Springer; 2002:292-305. doi:<a href="https://doi.org/10.1007/3-540-45793-3_20">10.1007/3-540-45793-3_20</a>'
  apa: 'Jurdziński, M., Kupferman, O., &#38; Henzinger, T. A. (2002). Trading probability
    for fairness. In <i>Proceedings of the 16th International Workshop on Computer
    Science Logic</i> (Vol. 2471, pp. 292–305). Edinburgh, Scotland: Springer. <a
    href="https://doi.org/10.1007/3-540-45793-3_20">https://doi.org/10.1007/3-540-45793-3_20</a>'
  chicago: Jurdziński, Marcin, Orna Kupferman, and Thomas A Henzinger. “Trading Probability
    for Fairness.” In <i>Proceedings of the 16th International Workshop on Computer
    Science Logic</i>, 2471:292–305. Springer, 2002. <a href="https://doi.org/10.1007/3-540-45793-3_20">https://doi.org/10.1007/3-540-45793-3_20</a>.
  ieee: M. Jurdziński, O. Kupferman, and T. A. Henzinger, “Trading probability for
    fairness,” in <i>Proceedings of the 16th International Workshop on Computer Science
    Logic</i>, Edinburgh, Scotland, 2002, vol. 2471, pp. 292–305.
  ista: 'Jurdziński M, Kupferman O, Henzinger TA. 2002. Trading probability for fairness.
    Proceedings of the 16th International Workshop on Computer Science Logic. CSL:
    Computer Science Logic, LNCS, vol. 2471, 292–305.'
  mla: Jurdziński, Marcin, et al. “Trading Probability for Fairness.” <i>Proceedings
    of the 16th International Workshop on Computer Science Logic</i>, vol. 2471, Springer,
    2002, pp. 292–305, doi:<a href="https://doi.org/10.1007/3-540-45793-3_20">10.1007/3-540-45793-3_20</a>.
  short: M. Jurdziński, O. Kupferman, T.A. Henzinger, in:, Proceedings of the 16th
    International Workshop on Computer Science Logic, Springer, 2002, pp. 292–305.
conference:
  location: Edinburgh, Scotland
  name: 'CSL: Computer Science Logic'
date_created: 2018-12-11T12:08:46Z
date_published: 2002-09-09T00:00:00Z
date_updated: 2023-06-05T10:02:54Z
day: '09'
doi: 10.1007/3-540-45793-3_20
extern: '1'
intvolume: '      2471'
language:
- iso: eng
month: '09'
oa_version: None
page: 292 - 305
publication: Proceedings of the 16th International Workshop on Computer Science Logic
publication_identifier:
  isbn:
  - '9783540442400'
publication_status: published
publisher: Springer
publist_id: '308'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Trading probability for fairness
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2471
year: '2002'
...