论文标题
结束:在部分决策信息下的游戏估算网络设计
The END: Estimation Network Design for games under partial-decision information
论文作者
论文摘要
多代理决策问题通常是通过分布式迭代算法解决的,在该算法中,代理只能在点对点网络上进行交流。每个代理通常都保留每个决策变量的副本,而本地副本之间的协议是通过共识协议执行的。然而,每个代理通常只受到决策变量的一小部分直接影响:忽略这种稀疏性会导致冗余,可扩展性差,网络大小,通信和内存开销。为了应对这些挑战,我们开发了估计网络设计(END),这是分布式算法设计和分析的框架,概括了最近的几种方法。可以调整末端算法,以利用问题特定的稀疏结构,通过仅将每个变量的副本分配到一部分代理,以提高效率并最小化冗余。我们通过设计针对部分决策信息寻求广义NASH平衡(GNE)的新算法来说明结局的潜力,从而可以利用成本函数,约束和聚合值的稀疏性。最后,我们在数值上测试我们的方法分配问题,揭示了沟通和记忆成本大大降低。
Multi-agent decision problems are typically solved via distributed iterative algorithms, where the agents only communicate between themselves on a peer-to-peer network. Each agent usually maintains a copy of each decision variable, while agreement among the local copies is enforced via consensus protocols. Yet, each agent is often directly influenced by a small portion of the decision variables only: neglecting this sparsity results in redundancy, poor scalability with the network size, communication and memory overhead. To address these challenges, we develop Estimation Network Design (END), a framework for the design and analysis of distributed algorithms, generalizing several recent approaches. END algorithms can be tuned to exploit problem-specific sparsity structures, by optimally allocating copies of each variable only to a subset of agents, to improve efficiency and minimize redundancy. We illustrate the END's potential by designing new algorithms for generalised Nash equilibrium (GNE) seeking under partial-decision information, that can leverage the sparsity in cost functions, constraints and aggregation values. Finally, we test numerically our methods on a unicast rate allocation problem, revealing greatly reduced communication and memory costs.