We study two natural problems about rational behaviors in multiplayer non-zero-sum sequential infinite duration games played on graphs: checking problems, that consist in deciding whether a strategy profile, defined by a Mealy machine, is rational; and rational verification, that consists in deciding whether all the rational answers to a given strategy satisfy some specification. We give the complexities of those problems for two major concepts of rationality: Nash equilibria and subgame-perfect equilibria, and for five major classes of payoff functions: parity, mean-payoff, quantitative reachability, energy, and discounted-sum.
翻译:我们研究了在图表上玩的多玩者非零和连续无限持续游戏中理性行为的两个自然问题:检查问题,即确定由米利机器定义的战略概况是否合理;以及合理核查,即决定特定战略的所有合理答案是否都满足某些要求;我们给出了这些问题的复杂性,以说明两个主要的合理性概念:纳什平衡和次游戏完美平衡,以及五大类的补偿功能:对等、平均偿还、数量可达性、能量和折扣总和。