分布式博弈问题研究及算法设计

作     者：李松洋 

作者单位：西南大学 

学位级别：硕士

导师姓名：李华青

授予年度：2023年

学科分类：07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：非合作博弈 聚合博弈 广义纳什均衡 原始-对偶方法 近端算子 

摘      要：博弈论是研究决策者(也称为“玩家)行为的一门学科,主要研究在多个玩家互动时,他们的决策和结果。在博弈论中,每个玩家的决策会影响整个博弈的结果,而每个玩家又会受到其他玩家的决策影响。不少学者将博弈论运用到现实生活中,以解决实际面临的工程问题,如智能能源系统、交通管理等。纳什均衡是博弈论中的一个解决方案概念,是指在一个博弈中,如果每个玩家都采取了最优的策略,那么所有玩家的策略都是相互协调的,达到了一个平衡状态。广义纳什均衡是纳什均衡的一种扩展,是具有全局共享耦合约束的博弈模型的解决方案。这些全局约束将每个玩家的可行行动集耦合在一起,从而使得任何一个玩家都不再能够通过改变自己的策略来获得更高的收益。随着信息技术的高速发展,博弈模型中的玩家数量也逐渐增多,传统的集中式广义纳什均衡求解算法已经不能够及时处理大量的计算需求。因此具有更好及时性、扩展性和隐私保护的分布式求解算法逐渐成为现今的研究热点。在现有的研究基础上,本文分别针对一般非合作博弈和聚合博弈,提出了高可用性、高性能的分布式广义纳什均衡求解算法,研究内容主要分为以下三点:(1)本文提出了一种完全信息下基于边一致的求解广义纳什均衡的分布式算法。考虑到现有的基于原始-对偶方法求解非合作博弈模型的广义纳什均衡的分布式算法需要一个维度取决于玩家数量的拉普拉斯矩阵来保证对偶变量的一致性,这意味该类算法不适用于大规模网络。本文所提算法假设每个玩家都可以与所有玩家进行信息交流,且不需要构建额外的拉普拉斯矩阵。同时,考虑现有大部分研究都使用全局步长,即所有玩家使用相同的步长,这可能导致步长无法灵活设置。本文提出的分布式算法采用了依赖于邻居数量的局部恒定步长,这一设置使得算法的灵活性更高。(2)本文在部分信息设置下提出了一种基于边一致的求解广义纳什均衡的分布式算法。考虑到在更多实际应用中,一些玩家无法与所有其他玩家进行通信,本文为每个玩家引入了一个对所有玩家整体行动的局部估计,从而在博弈中的玩家仅需要与其邻居玩家进行通信即可。并且通过古诺博弈以及路径规划模型的仿真实验,本文进一步验证了部分信息下和完全信息下得到的的广义纳什均衡的一致性。(3)本文研究了带有耦合约束的平均聚合博弈,并基于近端算子设计了求解该类博弈模型的广义纳什均衡的分布式算法。为了分布式求解该博弈问题,本文为每个玩家引入了对于聚合项的局部估计,从而保证了玩家之间的相互独立。与部分信息设置下的算法不同,这种算法的优点在于局部估计不依赖于玩家数量,因此具有高效性和可扩展性。从应用的角度来看,这种算法更适用于大规模网络。同时,本文为局部估计引入了一致性子空间,从而保证了局部估计的一致性。最后,通过充电模型的仿真实验,证实了算法的正确性和实用性。综上所述,本文在已有的研究基础之上,针对现有研究的不足,基于原始对偶方法和近端算子理论设计了一系列求解博弈模型广义纳什均衡的分布式算法。本文的研究成果将进一步扩展博弈模型求解方法,为分布式博弈解决实际工程问题提供完整的理论支撑。