Stackelberg Mean-payoff Games with a Rationally Bounded Adversarial Follower
share
Two-player Stackelberg games are non-zero sum strategic games between 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, and then both players receive their respective payoff which is a function of the two strategies. The function that maps strategies to pairs of payoffs is known by the two players. As a consequence, if we assume that the follower is perfectly rational then we can deduce that the follower responds by playing a so-called best-response to the strategy of the leader in order to maximise his own payoff. In turn, the leader should choose a strategy that maximizes the value 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 setting is adversarial. However, sometimes, a more realistic assumption is to consider that the follower has only bounded rationality: the follower responds with one of his ϵ-best responses, for some fixed ϵ > 0. In this paper, we study the ϵ-optimal Adversarial Stackelberg Value, ASV^ϵ for short, which is the value that the leader can obtain against any ϵ-best response of a rationally bounded adversarial follower. The ASV^ϵ of Player 0 is the supremum of the values that Player 0 can obtain by announcing her strategy to Player 1 who in turn responds with an ϵ-optimal strategy. We consider the setting of infinite duration games played on graphs with mean-payoff objectives.
READ FULL TEXT