---
_id: '475'
abstract:
- lang: eng
  text: 'First cycle games (FCG) are played on a finite graph by two players who push
    a token along the edges until a vertex is repeated, and a simple cycle is formed.
    The winner is determined by some fixed property Y of the sequence of labels of
    the edges (or nodes) forming this cycle. These games are traditionally of interest
    because of their connection with infinite-duration games such as parity and mean-payoff
    games. We study the memory requirements for winning strategies of FCGs and certain
    associated infinite duration games. We exhibit a simple FCG that is not memoryless
    determined (this corrects a mistake in Memoryless determinacy of parity and mean
    payoff games: a simple proof by Bj⋯orklund, Sandberg, Vorobyov (2004) that claims
    that FCGs for which Y is closed under cyclic permutations are memoryless determined).
    We show that θ (n)! memory (where n is the number of nodes in the graph), which
    is always sufficient, may be necessary to win some FCGs. On the other hand, we
    identify easy to check conditions on Y (i.e., Y is closed under cyclic permutations,
    and both Y and its complement are closed under concatenation) that are sufficient
    to ensure that the corresponding FCGs and their associated infinite duration games
    are memoryless determined. We demonstrate that many games considered in the literature,
    such as mean-payoff, parity, energy, etc., satisfy these conditions. On the complexity
    side, we show (for efficiently computable Y) that while solving FCGs is in PSPACE,
    solving some families of FCGs is PSPACE-hard. '
alternative_title:
- EPTCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Benjamin
  full_name: Aminof, Benjamin
  id: 4A55BD00-F248-11E8-B48F-1D18A9856A87
  last_name: Aminof
- first_name: Sasha
  full_name: Rubin, Sasha
  id: 2EC51194-F248-11E8-B48F-1D18A9856A87
  last_name: Rubin
citation:
  ama: 'Aminof B, Rubin S. First cycle games. In: <i>Electronic Proceedings in Theoretical
    Computer Science, EPTCS</i>. Vol 146. Open Publishing Association; 2014:83-90.
    doi:<a href="https://doi.org/10.4204/EPTCS.146.11">10.4204/EPTCS.146.11</a>'
  apa: 'Aminof, B., &#38; Rubin, S. (2014). First cycle games. In <i>Electronic Proceedings
    in Theoretical Computer Science, EPTCS</i> (Vol. 146, pp. 83–90). Grenoble, France:
    Open Publishing Association. <a href="https://doi.org/10.4204/EPTCS.146.11">https://doi.org/10.4204/EPTCS.146.11</a>'
  chicago: Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” In <i>Electronic
    Proceedings in Theoretical Computer Science, EPTCS</i>, 146:83–90. Open Publishing
    Association, 2014. <a href="https://doi.org/10.4204/EPTCS.146.11">https://doi.org/10.4204/EPTCS.146.11</a>.
  ieee: B. Aminof and S. Rubin, “First cycle games,” in <i>Electronic Proceedings
    in Theoretical Computer Science, EPTCS</i>, Grenoble, France, 2014, vol. 146,
    pp. 83–90.
  ista: 'Aminof B, Rubin S. 2014. First cycle games. Electronic Proceedings in Theoretical
    Computer Science, EPTCS. SR: Strategic Reasoning, EPTCS, vol. 146, 83–90.'
  mla: Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” <i>Electronic Proceedings
    in Theoretical Computer Science, EPTCS</i>, vol. 146, Open Publishing Association,
    2014, pp. 83–90, doi:<a href="https://doi.org/10.4204/EPTCS.146.11">10.4204/EPTCS.146.11</a>.
  short: B. Aminof, S. Rubin, in:, Electronic Proceedings in Theoretical Computer
    Science, EPTCS, Open Publishing Association, 2014, pp. 83–90.
conference:
  end_date: 2014-04-06
  location: Grenoble, France
  name: 'SR: Strategic Reasoning'
  start_date: 2014-04-05
corr_author: '1'
date_created: 2018-12-11T11:46:41Z
date_published: 2014-04-01T00:00:00Z
date_updated: 2025-04-14T13:51:05Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.4204/EPTCS.146.11
ec_funded: 1
external_id:
  arxiv:
  - '1404.0843'
file:
- access_level: open_access
  checksum: 4d7b4ab82980cca2b96ac7703992a8c8
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:17:08Z
  date_updated: 2020-07-14T12:46:35Z
  file_id: '5260'
  file_name: IST-2018-952-v1+1_2014_Rubin_First_cycle.pdf
  file_size: 100115
  relation: main_file
file_date_updated: 2020-07-14T12:46:35Z
has_accepted_license: '1'
intvolume: '       146'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 83 - 90
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11402-N23
  name: Moderne Concurrency Paradigms
- _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: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
publication: Electronic Proceedings in Theoretical Computer Science, EPTCS
publication_status: published
publisher: Open Publishing Association
publist_id: '7345'
pubrep_id: '952'
quality_controlled: '1'
scopus_import: '1'
status: public
title: First cycle games
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 146
year: '2014'
...