Utility Decoupling for Distributed Nash Equilibrium Seeking in Weakly Acyclic Games
针对有限动作集博弈的分布式纳什均衡求解问题，提出一种效用解耦方法，将原博弈重构为增广博弈，保留弱非循环性质，使多种全信息学习动力学转化为部分信息分布式求解动力学，并用颜色分配博弈验证有效性。
This article addresses the problem of distributed Nash equilibrium seeking over networks for games with finite action sets. Gradient-like and consensus-based methods commonly used for continuous action spaces fail to work for this case. To this end, we propose a utility decoupling method to reformulate the original game into an augmented game, which preserves the Nash equilibrium and weakly acyclic property, yet enjoys a utility coupling network the same as the communication network. In this way, a variety of full-information game-theoretic learning dynamics for the augmented game turns into partial-information Nash equilibrium seeking dynamics for the original game. We proceed to apply the developed utility decoupling method to formulate three types of distributed Nash equilibrium seeking dynamics, including distributed best-response dynamics, distributed fictitious play, and distributed regret matching for weakly acyclic games. In the last, a typical color assignment game is utilized to empirically illustrate the validity and effectiveness of our approach.