并发随机B\"uchi博弈的策略复杂性

我们研究了可数图上的2名玩家并发随机B\"uchi博弈。两名玩家，Max和Min，分别寻求最大化和最小化无限次访问一组目标状态的概率。我们表明，总存在仅使用步骤计数器加1位公共内存的-最优Max策略。这个上界适用于所有可数图，但即使对于有限图的特殊情况也仍是一个新结果。这个上界是紧的，因为仅使用步骤计数器或仅使用有限内存的Max策略即使在有限博弈图上也不是充分的。这个上界是稍强的新结果的结果：对于组合B\"uchi和瞬态目标的-最优Max策略仅需要1位公共内存（但不能是无内存的）。我们的证明技术还产生了一个相关的结果，即仅针对瞬态目标的-最优Max策略（在无限图中才有意义）可以是无内存的。