First-cycle games

DOI10.1016/J.IC.2016.10.008zbMATH Open1371.91019arXiv1404.0843OpenAlexW2963607100WikidataQ58105341 ScholiaQ58105341MaRDI QIDQ528186FDOQ528186

Authors: Benjamin Aminof, Sasha Rubin 

Publication date: 12 May 2017

Published in: Information and Computation (Search for Journal in Brave)

Abstract: 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 it 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 /Theta(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.

Full work available at URL: https://arxiv.org/abs/1404.0843

Recommendations

• scientific article; zbMATH DE number 7361821
• Memoryless determinacy of parity and mean payoff games: a simple proof
• Infinite games played on finite graphs
• Memoryless determinacy of infinite parity games: another simple proof
• Infinite games on finitely coloured graphs with applications to automata on infinite trees

zbMATH Keywords

parity gamesenergy gamesmean-payoff gamesgraph gamescycle gamesmemoryless determinacy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• The complexity of mean payoff games on graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Positional strategies for mean payoff games
• Memoryless determinacy of parity and mean payoff games: a simple proof
• DAG-Width and Parity Games
• Alternating traps in Muller and parity games
• Energy parity games
• Half-Positional Determinacy of Infinite Games
• Title not available (Why is that?)
• CONCUR 2005 – Concurrency Theory
• Exploring the boundary of half-positionality

Cited In (16)

• Bounded game-theoretic semantics for modal mu-calculus
• Title not available (Why is that?)
• Title not available (Why is that?)
• Average-energy games
• Half-positional objectives recognized by deterministic Büchi automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal supervisory control with mean payoff objectives and under partial observation
• An Achievement Game on a Cycle
• Title not available (Why is that?)
• Title not available (Why is that?)
• Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints
• Title not available (Why is that?)
• Reactive synthesis without regret

This page was built for publication: First-cycle games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528186)