一种基于机器学习的随机矩阵博弈求解方法

《Journal of Computational Science》：A machine learning-based solution method for stochastic matrix games

　　穆拉特·厄兹卡亚，恰纳卡莱18三月大学政治科学学院商业系，土耳其恰纳卡莱

摘要：随机矩阵博弈是一类重要的随机博弈，它通过引入状态依赖的态转移机制来扩展传统矩阵博弈。然而，由于需要求解高阶方程或进行计算成本高昂的迭代运算，针对随机矩阵博弈的分析与数值解法往往不切实际。为克服这些难题，我们提出了一种全新的全连接神经网络架构，用于高效估算随机矩阵博弈的博弈值。研究中，我们分别为3×3、4×4和5×5规模的各类博弈随机生成了5×105个样本，并采用容差为10??的Shapley迭代法对其求解。随后，我们将这些随机矩阵博弈分解为确定性矩阵、随机矩阵和指示矩阵，以构建合适的训练数据集。接着，通过一种新的向量化处理方法将这些矩阵转换为向量形式，作为神经网络的输入。实验结果表明，所提出的神经网络能够高效且精确地估算3×3、4×4和5×5规模随机矩阵博弈的博弈值，平均误差分别为-0.0070、-0.0154和0.1060。我们还通过绝对平均误差、绝对中位数误差和均方根误差等指标评估了该模型在不同规模博弈中的性能。一旦模型训练完成，即可快速输出博弈值，相比传统迭代方法大幅降低了计算时间。因此，所提出的神经网络为解决随机矩阵博弈提供了高效的替代方案。

引言：博弈论是一种用于分析理性参与者之间战略互动的数学框架。它研究的是这样一种情形：某一方的行为不仅会影响自身的结果，还会影响其他参与者的 outcome。其中最重要的原理之一——极小极大定理，由冯·诺伊曼在1928年证明，为非合作博弈论奠定了基础[1]。1944年，冯·诺伊曼和摩根斯坦在《博弈论与经济行为》一书中正式介绍了博弈论，此后无论是从理论还是实践层面，关于该领域的研究都大幅增加。例如，纳什证明了在特定条件下博弈存在均衡点，即所谓的纳什均衡[3]。沙普利提出了随机博弈的概念，它是重复博弈和马尔可夫决策过程的推广形式[4]。艾萨克则提出了微分博弈的概念[5]。此后，塞尔滕提出了次博弈完美均衡的概念[6]，哈萨尼发展了贝叶斯博弈理论[7]。后来，梅纳德-史密斯将博弈论应用于进化生物学，提出了进化稳定策略的概念[8]。鲁宾斯坦在讨价还价模型中提出了完美均衡的概念[9]。此外，人们还提出了多种类型的模糊博弈，并开发了新的求解方法[10][11][12][13][14]。这些研究充分体现了自博弈论诞生以来其发展的迅猛势头。

除了这些基础性工作之外，博弈论还被广泛应用于各种现实问题中。例如，在过去二十年中，王等人运用合作博弈论方法研究水资源分配问题，提升了水资源利用效率[15]。雷从博弈论视角对联盟形成问题进行了全面研究[16]。迈尔等人探讨了电信领域安全问题的博弈论解决方案，重点研究了非合作博弈论[17]。卡特等人利用博弈论分析了部署动态平台系统以增强安全性的最优策略[18]。余等人将博弈论应用于自动驾驶的变道模型设计，旨在提升拥堵环境下的变道性能[19]。厄兹卡亚和伊兹吉研究了新冠疫情期间的个体感染风险，强调了隔离措施在降低感染风险方面的作用[20]。他们还借助序贯博弈分析了土耳其与希腊之间的爱琴海争端[21]。格伦贝克等人研究了博弈论在国际及国家层面的渔业管理中的应用[22]。厄兹卡亚和伊兹吉还提出了一个博弈论模型来解释国际危机[23]。霍等人对博弈论在国防决策场景中的应用进行了全面综述[24]。艾哈迈德等人深入研究了演化博弈论在道路交通网络中的应用，分析了其在解决拥堵、安全及效率等问题上的有效性[25]。塞ikh和杜塔提出了一种非线性规划方法，用于解决具有区间值中性收益的网络安全相关矩阵博弈问题，该方法采用了加权平均优化技术，并在银行业务中得到了应用[26]。厄兹卡亚和巴卡拉奥卢利用带矩阵输入的矩阵博弈，研究了两国间战争导致的国际僵局问题[27]。季等人回顾并分析了运用博弈论方法优化能源需求方决策的问题[28]。王等人通过提出三方博弈模型，研究了中国的水资源分配问题，为水资源匮乏地区的合理水价制定提供了参考依据[29]。阿米特全面研究了博弈论在关键运营和供应链管理问题中的应用[30]。塞ikh和杜塔提出了基于加权平均线性规划技术的带图模糊收益的矩阵博弈模型，并通过网络恐怖主义策略选择案例以及与现有方法的比较，证明了该模型的有效性[31]。维尔马等人研究了博弈论在网络安全领域的应用，指出结合博弈论与网络安全的研究数量正在大幅增长[32]。皮亚纳等人利用博弈论提出了新的挑战-响应式物理层认证策略，用于保障无人机通信的安全[33]。程等人回顾了博弈论在电力市场优化中的应用，阐述了如何提升市场的性能、效率、可持续性及竞争力[34]。这些研究都表明，博弈论已在众多研究领域得到有效应用。

