论文标题
游戏实施：什么是障碍？
Game Implementation: What Are the Obstructions?
论文作者
论文摘要
在许多应用中，我们希望通过为其行动设计激励措施来影响独立代理的决策。我们在该领域重新审视一个称为游戏实施的基本问题：以标准形式和一系列理想的策略给定游戏，我们是否可以设计一套付款承诺，以便如果玩家考虑了付款承诺，那么所有未主导的策略都需要？此外，我们的目标是最大程度地减少成本，即最差的付款量。 我们研究了计算此类付款承诺的障碍，并更接近地确定我们可能要克服的障碍。我们表明，即使对于两个玩家来说，游戏实施也是NP-HARD，特别是解决一个长期的开放问题（Eidenbenz等人，2011年），并提出需要更多的限制来获得障碍结果。因此，我们研究了玩家只有少数恒定策略并获得以下策略的制度。首先，即使每个玩家的实用程序仅取决于另外三个，这种情况仍然是NP-HARD。其次，我们修复了少量策略和少量玩家的情况下的有缺陷的有效算法。在进一步的结果中，我们表征了一组所需的策略，这些策略可以零成本作为游戏的稳定核心。
In many applications, we want to influence the decisions of independent agents by designing incentives for their actions. We revisit a fundamental problem in this area, called GAME IMPLEMENTATION: Given a game in standard form and a set of desired strategies, can we design a set of payment promises such that if the players take the payment promises into account, then all undominated strategies are desired? Furthermore, we aim to minimize the cost, that is, the worst-case amount of payments. We study the tractability of computing such payment promises and determine more closely what obstructions we may have to overcome in doing so. We show that GAME IMPLEMENTATION is NP-hard even for two players, solving in particular a long open question (Eidenbenz et al. 2011) and suggesting more restrictions are necessary to obtain tractability results. We thus study the regime in which players have only a small constant number of strategies and obtain the following. First, this case remains NP-hard even if each player's utility depends only on three others. Second, we repair a flawed efficient algorithm for the case of both small number of strategies and small number of players. Among further results, we characterize sets of desired strategies that can be implemented at zero cost as a kind of stable core of the game.
