论文链接：https://proceedings.neurips.cc/paper/2020/file/5763abe87ed1938799203fb6e8650025-Paper.pdf

论文摘要：

在多智能体系统理论中，有一个值得称赞的结果，即简单、不耦合的无遗憾（no-regret）动态在常规形式的博弈中收敛到相关的均衡中。具体地说，这个结果已经有20多年的历史了。当所有玩家都试图在重复的常规形式博弈中最大程度地减少其内部遗憾（internal regret ）时，博弈的经验频率会收敛至常规形式的相关平衡。广义形式的博弈（即树状形式的博弈）通过对顺序移动（sequential move）、同时移动（simultaneous move）以及私人信息进行建模来泛化常规形式的博弈。

由于博弈的顺序性质，以及部分信息的存在，广义形式的关联与常规形式的关联相比，具有显着不同的属性，其中许多仍然是开放的研究方向。广义形式的相关均衡（Extensive-form correlated equilibrium，EFCE）已被提议为常规形式的相关均衡的自然广义对应。但是，目前尚不知道EFCE是不是由于未耦合的智能体动态而产生的。

在本文中，我们给出了第一个解耦的无遗憾动态，该动态收敛到具有完美召回作用的n玩家一般和（general-sum）广泛形式博弈中的EFCE集。

首先，我们在广义形式的博弈中引入触发遗憾（trigger regret）的概念，从而扩展了在常规形式的博弈中内部遗憾的概念。当每个玩家的触发遗憾低时，经验的博弈频率接近EFCE。然后，我们给出了一种有效的无触发遗憾算法。我们的算法将触发遗憾在每个决策点分解为玩家的局部子问题，并根据每个决策点的局部解构造玩家的全局策略。

获奖理由：

相关均衡（correlated equilibria，CE）容易计算，对社会的帮助比常见的纳什均衡（Nash equilibria）大很多。在许多博弈中，CE都展示了一个令人惊讶的性能：可以通过简单且分散的算法将所谓的内部遗憾降到最低，从而找到CE。

这篇论文表明，在大规模博弈中，即广义（或树型）博弈中，确实存在能够将遗憾降到最低的、收敛到CE的算法。

论文结果通过博弈论、计算机科学和经济学的交叉解决了一个长期存在的开放性问题，并且对涉及调解器的博弈具有潜在的巨大影响，比如通过导航app有效规划交通路线。

2 时间检验奖

获奖论文：《HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent》.