Lasso Games

概要

We study games on finite graphs with labelled or weighted edges in which plays end as soon as the first loop is formed. The resulting play has a lasso shape: a path (head) followed by a cycle (loop). We consider two semantics for determining the winner: the loop semantics, where only the loop matters, and the lasso semantics, where the entire play is taken into account. We show that adopting the lasso semantics may have a dramatic impact on both the complexity of the game and the memory required to play optimally. Mean-payoff games with lasso semantics are no longer positionally determined, and the threshold problem – deciding whether the value of the game is at least 0 – is PSPACE-complete. In contrast, lasso parity games are equivalent to weak parity games, remain positionally determined and are solvable in polynomial time. Furthermore, we show that if a positionally determined winning objective is closed under cyclic permutation and both the objective and its complement are closed under concatenation, then it is equivalent to the parity objective. Finally, we consider mod-k games, where the winner depends on the length of the path modulo k >= 2. We show that these games, in both semantics, are PSPACE-complete. Alongside computational complexity, we analyze the memory required to play optimally. We establish that for any game positionally determined in loop semantics, memory of size 2^n is sufficient in lasso semantics. We complement this by showing exponential memory lower bounds for lasso mean-payoff and mod-k games.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Lasso Games

# 概要
We study games on finite graphs with labelled or weighted edges in which plays end as soon as the first loop is formed. The resulting play has a lasso shape: a path (head) followed by a cycle (loop).

# 原典
https://arxiv.org/abs/2610.15480

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。