论文标题
分布式强大游戏的算法设计和近似分析
Algorithm design and approximation analysis on distributed robust game
论文作者
论文摘要
我们设计了一种分布式算法，以寻求具有不确定耦合约束的强大游戏的概括性纳什平衡。由于集合约束中参数的不确定性，我们旨在在最坏情况下找到广义的NASH平衡。但是，直接获得确切的平衡是具有挑战性的，因为参数来自一般凸集，该集合可能没有分析表达式或具有高维非线性。为了解决此问题，我们首先使用刻有多面的多面体近似参数集，并通过强大的优化将最坏情况下的近似问题转换为具有资源分配约束的扩展某些游戏。然后，我们为该游戏提出了一种分布式算法，并证明从算法获得的平衡诱导了原始游戏的$ε$纳什nash平衡，然后进行融合分析。此外，诉诸于度量空间以及对非线性扰动系统的分析，我们估计与$ε$相关的近似准确性，并指出影响$ε$准确性的因素。
We design a distributed algorithm to seek generalized Nash equilibria of a robust game with uncertain coupled constraints. Due to the uncertainty of parameters in set constraints, we aim to find a generalized Nash equilibrium in the worst case. However, it is challenging to obtain the exact equilibria directly because the parameters are from general convex sets, which may not have analytic expressions or are endowed with high-dimensional nonlinearities. To solve this problem, we first approximate parameter sets with inscribed polyhedrons, and transform the approximate problem in the worst case into an extended certain game with resource allocation constraints by robust optimization. Then we propose a distributed algorithm for this certain game and prove that an equilibrium obtained from the algorithm induces an $ε$-generalized Nash equilibrium of the original game, followed by convergence analysis. Moreover, resorting to the metric spaces and the analysis on nonlinear perturbed systems, we estimate the approximation accuracy related to $ε$ and point out the factors influencing the accuracy of $ε$.
