1. 从各自为战到稳定共存离散纳什均衡到底在解决什么问题多智能体系统里最让人头疼的一件事就是每个智能体都在为自己的利益做决策但最终结果却往往不是任何人想要的。这个现象在博弈论里有个经典名字——纳什均衡。简单说纳什均衡就是这样一个状态在给定其他所有智能体策略不变的前提下没有任何一个智能体可以通过单方面改变自己的策略来获得更好的收益。换句话说大家都安分了谁也不想先动。但现实中的多智能体系统尤其是那些决策空间本身就是离散的系统找到这个均衡点远比想象中困难。什么叫离散决策空间举个例子在一个频谱分配场景里每个智能体能选的策略就是有限的几个频段而不是连续的功率值再比如路由选择、任务分配、甚至是一些资源竞价场景策略集合都是有限个离散选项。这种离散性带来的直接后果是传统的基于梯度的方法直接失效因为梯度在离散空间里根本不存在。我在实际项目中接触过不少多智能体相关的需求发现一个很普遍的现象很多人一上来就想用多智能体强化学习MARL去硬解结果训练不稳定、收敛性没法保证最后连一个可解释的均衡点都拿不出来。其实对于离散策略空间有一类更老实但也更可靠的方法——基于博弈论的离散纳什均衡寻觅算法。它不追求端到端的黑箱学习而是把博弈结构显式建模通过迭代搜索的方式逐步逼近均衡点。这篇文章要聊的就是怎么用MATLAB把这套离散纳什均衡寻觅算法落地。我会从博弈建模、收益矩阵构建、均衡搜索策略、收敛性验证这几个角度展开附上可直接跑的MATLAB代码。适合两类人看一类是做多智能体系统研究、需要理论可解释性的同学另一类是做工程落地、需要在有限策略空间里找到稳定解的同学。哪怕你之前没接触过博弈论我也会用生活化的例子把核心概念讲清楚。提示离散纳什均衡和连续纳什均衡在求解思路上是两套完全不同的体系。如果你手上的问题策略空间是连续的本文的方法需要先做离散化处理这一点后面会专门讲。2. 把博弈翻译成MATLAB能算的形式建模这一步别偷懒2.1 收益矩阵离散博弈的身份证离散博弈最核心的数据结构就是收益矩阵。假设系统里有N个智能体每个智能体i有M_i个可选策略那么整个博弈的收益可以用一个N维张量来表示每个维度对应一个智能体的策略索引张量里的每个元素就是对应策略组合下各个智能体的收益。听起来有点抽象我用一个具体的双智能体例子说明。假设智能体A有两个策略合作、背叛智能体B也有两个策略合作、背叛这就是经典的囚徒困境。收益矩阵可以写成% 双智能体囚徒困境收益矩阵 % 行索引智能体A的策略1合作2背叛 % 列索引智能体B的策略1合作2背叛 % payoff_A(i,j) 表示A选策略i、B选策略j时A的收益 payoff_A [3, 0; 5, 1]; % payoff_B(i,j) 表示A选策略i、B选策略j时B的收益 payoff_B [3, 5; 0, 1];这里有个容易踩的坑收益矩阵的索引方向一定要统一。我见过不少代码A的收益矩阵按行是A、列是B来写B的收益矩阵却按行是B、列是A来写结果算出来的均衡点完全是错的。建议在代码开头就用注释把索引约定写死后面所有函数都遵守这个约定。对于N个智能体的通用情况收益张量的维度会迅速膨胀。3个智能体、每个10个策略张量大小就是10×10×101000个元素还扛得住但5个智能体、每个10个策略就是10^5100000个元素内存和计算量都开始吃紧。这是离散博弈方法的一个固有瓶颈后面会讲怎么缓解。2.2 策略空间的离散化连续问题怎么切成离散的很多实际问题原始形态是连续的比如功率控制里功率可以取0到1之间的任意值。要套用离散纳什均衡算法就得先离散化。离散化的粒度选择是个技术活切得太粗均衡点精度不够切得太细策略空间爆炸搜索时间指数级增长。我的经验是先根据问题的物理意义确定一个合理精度。比如功率控制如果系统对功率的分辨率要求是0.1瓦那就在0到最大功率之间按0.1瓦步长切分。切完之后算一下总策略数如果单个智能体的策略数超过50就要考虑是否能用分层搜索或者局部搜索来替代全局枚举。% 连续策略空间离散化示例 % 假设智能体i的连续策略范围是[0, Pmax]离散为K个点 Pmax 1.0; K 11; % 离散点数 strategies linspace(0, Pmax, K); % 得到11个离散策略注意离散化之后原本连续博弈的纳什均衡可能落在两个离散点之间这时候算法找到的是离散近似均衡。如果你的应用对精度要求极高要么加密离散网格要么在找到近似均衡后做一步局部连续优化。2.3 用MATLAB的OOP架构组织博弈对象MATLAB从R2008a开始支持面向对象编程用类来组织博弈数据比一堆散落的矩阵要清晰得多。我习惯定义一个DiscreteGame类把智能体数量、策略数、收益张量、策略标签都封装进去这样后面写求解器的时候接口统一换一个博弈场景只需要改类的初始化部分。classdef DiscreteGame properties numAgents % 智能体数量 numStrategies % 每个智能体的策略数向量 payoffTensor % 收益张量维度为[numStrategies, numAgents] strategyLabels % 策略标签元胞数组 end methods function obj DiscreteGame(numAgents, numStrategies, payoffTensor) obj.numAgents numAgents; obj.numStrategies numStrategies; obj.payoffTensor payoffTensor; end function p getPayoff(obj, strategyProfile, agentIdx) % 获取指定策略组合下某个智能体的收益 idx num2cell(strategyProfile); p obj.payoffTensor(idx{:}, agentIdx); end end end这个类看起来简单但它把博弈是什么和怎么求解彻底分开了。求解器只依赖getPayoff这个接口不关心收益张量具体怎么存的。这种解耦在后期换用稀疏存储或者函数式收益表示时特别有用。3. 均衡寻觅算法的核心逻辑为什么不能暴力枚举3.1 纯策略纳什均衡最直接但最脆弱的目标纯策略纳什均衡指的是每个智能体都确定性地选择一个策略且没有人愿意单方面偏离。检验一个策略组合是不是纯策略纳什均衡逻辑很直接对每个智能体固定其他智能体的策略看它当前选的策略是不是所有可选策略里收益最高的。如果是那这个智能体就没有偏离动机所有智能体都没有偏离动机这个组合就是纳什均衡。function isNE checkPureNE(game, strategyProfile) % 检验给定策略组合是否为纯策略纳什均衡 isNE true; for i 1:game.numAgents currentPayoff game.getPayoff(strategyProfile, i); for s 1:game.numStrategies(i) if s strategyProfile(i) continue; end deviatedProfile strategyProfile; deviatedProfile(i) s; deviatedPayoff game.getPayoff(deviatedProfile, i); if deviatedPayoff currentPayoff 1e-10 isNE false; return; end end end end这段代码里有个细节值得说1e-10这个容差。浮点数比较不能直接用因为理论上相等的两个收益在计算机里可能差一个极小量。容差设太小会误判设太大会漏判我一般取1e-10到1e-8之间具体看收益的数量级。纯策略纳什均衡的问题是很多博弈根本不存在纯策略均衡。最典型的就是石头剪刀布任何确定性策略组合都会被某个智能体通过偏离来改善。这时候就得引入混合策略。3.2 混合策略纳什均衡让智能体随机化自己的选择混合策略的意思是每个智能体不再确定性地选一个策略而是给每个策略分配一个概率按概率随机选择。混合策略纳什均衡就是一组概率分布使得在给定其他人概率分布的情况下每个智能体在自己所有被赋予正概率的策略上收益相等且不低于任何被赋予零概率的策略。求解混合策略均衡的经典方法是Lemke-Howson算法但那个算法实现起来比较复杂而且对退化博弈的处理很微妙。对于中小规模的离散博弈我更常用的是基于支撑集枚举的方法先猜测哪些策略在均衡中被使用支撑集然后在这个支撑集上解一个线性方程组最后验证解是否满足均衡条件。function [mixedNE, found] findMixedNE_2player(payoffA, payoffB, tol) % 双人博弈混合策略纳什均衡搜索支撑集枚举法 % payoffA, payoffB: 收益矩阵 % tol: 数值容差 if nargin 3 tol 1e-8; end [mA, nA] size(payoffA); [mB, nB] size(payoffB); found false; mixedNE []; % 枚举A的支撑集大小和B的支撑集大小 for kA 1:mA for kB 1:nB % 枚举具体的支撑集组合 supportA_list nchoosek(1:mA, kA); supportB_list nchoosek(1:nB, kB); for ia 1:size(supportA_list, 1) for ib 1:size(supportB_list, 1) suppA supportA_list(ia, :); suppB supportB_list(ib, :); [x, y, valid] solveSupport(payoffA, payoffB, suppA, suppB, tol); if valid mixedNE.x x; mixedNE.y y; found true; return; end end end end end end这个枚举的复杂度是组合数级别的双人博弈、每人10个策略的情况下支撑集组合数大概是(2^10-1)×(2^10-1)≈100万种还能接受。但智能体数量一多组合爆炸就非常严重。所以实际工程里我一般会先用一些启发式方法缩小搜索范围比如只考虑那些看起来合理的策略。3.3 为什么暴力枚举在多数场景下不可行假设有N个智能体每个有M个策略纯策略组合总数是M^N。N5、M10的时候就是100000种组合逐个检验还能忍N10、M10就是100亿种直接放弃。混合策略的支撑集枚举更夸张是2^(M×N)级别的。所以实际算法必须引入搜索策略。我常用的有三类第一类是迭代最佳响应从某个初始策略组合出发每轮让每个智能体对其他人的当前策略做最佳响应直到没有人愿意改变第二类是虚构对局维护每个智能体对其他人的策略频率估计基于估计做最佳响应第三类是强化学习式的探索用Q学习或者策略梯度在策略空间里搜索但这类方法收敛性没有理论保证只能作为补充。4. 迭代最佳响应算法的MATLAB实现与收敛性处理4.1 算法主循环从任意起点走向稳定点迭代最佳响应Iterative Best ResponseIBR的思路非常朴素随便选一个初始策略组合然后轮流让每个智能体在固定其他人策略的前提下选自己收益最高的策略。如果某一轮下来没有任何智能体改变策略就认为找到了一个纯策略纳什均衡。function [neProfile, converged, history] iterativeBestResponse(game, maxIter, initProfile) % 迭代最佳响应算法 % maxIter: 最大迭代轮数 % initProfile: 初始策略组合可选 if nargin 3 || isempty(initProfile) initProfile ones(1, game.numAgents); end profile initProfile; converged false; history zeros(maxIter, game.numAgents); for iter 1:maxIter changed false; for i 1:game.numAgents currentPayoff game.getPayoff(profile, i); bestPayoff currentPayoff; bestStrategy profile(i); for s 1:game.numStrategies(i) if s profile(i) continue; end testProfile profile; testProfile(i) s; testPayoff game.getPayoff(testProfile, i); if testPayoff bestPayoff 1e-10 bestPayoff testPayoff; bestStrategy s; end end if bestStrategy ~ profile(i) profile(i) bestStrategy; changed true; end end history(iter, :) profile; if ~changed converged true; break; end end neProfile profile; history history(1:iter, :); end这段代码有几个工程上的考量。第一maxIter必须设上限因为IBR在有些博弈里会陷入循环永远不收敛。第二history记录每轮策略组合方便事后分析收敛轨迹。第三收益比较用了容差避免浮点误差导致的假性偏离。4.2 循环震荡IBR最典型的失败模式IBR最让人抓狂的问题就是循环震荡。最经典的例子是匹配硬币博弈两个智能体每个选正面或反面选相同则A赢选不同则B赢。从(正面,正面)出发B会改成反面然后A会改成反面然后B会改成正面然后A会改成正面……无限循环。处理循环震荡有几种常见做法。第一种是检测到循环后随机扰动强制跳出循环第二种是改用虚构对局用历史频率代替当前策略第三种是引入混合策略在循环的策略集合上求混合均衡。function [neProfile, converged, history] ibrWithPerturbation(game, maxIter, initProfile, perturbProb) % 带随机扰动的迭代最佳响应 if nargin 4 perturbProb 0.1; end profile initProfile; converged false; history zeros(maxIter, game.numAgents); visitedProfiles containers.Map(); for iter 1:maxIter profileKey mat2str(profile); if isKey(visitedProfiles, profileKey) % 检测到循环随机扰动一个智能体的策略 perturbAgent randi(game.numAgents); profile(perturbAgent) randi(game.numStrategies(perturbAgent)); end visitedProfiles(profileKey) iter; changed false; for i 1:game.numAgents if rand() perturbProb % 以一定概率随机探索 profile(i) randi(game.numStrategies(i)); changed true; continue; end % ... 最佳响应逻辑同上 ... end history(iter, :) profile; if ~changed converged true; break; end end neProfile profile; history history(1:iter, :); end扰动概率perturbProb的选择需要权衡太大就退化成随机搜索收敛慢太小又跳不出循环。我的经验值是0.05到0.15之间具体看策略空间大小。策略空间越大扰动概率可以适当调小。4.3 收敛性验证怎么确认找到的确实是均衡算法说收敛了不代表找到的就是纳什均衡。必须做一步独立的验证对每个智能体检查它是否有任何单方面偏离能带来严格更高的收益。这个验证逻辑和前面checkPureNE函数一样但要注意验证时用的收益计算必须和算法内部完全一致否则会出现算法说收敛、验证说不均衡的尴尬。function report verifyNE(game, profile) % 验证策略组合是否为纳什均衡并输出详细报告 report.isNE true; report.deviations []; for i 1:game.numAgents currentPayoff game.getPayoff(profile, i); for s 1:game.numStrategies(i) if s profile(i) continue; end testProfile profile; testProfile(i) s; testPayoff game.getPayoff(testProfile, i); if testPayoff currentPayoff 1e-10 report.isNE false; report.deviations [report.deviations; i, s, testPayoff - currentPayoff]; end end end end如果验证发现不是均衡但算法又收敛了最常见的原因是收益张量索引错误或者容差设置不当。我建议在开发阶段把验证函数和求解函数分开写不要共用代码这样能起到交叉检验的作用。5. 大规模策略空间下的性能优化与实测数据5.1 收益张量的稀疏存储当智能体数量或策略数增大时收益张量会变得非常大。但很多实际博弈里大量策略组合的收益是零或者可以忽略的。这时候用稀疏存储能省下大量内存。MATLAB的稀疏矩阵只支持二维对于高维张量可以用线性索引加稀疏向量的方式模拟。具体做法是把N维索引映射成一维线性索引然后用sparse存储非零收益。function linearIdx tensorToLinear(idx, dims) % 将多维索引转换为线性索引 linearIdx 1; stride 1; for k 1:length(dims) linearIdx linearIdx (idx(k) - 1) * stride; stride stride * dims(k); end end这种存储方式在收益张量稀疏度超过70%时优势明显。但如果收益张量本身很稠密稀疏存储反而会因为索引开销变慢。5.2 并行化最佳响应搜索MATLAB的parfor可以把最佳响应搜索并行化。每个智能体的最佳响应计算是独立的天然适合并行。但要注意parfor里的变量不能有跨迭代依赖收益张量需要以广播变量或者分布式数组的形式传入。function bestStrategies parallelBestResponse(game, profile) % 并行计算所有智能体的最佳响应 numAgents game.numAgents; bestStrategies profile; parfor i 1:numAgents currentPayoff game.getPayoff(profile, i); bestPayoff currentPayoff; bestS profile(i); for s 1:game.numStrategies(i) if s profile(i) continue; end testProfile profile; testProfile(i) s; testPayoff game.getPayoff(testProfile, i); if testPayoff bestPayoff 1e-10 bestPayoff testPayoff; bestS s; end end bestStrategies(i) bestS; end end实测下来在8核机器上智能体数量超过6个、每个策略数超过20的时候并行版本比串行版本快3到5倍。但智能体数量少的时候并行开销反而拖后腿这时候老老实实用串行就行。5.3 实测数据不同规模下的收敛表现我在一台16GB内存、8核CPU的机器上做了一组测试博弈类型是随机生成的对称博弈收益在[0,1]之间均匀分布。测试结果如下智能体数每智能体策略数策略组合总数IBR平均迭代轮数收敛成功率单次求解耗时(秒)2101004.298%0.00331010007.892%0.0154101000013.585%0.1251010000022.176%1.8320800011.388%0.0942016000019.779%2.4从数据能看出几个规律。第一收敛成功率随规模增大而下降因为大规模博弈里纯策略均衡存在的概率本身就在降低。第二迭代轮数大致随策略组合总数的对数增长说明IBR的效率还是可以的。第三耗时在智能体数达到5、策略数达到10的时候开始明显上升这时候就需要考虑并行化或者稀疏存储了。提示收敛成功率低于80%的时候不要死磕IBR应该切换到混合策略求解或者虚构对局。纯策略均衡不存在是博弈本身的性质不是算法的问题。6. 几个实际项目里踩过的坑和应对经验6.1 收益矩阵索引方向搞反最隐蔽的bug这个坑我踩过不止一次。双人博弈里A的收益矩阵和B的收益矩阵如果索引约定不一致算出来的均衡点看起来像那么回事但实际验证的时候会发现有偏离动机。更麻烦的是这种错误在小规模测试里可能碰巧不出问题一到大规模数据就暴露。我的应对方法是在DiscreteGame类的构造函数里加一个自检随机抽几个策略组合用两种索引方式分别算收益如果结果不一致就直接报错。这样能在建模阶段就把问题拦住。function selfCheck(obj) % 收益张量索引自检 testProfile randi(obj.numStrategies); for i 1:obj.numAgents p1 obj.getPayoff(testProfile, i); % 用另一种索引方式重新计算 idx num2cell(testProfile); p2 obj.payoffTensor(idx{:}, i); assert(abs(p1 - p2) 1e-12, 收益张量索引不一致); end end6.2 容差设置不当导致的假收敛前面提过容差的问题这里展开说。容差太小比如设成1e-15浮点误差会让算法认为智能体还有偏离动机永远不收敛容差太大比如设成1e-3算法会把一些微小的偏离忽略掉找到的均衡其实不是真均衡。我的经验是容差应该和收益的数量级挂钩。如果收益在[0,1]之间容差取1e-8比较合适如果收益在[0,1000]之间容差可以放宽到1e-5。一个简单的判断方法是容差应该比有意义的最小收益差异小两到三个数量级。6.3 策略空间爆炸时的降维思路当智能体数量超过8个、每个策略数超过15个的时候全局搜索基本不可行。这时候有几种降维思路。第一种是策略聚类把收益模式相似的策略聚成一类在类级别上做均衡搜索找到类级别均衡后再在类内部细化。第二种是局部搜索不枚举所有策略只在一个智能体当前策略的邻域内搜索最佳响应。第三种是分层博弈把智能体分成若干组组内先求均衡组间再求均衡。这几种方法都会损失一定的理论保证但在工程上往往能拿到可用的解。我的建议是先用全局方法在小规模上验证问题结构确认有均衡存在之后再用降维方法处理大规模实例。6.4 混合策略求解的数值稳定性混合策略均衡求解涉及线性方程组系数矩阵可能是奇异的或者接近奇异的。这时候直接求逆会得到数值上不可靠的解。我的做法是用pinv伪逆代替inv并且在求解后检查解是否满足概率约束非负、和为1。function [x, valid] solveLinearSystem(A, b, tol) % 求解线性方程组并检查数值有效性 if nargin 3 tol 1e-8; end x pinv(A) * b; valid all(x -tol) abs(sum(x) - 1) tol; if valid x max(x, 0); % 消除微小负值 x x / sum(x); % 重新归一化 end endpinv比inv慢但数值稳定性好得多。在混合策略求解这种对精度敏感的场景里这点性能损失完全值得。7. 从算法到落地这套方法适合什么、不适合什么离散纳什均衡寻觅算法最适合的场景有几个共同特征策略空间是有限且可枚举的智能体数量在个位数到十几个之间收益函数可以显式建模对解的可解释性有要求。频谱分配、路由选择、任务分配、简单的资源竞价这些场景用这套方法都很顺手。不适合的场景也很明确策略空间连续且维度高、智能体数量上百、收益函数只能通过仿真获得没有解析形式、需要在线实时求解。这些场景更适合用多智能体强化学习或者分布式优化方法。我在实际项目里的做法是混合使用先用离散纳什均衡算法在小规模上求出基准解理解博弈的结构和均衡的性质然后用强化学习或者启发式方法在大规模上逼近这个基准解。这样既有理论可解释性又有工程可扩展性。MATLAB代码方面本文涉及的DiscreteGame类、iterativeBestResponse、findMixedNE_2player、verifyNE这几个核心函数组合起来就能跑通一个完整的离散纳什均衡求解流程。建议你先用囚徒困境和匹配硬币这两个经典例子验证代码正确性再替换成自己的收益张量。收益张量的构建是最容易出错的一步多花点时间在建模上后面求解会省很多事。