無限持續博弈的普遍圖理論

我們引入了通用圖的概念，作為構造求解無限持續對策的算法的工具，如奇偶對策和平均收益對策。在第一部分中，我們發展了通用性圖的理論，主要有兩個目的:在不同最近引入的相關模型之間顯示等價性和歸一化結果，并對任何位置确定的目标構造泛型值疊代算法。在第二部分，我們給出了四個應用:奇偶博弈，平均收益博弈，以及它們的組合(以目标的分離形式)。對于這四種情況中的每一種，我們都建構算法，以達到或改進已知的時間和空間複雜性。

原文題目：The Theory of Universal Graphs for Infinite Duration Games

原文：We introduce the notion of universal graphs as a tool for constructing algorithms solving games of infinite duration such as parity games and mean payoff games. In the first part we develop the theory of universal graphs, with two goals: showing an equivalence and normalisation result between different recently introduced related models, and constructing generic value iteration algorithms for any positionally determined objective. In the second part we give four applications: to parity games, to mean payoff games, and to combinations of them (in the form of disjunctions of objectives). For each of these four cases we construct algorithms achieving or improving over the best known time and space complexity.

無限持續博弈的普遍圖理論.pdf