Diversified Strategies for Mitigating Adversarial Attacks in Multiagent Systems
Diversified Strategies for Mitigating Adversarial Attacks in Multiagent Systems
复制标题
DOI：
10.5555/3237383.3237446
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Maria-Florina Balcan;Avrim Blum;Shang-Tse Chen
中科院分区：
文献类型：
--
作者：
Maria-Florina Balcan;Avrim Blum;Shang-Tse Chen
在这项工作中，我们考虑在线决策的设置，玩家要防范可能的对抗性攻击或其他灾难性的失败。为了解决这个问题，我们提出了一个解决方案的概念，其中玩家有一个额外的约束，在每个时间步，他们必须发挥\em多元化的混合策略：一个不把太多的重量在任何一个行动。这种约束的动机是金融、路由和资源分配等应用程序，在这些应用程序中，人们希望限制自己对对抗性或灾难性事件的暴露，同时在典型情况下仍然表现良好。我们探索了零和和一般和游戏中多元化策略的属性，并提供了在多元化策略家族中最小化后悔的算法，以及使用税收或费用来引导标准后悔最小化玩家走向多元化策略的方法。我们还分析了一般和博弈中多样化策略产生的均衡。我们发现，令人惊讶的是，要求多样化实际上可以导致更高的福利均衡，并给予强有力的保证，无政府状态的价格和社会福利所产生的遗憾最小化多元化代理。我们还给出了算法，在分布式环境中，必须限制通信开销找到最佳的多样化的策略。
In this work we consider online decision-making in settings where players want to guard against possible adversarial attacks or other catastrophic failures. To address this, we propose a solution concept in which players have an additional constraint that at each time step they must play a \em diversified mixed strategy: one that does not put too much weight on any one action. This constraint is motivated by applications such as finance, routing, and resource allocation, where one would like to limit one's exposure to adversarial or catastrophic events while still performing well in typical cases. We explore properties of diversified strategies in both zero-sum and general-sum games, and provide algorithms for minimizing regret within the family of diversified strategies as well as methods for using taxes or fees to guide standard regret-minimizing players towards diversified strategies. We also analyze equilibria produced by diversified strategies in general-sum games. We show that surprisingly, requiring diversification can actually lead to higher-welfare equilibria, and give strong guarantees on both price of anarchy and the social welfare produced by regret-minimizing diversified agents. We additionally give algorithms for finding optimal diversified strategies in distributed settings where one must limit communication overhead.