Approachability in repeated games: Computational aspects and a Stackelberg variant

[摘要] We consider a finite two-player zero-sum game with vector-valued rewards. We study the question of whether a given polyhedral set D is ;;approachable,” that is, whether Player 1 (the ;;decision maker”) can guarantee that the long-term average reward belongs to D, for any strategy of Player 2 (the ;;adversary”). We examine Blackwell;;s necessary and sufficient conditions for approachability, and show that the problem of checking these conditions is NP-hard, even in the special case where D is a singleton. We then consider a Stackelberg variant whereby, at each stage, the adversary gets to act after observing the decision maker;;s action. We provide necessary and sufficient conditions for approachability, and again establish that checking these conditions is NP-hard, even when D is a singleton. On the other hand, if the dimension of the reward vector is fixed, an approximate version of these conditions can be checked in polynomial time.

[发布机构] Elsevier