在本研究中，我们主要关注沙普利提出的随机博弈[4]。这类博弈用于建模和分析理性参与者在动态环境中的战略互动。现有文献中有大量研究致力于探索并将随机博弈应用于不同问题。例如，内曼和索林撰写了一本关于随机博弈的综合性著作，涵盖了该领域的理论与应用内容[35]。阿米尔回顾了随机博弈在经济学中的应用，讨论了完全信息博弈以及涉及连续规模参与者的随机博弈[36]。博姆和苏吉斯研究了风险环境下参与者之间合作的随机博弈问题[37]。科纽霍夫斯基和马洛娃探讨了合作随机博弈的发展，并分析了经济情境中决策者之间的互动关系[38]。杨和佩特罗相研究了技术发展背景下的合作随机微分博弈问题[39]。达根分析了带噪声的一般随机博弈中是否存在平稳的马尔可夫完美均衡[40]。查特吉等人提出了一种有效方法，可将简单的随机奇偶性博弈转化为非随机奇偶性博弈[41]。巴尼克和博帕迪卡尔通过多阶段随机博弈，分析了带有敌对意图的“自我车辆”与非“自我车辆”之间的决策过程[42]。克莱什尼娜等人研究了当信息量发生变化时，随机博弈中的合作关系如何改变[43]。鲍亚等人利用并发随机博弈，分析了通信攻击对物联网系统安全性及能耗的影响[44]。朴和李基于随机博弈开发了一种优化算法，用于工业物联网设备间的网络系统优化[45]。麦卡蒂等人提出了一种基于折现零和随机博弈的军事行动动态规划模型[46]。尽管随机博弈的结构可能各异，但它们在诸多研究中都被有效地用于模拟现实问题。

通常，随机博弈的求解方法包括策略迭代、价值迭代、动态规划以及二次规划等。不过本研究聚焦于随机矩阵博弈，而这类博弈最常用的求解方法是沙普利迭代，它是由沙普利提出的、属于价值迭代范畴的求解方法[4]。沙普利迭代通过考虑状态间的转换以及参与者所采取的行动来计算博弈值。除这一经典方法外，伊兹吉等人最近又提出了四种不同的求解方法，旨在为这类博弈提供更多可选方案。其中两种方法是将沙普利的方法与扩展矩阵范数方法及其迭代形式相结合，具体内容可见伊兹吉等人的相关研究[47]。这两种迭代方法分别被称为弱混合沙普利迭代和强混合沙普利迭代[47]。其余两种方法则是完全基于扩展矩阵范数方法的新颖求解方案。

因此，对于随机矩阵博弈而言，既有传统的求解技术，也有现代的求解方法。但由于所有这些方法都具有迭代性质，求解大规模随机矩阵博弈时往往需要承担巨大的计算负担。无论采用哪种方法，随着随机矩阵博弈规模的增长，其计算成本和时间都会相应上升。此外，在随机矩阵博弈的求解过程中，寻找均衡点也是一个挑战。为克服现有方法的缺陷，机器学习技术越来越受到重视[48][49][50]。例如，卡斯格伦等人采用了数据效率高的深度Q学习方法，实现了随机博弈中纳什均衡的无模型学习[51]。鲁托托等人考虑使用机器学习框架来解决高维平均场博弈问题[52]。伊兹吉等人提出了他们所设计的新型方法——扩展矩阵范数方法，用于解决大规模矩阵博弈问题，通过降低计算成本和时间提升了求解效率[53]。钟等人研究了领导者-追随者型多玩家一般和博弈问题，并提出了一种样本效率高的强化学习算法，用于寻找斯塔克尔伯格-纳什均衡[54]。达斯卡拉克斯等人开发了一种去中心化算法，能够在假设参与者之间存在共享随机性的前提下，学习一般和随机博弈中的非平稳马尔可夫相关均衡[55]。厄兹卡亚和伊兹吉提出了一种卷积神经网络，用于预测马尔可夫奖励博弈的总奖励值[56]。贾因等人研究了博弈论方法如何提升强化学习算法的性能，进而改善自动驾驶车辆之间的交互效果[57]。伊兹吉等人还提出了一种基于整体矩阵范数的求解方法（MNBS方法），该方法借鉴了文献[58][59]中关于矩阵移动的理念，专门用于某种类型的随机博弈，即决策树形式的马尔可夫奖励博弈[60]。后来，他们又开发并提出了一种新的神经网络架构，通过简化决策树结构，解决了MNBS方法的迭代性问题，尤其适用于大规模决策树[61]。达扬克拉和劳里埃尔提出了一种单层数值方法，通过将斯塔克尔伯格平均场博弈问题重新表述为平均场最优控制问题，从而求解这类问题[62]。上述研究都体现了将博弈论与机器学习方法相结合，以提升现有求解技术性能的趋势。

