Approachability in repeated games: Computational aspects and a Stackelberg variant
成果类型：
Article
署名作者：
Mannor, Shie; Tsitsiklis, John N.
署名单位：
Massachusetts Institute of Technology (MIT); McGill University
刊物名称：
GAMES AND ECONOMIC BEHAVIOR
ISSN/ISSBN：
0899-8256
DOI：
10.1016/j.geb.2008.03.008
发表日期：
2009
页码：
315-325
关键词：
摘要：
We consider a finite two-player zero-stun 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. (C) 2008 Elsevier Inc. All rights reserved.
来源URL：