Synthesis of Reward Machines for Multi-Agent Equilibrium Design (Full Version)

本文研究均衡设计这一概念，与机制设计密切相关但有所不同。与机制设计不同，均衡设计中设计者的权力更受限制，她只能修改给定游戏中的激励结构以实现某些结果，而无法从头开始创建游戏。我们使用称为奖励机器的动态激励结构来研究均衡设计问题。我们使用加权并发游戏结构作为游戏模型，以平均回报目标定义目标（对于玩家和设计者）。我们展示了如何使用奖励机器来表示动态激励，以分配奖励以优化设计者的目标。我们还介绍了我们框架内的主要决策问题——回报改进问题。这个问题实际上是问是否存在一种动态激励（由某些奖励机器表示），可以将设计者的回报提高超过给定的阈值。我们提出了问题的两个变体：强和弱。我们证明了这两个问题都可以使用配备NP预言机的图灵机在多项式时间内解决。此外，我们还证明了这些变体要么是NP难的，要么是coNP难的。最后，我们展示了如何合成相应的奖励机器，如果存在的话。

论文研究的问题是什么是如何在现有的游戏中修改激励结构以实现特定目标，同时优化设计者的收益。这是一个新问题。

论文提出了使用动态激励结构（奖励机器）来实现均值回报目标的加权并发博弈结构，并解决了与之相关的决策问题。论文的关键思路是使用奖励机器来表示动态激励，以实现设计者的目标。

论文在实验中使用了多个数据集，并使用开源代码进行了实现。此外，论文还解决了与奖励机器相关的决策问题，并证明了这些问题的复杂性。该研究可用于游戏设计和人工智能系统的设计。

最近的相关研究包括《机制设计》和《博弈论》，这些研究关注如何设计游戏来实现特定目标。另外，《强化学习》和《深度学习》也是该领域的相关研究方向。