Two-player mean-payoff Stackelberg games are nonzero-sum infinite duration games played on a bi-weighted graph by a leader (Player~0) and a follower (Player~1). Such games are played sequentially: first, the leader announces her strategy, second, the follower chooses his strategy. This pair of strategies defines a unique infinite path in the graph and both players receive their respective payoff computed as the mean of the rewards that they receive when traversing edges along the infinite path. As a consequence, if we assume that the follower is rational then we can deduce that the follower's response to the leader strategy is a strategy that maximizes his payoff against the strategy proposed by the leader; it is thus a best-response to this strategy. Knowing that, the leader should choose a strategy that maximizes the payoff that she receives when the follower chooses a best-response to her strategy. If we cannot impose which best-response is chosen by the follower, we say that the follower, though strategic, is \emph{adversarial} towards the leader. The maximal value that the leader can get in this nonzero-sum game is called the {\em adversarial Stackelberg value} of the game. First, we show that the nonzero-sum nature of the mean-payoff Stackelberg game makes it fragile against modelling imprecisions. This is in contrast with mean-payoff games in the zero-sum setting which are robust. Second, we show how robustness is recovered when considering $\epsilon$-best responses of the follower instead of best-responses only. This lead to the notion of $\epsilon$-adversarial Stackelberg value. Third, we provide algorithms to decide the threshold problem for this robust value as well as ways to compute it effectively. Finally, we characterize the memory needed by the strategies of the leader and the follower in these games.
翻译:双玩者平均报酬 Stackelberg 游戏是非零和无限的游戏, 由领导者( Player ~ 0) 和追随者( Player ~ 1) 在双加权的图表上播放。 这种游戏是依次播放的: 首先, 领导者宣布其策略, 第二, 追随者选择其策略。 这对图中定义了一个独特的无限路径, 两个玩家在沿着无限路径翻滚时得到的回报是他们各自得到的回报的平均值。 因此, 如果我们假设追随者是理性的, 然后我们可以推断, 追随者对游戏领导者战略的反应是一种战略, 使他对领导者提出的策略的回报最大化; 因此, 这是对这个策略的最佳反应。 领导者应该选择一个在追随者选择对她的策略做出最佳反应时得到的回报最大化。 如果我们不能将最佳反应强加给后续者, 我们说, 跟踪者, 虽然战略是正对冲的, 但是, 我们的后期反应, 也是对当前领导人来说, 最高级的数值, 也就是我们向前期的 。