在此背景下，我们的目标是利用神经网络的优势，彻底改变随机矩阵博弈的求解流程，大幅提升计算效率，且在神经网络训练完成后，即可实现即时求解。在本研究中，我们提出了一种全新的全连接神经网络架构，该架构能够精准预测随机矩阵博弈的博弈值。这一方法为传统的分析及数值解法提供了一种颠覆性的替代方案，能够实现复杂博弈论模型的快速、可扩展且智能化的计算。简而言之：
• 我们提出了一种全新的全连接神经网络架构，可用于预测不同规模随机矩阵博弈的博弈值。
• 我们成功估算出了3×3、4×4和5×5规模随机博弈的博弈值，平均误差分别为-0.0070、-0.0154和0.1060。
• 将机器学习技术融入随机矩阵博弈的求解过程，可实现实时求解，这一优势对于实际应用尤其是从业者来说意义重大。它能够帮助人们在复杂环境中做出更高效、更具适应性的决策。

本文结构如下：第二部分介绍了随机矩阵博弈的基本定义，并综述了传统的及现代的求解方法。第三部分阐述了数据准备流程，包括所采用的向量化操作方式，以及所提出神经网络的整体结构。第4节详细介绍了全连接神经网络，并展示了不同规模随机矩阵博弈的求解结果。最后一部分则给出了本文的结论。

理论背景：随机矩阵博弈的求解
在本节中，我们简要介绍随机博弈的定义以及与这类博弈相关的传统和现代求解方法。一般来说，随机博弈是指在博弈过程中会转移到另一种状态的博弈。在现有研究中，这类博弈通常通过Shapley迭代法来求解。不过，近年来也出现了一些混合型的现代求解技术，比如弱混合Shapley迭代、强混合Shapley迭代以及扩展矩阵范数法等。

基于机器学习的随机矩阵博弈求解方法
随机矩阵博弈的解析解需要求解高阶方程，而这往往会导致较高的计算成本。随着随机矩阵博弈规模的增大，这些方程的复杂性也会随之上升，使得求解过程更加繁琐。例如，求解2×2或3×3的随机矩阵博弈分别需要求解二次方程或三次方程，而且随着矩阵规模的增加，方程的阶数也会上升。

数值实验与结果
在本节中，我们阐述了所提出的神经网络架构的整体结构。首先，我们创建了包含5×105组3×3、4×4和5×5随机矩阵博弈的独立数据集，这些数据的解是通过Shapley迭代法得到的，其容差水平为10^-5。之后，我们利用文献[61]中介绍的向量化处理方法对这些数据集进行处理，以便将其作为输入传递给神经网络。接着，我们使用其中80%的样本数据来训练神经网络。

结论
由于需要求解高阶方程来确定博弈价值，解析方法在解决随机矩阵博弈时往往不够实用。因此，我们简要介绍了随机矩阵博弈及其数值解法。不过，对于规模较大的随机博弈而言，数值方法的运用难度会逐渐增加。为了解决这一难题，我们提出了一种用于求解此类博弈的全连接神经网络。

未来工作与局限性
尽管所提出的神经网络在解决随机矩阵博弈方面取得了不错的效果，但仍存在一些局限性。首先，本研究仅针对3×3到5×5规模的随机矩阵博弈进行了探讨。随着博弈规模的增大，解析公式中所涉及的高阶多项式方程会使得问题复杂性显著提升，因此构建大规模数据集并获取数值解也会变得愈发困难。

利益冲突声明
作者声明自己不存在任何可能影响本文研究结果的已知财务利益或个人关系。