引论第二矩阵对策第三矩阵对策的求解

O运筹学讲义OperationsResearchGameTheory·MatrixGamesLectureSeries引论·第二矩阵对策·第三矩阵对策的求解运筹学/博弈论专题讲义高校教学讲义对策论专题M矩阵对策讲义CONTENTSSYLLABUS课程目录PART01第一部分引论博弈论发展简史与关键里程碑矩阵对策的基本模型与术语体系本课程的知识定位与学习目标PART02第二部分第二矩阵对策纯策略鞍点与极大极小原理混合策略与冯·诺依曼极小极大定理优超原则化简与2×n/m×2图解法线性规划建模与综合求解例题PART03第三部分第三矩阵对策的求解n人非合作博弈与纳什均衡合作博弈特征函数与核心（Core）Shapley值公理化定义与计算方法联盟结构与Owen值等扩展解概念CHAPTER01引论博弈论简史·矩阵对策基本模型·课程定位H学术青瓷·矩阵对策讲义HISTORYCHAPTER01博弈论发展简史博弈论从古代策略智慧演变为严格的数学学科，经历了从个案分析到公理化体系的百年历程。冯·诺依曼1928年的极小极大定理是矩阵对策的理论基石，而1944年《博弈论与经济行为》的出版标志着博弈论作为独立学科的正式诞生。约公元前4世纪1912192119281944齐王赛马田忌通过策略调整以弱胜强，是中国古代策略对抗的经典案例，体现了策略选择优于单纯实力比拼的思想。策梅洛定理德国数学家E.Zermelo证明国际象棋三种着法必存在一种确定性结果，首次将博弈问题纳入严格数学分析框架。博雷尔的开创性工作法国数学家E.Borel引入"最优策略"概念，研究了简单零和博弈，为冯·诺依曼的工作做了重要铺垫。冯·诺依曼极小极大定理证明了有限二人零和博弈中极大极小值等于极小极大值，被公认为博弈论作为数学学科的奠基性成果。《博弈论与经济行为》出版冯·诺依曼与摩根斯坦合著此书，系统建立了博弈论的理论体系，奠定了该学科的研究基础与方向。H矩阵对策讲义MODELDEFINITIONDEFINITION矩阵对策的基本模型矩阵对策是二人有限零和博弈的标准数学模型，由两个局中人、各自的有限策略集和一个支付矩阵完整刻画。其核心特征是零和性——任一局势下双方赢得之和为零，利益完全对抗。该模型可用三元组G={S₁,S₂,A}表示。二人有限零和：局中人数为二，每人可选策略数量有限，且任何局势下双方赢得总和恒为零，即一方所得恰为另一方所失，利益完全对抗。策略集定义：局中人I的策略集S₁={α₁,α₂,…,αₘ}含m个纯策略，局中人II的策略集S₂={β₁,β₂,…,βₙ}含n个纯策略，均为有限集。支付矩阵：当局中人I选αᵢ、II选βⱼ时形成纯局势(αᵢ,βⱼ)，I的赢得值为aᵢⱼ，所有aᵢⱼ构成m×n阶矩阵A=(aᵢⱼ)，称为局中人I的赢得矩阵。零和对偶性：由于对策为零和，局中人II在局势(αᵢ,βⱼ)下的赢得为−aᵢⱼ，故II的赢得矩阵为−A，整个对策可由单个矩阵A完整描述。三元组表示：矩阵对策标准记为G={S₁,S₂,A}，其中S₁、S₂分别为两局中人的策略集，A为I的赢得矩阵，该表示法涵盖了模型的全部信息。CHAPTER02第二矩阵对策纯策略鞍点·混合策略·优超原则·图解法·线性规划THEORYGAMETHEORY纯策略鞍点与判定准则鞍点是矩阵对策中最基本的解概念，指满足双方均无动机单方面偏离的纯局势。其数学定义为：若ai*j*同时是其所在行的最小值和所在列的最大值，则(αi*,βj*)为鞍点。鞍点存在的充要条件是极大极小值等于极小极大值，此时对策有纯策略解，对策值v即为该公共值。01鞍点定义—纯局势(αi*,βj*)称为鞍点，若对一切i=1,…,m和j=1,…,n均满足aij*≤ai*j*≤ai*j，即该元素既是其行的最小值又是其列的最大值。02极大极小值—局中人I采取保守策略，先求每行最小值再取最大，记为vI=maximinjaij，表示I能保证的最低赢得下限。03极小极大值—局中人II同样保守，先求每列最大值再取最小，记为vII=minjmaxiaij，表示II能将I的赢得限制在此上限之内。04鞍点存在定理—鞍点存在的充要条件是vI=vII，此时公共值v=vI=vII称为对策的值，对应的纯策略对即为对策的解。05鞍点性质—若矩阵对策存在多个鞍点，则所有鞍点对应的支付值必定相等；且若(ai*,bj*)和(ak*,bl*)都是鞍点，则交叉局势(ai*,bl*)和(ak*,bj*)也是鞍点。vI=vII鞍点存在充要条件v=v*对策值（公共鞍点值）∀saddle多鞍点支付值相等EXAMPLE·鞍点求解MATRIXGAMES鞍点求解例题演示通过具体矩阵演示鞍点判定的完整流程：先逐行求最小值得到vI，再逐列求最大值得到vII，比较两者是否相等——相等则鞍点存在，不等则需转入混合策略求解。CASEA无鞍点Aβ₁β₂β₃minα₁3141α₂2532α₃4262vI=2≠vII=4→无鞍点，需混合策略CASEB有鞍点Aβ₁β₂β₃minα₁3543α₂2532α₃4564vI=4=vII=4✓鞍点(α₃,β₁)，v=4求解四步骤01列出支付矩阵—确定局中人策略集与对应收益值02求各行最小值，取最大得vI=max{min}03求各列最大值，取最小得vII=min{max}04比较vI与vII—相等则有鞍点，不等则需混合策略鞍点定位要点鞍点元素须同时满足：是本行最小值&本列最大值。CaseB中a₃₁=4即为第三行最小且第一列最大，故(α₃,β₁)为鞍点，对策值v=4。实践提示求解时应先尝试鞍点判定（纯策略解计算最简），确认无鞍点后才引入混合策略，避免不必要的复杂计算。MIXEDSTRATEGYTHEORY混合策略的定义与意义混合策略是局中人在纯策略集上的概率分布，用于解决纯策略鞍点不存在时的求解问题。通过随机化选择，局中人可以避免被对手预测和利用。引入混合策略后，矩阵对策的解空间从有限个纯局势扩展到连续的概率单纯形，为极小极大定理的成立提供了必要的数学基础。混合策略定义：局中人I的混合策略是m维概率向量x=(x1,…,xm)，满足xi≥0且Σxi=1；II的混合策略是n维概率向量y=(y1,…,yn)，满足yj≥0且Σyj=1。期望支付函数：当I使用混合策略x、II使用y时，I的期望赢得为E(x,y)=xTAy=ΣiΣj

xi·aij·yj，这是双线性函数。纯策略作为特例：纯策略αi对应混合策略ei（第i分量为1、其余为0的单位向量），因此纯策略是混合策略的退化情形，混合策略推广了纯策略概念。随机化的必要性：当无鞍点时，任何纯策略都会被对手针对性利用；通过随机化，局中人使对手无法准确预测自己的行为，从而获得稳定的期望收益保障。策略空间扩展：混合策略将局中人的选择从有限的m个或n个点扩展到m-1维或n-1维概率单纯形，使对策的解空间成为紧凸集，为存在性证明提供拓扑基础。THEOREMMATRIXGAMES冯·诺依曼极小极大定理极小极大定理断言：任意有限二人零和博弈在混合策略意义下必有解，即maxxminyE(x,y)=minymaxxE(x,y)=v。该定理由冯·诺依曼于1928年首次证明，是博弈论作为数学学科的奠基性成果，保证了矩阵对策最优混合策略的存在性，并为后续线性规划解法提供了理论依据。定理表述：对任意m×n实矩阵A，maxx∈Δmminy∈ΔnxTAy=miny∈Δnmaxx∈ΔmxTAy，其中Δm和Δn分别为m维和n维概率单纯形。对策值的存在：上述公共值记为v(G)或简记为v，称为矩阵对策G的值。它表示局中人I在最优策略下能保证的期望赢得，也是II能将I的期望赢得限制的上限。最优策略对：使上式成立的混合策略x*和y*分别称为局中人I和II的最优混合策略。它们满足：对任意y有E(x*,y)≥v，对任意x有E(x,y*)≤v。历史地位：冯·诺依曼1928年首次证明此定理，他本人评价"没有这个定理就不可能有博弈论"。博雷尔曾猜测该定理对5×5以上矩阵不成立，冯·诺依曼的证明否定了这一猜想。证明思路概述：经典证明可利用凸集分离定理、Brouwer不动点定理或线性规划强对偶定理完成。其中线性规划方法最具构造性，直接将对策求解转化为LP问题。H矩阵对策讲义PRINCIPLETHEORY混合策略求解的无差异原理无差异原理是求解混合策略的核心工具：在最优策略对(x*,y*)下，若某纯策略被正概率使用，则该策略给对手带来的期望支付必等于对策值v。这一性质将最优策略的求解转化为等式与不等式系统，为图解法和线性规划方法提供了直接的理论基础。互补松弛条件：设(x*,y*)为最优策略对，v为对策值。若y*_j>0，则Σᵢx*ᵢaᵢⱼ=v；若x*ᵢ>0，则Σⱼaᵢⱼy*ⱼ=v。即正概率策略对应的期望支付恰等于v。支撑集外策略：若y*_j=0，则Σᵢx*ᵢaᵢⱼ≥v（对I有利）；若x*ᵢ=0，则Σⱼaᵢⱼy*ⱼ≤v（对II有利）。支撑集外的策略不会比v更差（对使用者而言）。等式系统构建：若已知最优策略的支撑集大小，可将互补松弛条件写为线性等式组加上概率归一化条件，直接求解得到候选最优策略，再验证不等式条件是否满足。支撑集枚举思想：理论上可枚举所有可能的支撑集组合，对每个组合求解等式系统并验证可行性。但组合数随策略数指数增长，仅适用于小规模问题。与线性规划的联系：无差异原理本质上就是线性规划互补松弛条件的博弈论表述。将对策转化为LP后，最优基变量对应支撑集内的策略，非基变量对应支撑集外的策略。矩阵对策讲义11/34H矩阵对策DOMINANCELECTURE·矩阵对策求解优超原则与矩阵化简优超原则是矩阵对策求解的重要预处理工具：若某纯策略在任何对手策略下都不优于另一策略，则该策略可被安全删除而不改变对策的解。纯策略优超通过逐元素比较判定，混合策略优超则需检查凸组合关系。反复应用优超可显著缩减矩阵规模，降低后续求解的计算复杂度。纯策略优超（I方）：若对一切j=1,…,n都有aij≥akj，则称αi优超αk。此时αk可从策略集中删除，因为I永远不会选择被优超的策略。纯策略优超（II方）：若对一切i=1,…,m都有aij≤ail，则称βj优超βl。II的目标是最小化支付，因此较小的列优超较大的列，被优超的列可删除。混合策略优超：若存在概率向量λ使得Σkλkakj≥aij对所有j成立（λk≥0,Σλk=1），则纯策略αi被其他纯策略的混合策略优超，αi可删除。II方类似。严格优超与弱优超：不等式严格成立则为严格优超，可直接删除；若允许等号则为弱优超，删除时需保留至少一个等价策略以避免丢失解。化简流程：反复检查行列优超关系，删除被优超的策略，直到无法进一步化简为止。化简后的矩阵与原对策具有相同的值和最优策略（被删策略概率为零）。METHODGRAPHICALSOLUTION2×n矩阵对策的图解法图解法是求解2×n型矩阵对策最直观的方法：将I的混合策略参数化为x∈[0,1]，对II的每个纯策略画出期望支付直线，取下包络得到I的保证赢得曲线，该曲线的最高点即为对策值v，对应的x*为I的最优混合策略。参数化混合策略局中人I仅有两个纯策略，混合策略表示为(x,1−x)，其中x∈[0,1]为选择第一个纯策略的概率，策略空间退化为单位区间。期望支付直线对II的第j个纯策略，I的期望支付fj(x)=(a1j−a2j)x+a2j，是x的一次函数，图像为直线。下包络与极大极小II会选择使I赢得最小的策略，I在x处的保证赢得为g(x)=minjfj(x)，即所有直线的下包络。I的最优策略x*使g(x*)取最大值。对策值读取g(x)的最高点纵坐标即为对策值v，横坐标x*给出I的最优混合策略(x*,1−x*)。最高点通常是两条或多条直线的交点。II的最优策略确定在x*处与下包络相切的直线对应的纯策略构成II最优混合策略的支撑集，通过解交点方程可得支撑集内策略的概率分配。METHODMATRIXGAMEm×2图解法与适用范围m×2型矩阵对策的图解法与2×n型对称：将II的混合策略参数化为y∈[0,1]，画出I各纯策略的期望支付直线，取上包络得到II的保证损失曲线，该曲线的最低点即为对策值v。m×2参数化：II的混合策略为(y,1-y)，y∈[0,1]。对I的第i个纯策略，期望支付为hi(y)=ai1·y+ai2·(1-y)，同样是y的线性函数。上包络与极小极大：I会选择使赢得最大的策略，故II在y处面临的实际支付为H(y)=maxihi(y)，即所有直线的上包络。II的最优y*使H(y*)最小。对策值与最优策略：H(y)的最低点纵坐标为对策值v，横坐标y*给出II的最优混合策略(y*,1-y*)。最低点处相交的直线对应I最优策略的支撑集。图解法适用条件：适用于2×n、m×2型矩阵，或经优超化简后降至此规模的矩阵。当m,n均大于2时图解法不再直接适用，需改用线性规划或其他数值方法。教学价值：图解法将抽象的极大极小问题转化为直观的几何操作，有助于学生理解混合策略的本质、支撑集的概念以及对策值的含义，是课堂教学的首选演示方法。LINEARPROGRAMMING15矩阵对策的线性规划建模（I方）矩阵对策可等价转化为线性规划问题：局中人I的最优混合策略求解等价于一个LP，目标是最大化保证赢得v，约束为对各纯策略的期望支付不低于v。通过变量替换ui=xi/v可化为标准LP形式，使通用LP求解器可直接应用。1原始LP模型maxv，s.t.Σixiaij≥v(j=1,…,n)，Σixi=1，xi≥0。共m+1个变量，n+1个约束。2标准化变换假设v>0，令ui=xi/v，则xi=ui·v，Σxi=1变为v·Σui=1即v=1/Σui。最大化v等价于最小化Σui。3标准LP形式minΣiui，s.t.Σiuiaij≥1(j=1,…,n)，ui≥0。这是一个m变量、n约束的标准LP，可用单纯形法或内点法求解。4还原最优策略求得最优u*后，v*=1/Σui*，x*i=u*i/Σui*。从LP最优解恢复原对策的最优混合策略和对策值。5负值处理若支付矩阵含负元素导致v可能为负，可先给A加常数c使所有元素为正，求解后对策值减去c即可。最优策略不受平移影响。G矩阵对策讲义DUALITYLINEARPROGRAMMINGII方LP模型与对偶关系局中人II的LP模型与I方互为对偶：I方为minΣuis.t.Σiuiaij≥1，II方为maxΣvjs.t.Σjaijvj≤1。根据线性规划强对偶定理，两者最优值相等，这直接给出了极小极大定理的证明。01II方原始LPminw，s.t.Σjaijyj≤w（i=1,…,m），Σjyj=1，yj≥0。目标是最小化I的期望赢得上界w。02II方标准形式令vj=yj/w，得maxΣjvj，s.t.Σjaijvj≤1（i=1,…,m），vj≥0。这是n变量、m约束的标准LP。03对偶配对I方LP（minΣui，ATu≥1，u≥0）与II方LP（maxΣvj，Av≤1，v≥0）互为对偶。约束矩阵互为转置，目标系数与右端项互换。04强对偶即极小极大LP强对偶定理保证两问题最优值相等：minΣui*=maxΣvj*。还原后即为vI=vII=v，这正是极小极大定理的LP证明。I方(Primal)minΣuiATu≥1⇌对偶II方(Dual)maxΣvjAv≤105计算实践实际求解时只需解其中一个LP，另一个的最优解可从对偶变量中直接读出。现代LP求解器（单纯形法、内点法）可同时给出原问题和对偶问题的最优解。MATRIXGAME·LPDUALITY·MINIMAXTHEOREMCaseStudy017线性规划求解综合例题通过完整例题演示LP求解矩阵对策的全流程：鞍点检验→常数平移→LP建模→求解→还原对策值与最优策略。01问题设定支付矩阵A为3×3矩阵，代表简化版齐王赛马：[3-11-13111-1]鞍点检验：vI=-1,vII=1，不等，需混合策略。02常数平移矩阵含负元素，加常数c=2，得正矩阵A'：[513153331]求解后对策值减2即可还原，最优策略不变。03LP建模（I方标准线性规划）目标函数：minu₁+u₂+u₃约束条件（对应II的三个纯策略）：5u₁+u₂+3u₃≥1u₁+5u₂+3u₃≥13u₁+3u₂+u₃≥1u₁,u₂,u₃≥004求解与还原最优解u*=(1/9,1/9,1/9)Σuᵢ*=1/3，故v'=3原对策值v=3−2=1最优策略x*=(1/3,1/3,1/3)05对偶获取II方策略由LP对偶解或直接对称性：y*=(1/3,1/3,1/3)验证：

E(x*,y*)=1=v

✓解正确Result对策值v=1I方策略x*=(⅓,⅓,⅓)II方策略y*=(⅓,⅓,⅓)齐王赛马·对称均衡解SUMMARYGAMETHEORY·LECTURE18第二矩阵对策求解体系小结第二矩阵对策的求解形成了层次分明的方法体系：鞍点判定为首选，优超原则为预处理，图解法适用于小规模，线性规划为通用求解器。各方法以极小极大定理和无差异原理为共同理论基础，彼此衔接而非孤立。掌握这一体系的关键在于理解方法间的内在逻辑与适用边界。求解优先级：先查鞍点（纯策略解）→再用优超化简→小规模用图解法→一般规模用线性规划。遵循此顺序可避免不必要的复杂计算。理论基础统一：极小极大定理保证解的存在性，无差异原理提供求解的等式条件，LP对偶定理给出极小极大定理的构造性证明。三者构成完整的理论链条。方法间联系：图解法本质是二维LP的几何可视化；优超原则对应LP中的冗余约束消除；鞍点存在等价于LP有整数最优解（纯策略）。适用边界：鞍点法仅适用于有纯策略解的情形；图解法限于2×n或m×2；LP适用于任意有限矩阵但计算量随规模增长；大规模问题可考虑迭代算法。核心能力要求：学生应能判断何时用何种方法、正确建立LP模型、从LP解还原对策解、并用无差异原理验证结果的正确性。1鞍点判定→2优超化简→3图解法/LP→验证求解理论基础：极小极大定理·无差异原理·LP对偶CHAPTER03第三矩阵对策的求解n人非合作博弈·纳什均衡·合作博弈·Shapley值·核心GAMETHEORYNON-COOPERATIVEGAMESn人非合作博弈的标准形式n人非合作博弈由局中人集合、各自的策略空间和支付函数三元组定义，是矩阵对策向多人非零和情形的推广。其核心特征是策略相互依赖与非零和性：每个局中人的支付取决于所有人的策略组合，且各方利益不完全对立。标准形式定义：n人非合作博弈记为Γ={N,{Si},{ui}}，其中N={1,…,n}为局中人集合，Si为局中人i的策略集，ui:S1×…×Sn→R为i的支付函数。策略相互依赖：局中人i的支付ui(s1,…,sn)不仅取决于自己的策略si，还取决于所有其他局中人的策略组合s-i，体现了策略互动。输的结局。这与二人零和博弈的严格对抗本质不同。非合作假设：局中人独立决策，不能达成有约束力的协议或侧支付。即使合作对所有人有利，也无法强制执行合作协议。有限博弈表示：当所有Si有限时，博弈可用多维支付张量表示。例如三人各有两个策略时，需2×2×2=8个支付三元组。规模增长迅速，故常用函数或矩阵族描述。MATRIXGAMES·LECTURE2020/34GAMETHEORYDEFINITION&PROPERTIES纳什均衡的定义与性质纳什均衡是非合作博弈的核心解概念：一个策略组合是纳什均衡，当且仅当每个局中人的策略都是对其他所有人策略的最优反应，无人有动机单方面偏离。它是一种自我实施的稳定状态，纳什1950年的存在性定理保证了有限博弈混合策略纳什均衡的存在。1纯策略纳什均衡策略组合s*=(s₁*,…,sₙ*)是纳什均衡，若对每个i∈N和每个sᵢ∈Sᵢ，都有uᵢ(sᵢ*,s*₋ᵢ)≥uᵢ(sᵢ,s*₋ᵢ)，即sᵢ*是对s*₋ᵢ的最优反应。2最优反应对应局中人i对其他人的策略s₋ᵢ的最优反应集BRᵢ(s₋ᵢ)=argmaxuᵢ(sᵢ,s₋ᵢ)。纳什均衡即满足sᵢ*∈BRᵢ(s*₋ᵢ)对所有i成立的s*。3自我实施稳定性纳什均衡是"自我实施"的——一旦所有局中人都按均衡策略行动，没有人能通过单方面偏离获益。这种稳定性不需要外部强制力维持。4多重性与不存在性纳什均衡可能不唯一（如协调博弈有多个均衡），也可能不存在纯策略纳什均衡（如匹配硬币博弈）。但混合策略纳什均衡在有限博弈中一定存在。5纳什存在性定理（1950）任何有限n人非合作博弈至少存在一个混合策略纳什均衡。证明基于Brouwer或Kakutani不动点定理，是博弈论最重要的存在性结果之一。核心直觉：纳什均衡=每个人都选择了"对他人最优反应"的策略→无人愿意偏离→系统自动稳定ANALYSISGAMETHEORY囚徒困境与纳什均衡分析囚徒困境揭示了纳什均衡的核心特征与局限：占优策略均衡(D,D)是唯一纳什均衡，但帕累托劣于(C,C)。这体现了个体理性与集体理性的根本冲突——非合作博弈的均衡结果不一定是社会最优的。01博弈设定两嫌疑犯各有坦白(D)和抵赖(C)两种策略。支付矩阵以负刑期表示收益。02占优策略分析对局中人1：若2选D则D得-8优于C得-10；若2选C则D得0优于C得-2。D是1的严格占优策略，对称地D也是2的严格占优策略。03纳什均衡识别(D,D)是唯一纳什均衡——双方均在做最优反应。尽管(C,C)对双方更优，但任何一方都有偏离动机，故非均衡。04帕累托无效性均衡(D,D)被(C,C)帕累托占优，个体理性导致的均衡结果非集体最优，是非合作博弈的典型困境。05现实意义广泛存在于军备竞赛、价格战、公地悲剧等场景。解决途径包括重复博弈、契约设计与制度安排。PAYOFFMATRIX·支付矩阵局中人2

局中人1D（坦白）

-8,-8★纳什均衡

0,-10C（抵赖）-10,0

-2,-2帕累托最优

纳什均衡帕累托最优(-8,-8)均衡支付·非最优(-2,-2)合作支付·帕累托优NASHEQUILIBRIUMGameTheory·Lecture23混合策略纳什均衡混合策略纳什均衡将纯策略均衡推广到概率分布空间，保证了有限博弈均衡的存在性。其核心求解条件是无差异原理的推广：均衡下正概率纯策略的期望支付相等且不低于其他策略。该条件将均衡求解转化为方程组问题，但计算复杂度随局中人和策略数快速增长。01混合策略定义—局中人i的混合策略σi是Si上的概率分布。n人混合策略组合σ=(σ1,…,σn)下的期望支付Ui(σ)=Es~σ[ui(s)]，对各i独立计算。02均衡定义—σ*是混合策略纳什均衡，若对每个i和每个σ'i，Ui(σ*i,σ*−i)≥Ui(σ'i,σ*−i)。即σ*i是对σ*−i的最优反应（在混合策略空间中）。03无差异条件—σ*是均衡当且仅当对每个i，所有在σ*i支撑集中的纯策略对σ*−i的期望支付相等，且不低于支撑集外纯策略的期望支付。04求解方法—利用无差异条件建立方程组（正概率策略期望支付相等+概率归一化），求解候选均衡后验证不等式条件。小规模可手算，大规模需数值算法。05计算复杂性—混合策略纳什均衡的求解是PPAD-complete问题，不存在多项式时间算法（除非P=PPAD）。实践中对小规模博弈可用支持枚举法，大规模用Lemke-Howson等算法。COOPERATIVEGAMES合作博弈的特征函数形式合作博弈用特征函数v:2N→R描述，v(S)表示联盟S能保证的总收益。TU博弈假设收益可自由转移，核心问题是如何将大联盟的收益v(N)公平分配给各成员。不同的公平标准导出了核心、Shapley值、核仁等不同的解概念。01特征函数定义—TU博弈是一个对(N,v)，其中N={1,…,n}为局中人集合，v:2N→R为特征函数，v(S)表示联盟S⊆N能保证获得的总收益，通常规定v(∅)=0。02可转移效用假设—TU博弈假设联盟收益可在成员间自由转移（如货币支付），因此只需关注总收益v(S)的分配，不需考虑效用的不可比性。NTU博弈则放松此假设。03单调性与超可加性—常见假设包括单调性（S⊆T⇒v(S)≤v(T)）和超可加性（S∩T=∅⇒v(S)+v(T)≤v(S∪T)），后者保证合作不比单干差，是大联盟形成的激励基础。04分配问题—合作博弈的核心问题是寻找分配向量x=(x1,…,xn)使得Σxi=v(N)（有效性），且满足某种公平性或稳定性标准。不同标准导出不同解概念。05与非合作博弈的关系—合作博弈可视为非合作博弈的"简化"——忽略策略细节，直接关注联盟收益。特征函数v(S)本身可由非合作博弈的均衡结果导出（如极小极大表示）。COOPERATIVEGAMESDEFINITION核心（Core）的定义与性质核心是合作博弈中基于稳定性的解概念：一个分配属于核心，当且仅当它有效且不被任何联盟反对（即每个联盟获得的分配总额不低于其特征函数值）。核心中的分配保证了大联盟的稳定性，但核心可能为空集。核心非空的充要条件由Bondareva-Shapley定理给出。核心定义：分配x∈Rn属于核心C(v)，若满足：(1)有效性Σi∈Nxi=v(N)；(2)群体理性Σi∈Sxi≥v(S)对所有S⊆N成立。稳定性解释：群体理性条件意味着没有联盟S能通过脱离大联盟获得更高总收益。核心中的分配使大联盟"稳定"——没有子联盟有动机分裂。核心可能为空：并非所有TU博弈都有非空核心。例如简单的三人多数博弈v(S)=1（当|S|≥2）否则0，其核心为空。空核心意味着不存在稳定的分配方案。Bondareva-Shapley定理：核心非空的充要条件是博弈是平衡的——对N的每个平衡权重系{λS}，ΣSλSv(S)≤v(N)。这是核心存在性的完整刻画。凸博弈核心非空：若v是凸博弈（即v(S)+v(T)≤v(S∪T)+v(S∩T)对所有S,T成立），则核心一定非空且为多面体。凸博弈中Shapley值属于核心。EXAMPLECOOPERATIVEGAMES核心计算例题通过三人博弈例题演示核心的计算流程：列出有效性等式和所有联盟的群体理性不等式，求解线性不等式组。本例核心非空，(1,2,2)是一个可行分配。1博弈设定—N={1,2,3}，v({1})=v({2})=v({3})=0，v({1,2})=2，v({1,3})=3，v({2,3})=4，v(N)=5。大联盟总收益为5。2有效性约束—x₁+x₂+x₃=v(N)=5。这是核心的等式约束，确保分配耗尽大联盟的全部收益。3群体理性约束—x₁≥0,x₂≥0,x₃≥0（单人联盟）；x₁+x₂≥2,x₁+x₃≥3,x₂+x₃≥4（双人联盟）。共6个不等式。4可行性验证—三双人约束相加得2(x₁+x₂+x₃)≥9⇒5≥4.5，兼容。由x₂+x₃≥4得x₁≤1；由x₁+x₃≥3得x₂≤2；由x₁+x₂≥2得x₃≤3。核心非空。5核心分配示例—(1,2,2)满足所有约束：1+2+2=5,1+2≥2,1+2≥3,2+2≥4,各分量≥0。核心是一个凸多面体，(1,2,2)是其中一个顶点。要点：核心计算本质上是线性可行性问题，可用线性规划（LP）方法系统求解。当约束相容时核心非空，否则核心为空集。S矩阵对策讲义COOPERATIVEGAMESDEFINITIONShapley值的定义与直觉Shapley值将每个局中人的分配定义为其在所有可能加入顺序下的平均边际贡献，权重为局中人以某子集为前驱集的组合概率，体现"按贡献分配"的公平原则。排列视角—考虑N的所有n!个排列π。局中人i在排列π中的边际贡献为Δi(π)=v(Pπ(i)∪{i})−v(Pπ(i))，其中Pπ(i)为π中i之前的玩家集。Shapley值公式—φi(v)=(1/n!)ΣπΔi(π)=ΣS⊆N\{i}[|S|!(n−|S|−1)!/n!]·[v(S∪{i})−v(S)]。权重系数为组合概率。权重解释—系数|S|!(n−|S|−1)!/n!恰好等于在随机均匀排列中，局中人i的前驱集恰好为S的概率。因此Shapley值是边际贡献的期望值。公平直觉—Shapley值体现了"按贡献分配"的公平原则——每个人获得的份额等于他在各种合作情境下对联盟的平均边际贡献，不多也不少。计算复杂度—直接按公式计算需枚举2n−1个子集，指数级复杂度。但对特殊结构的博弈（如加权投票博弈）有高效算法；也可用采样近似。AXIOMATICSPAGE28Shapley值的公理化刻画Shapley定理（1953）证明：有效性、对称性、虚拟人公理和可加性四条公理唯一确定了Shapley值——它是唯一同时满足这四条基本公平性要求的分配规则，公理化刻画赋予其不可替代的理论地位。E有效性EfficiencyΣi∈Nφi(v)=v(N)分配耗尽大联盟的全部收益，既不浪费也不超额。这是任何合理分配规则的基本要求。S对称性Symmetryv(S∪{i})=v(S∪{j})∀S⊆N\{i,j}若局中人i和j在所有联盟中贡献相同，则φi(v)=φj(v)。名字标签不影响分配结果。N虚拟人公理NullPlayerv(S∪{i})=v(S)∀S⟹φi(v)=0若局中人对任何联盟无贡献，则获得零分配。不劳者不得，排除搭便车者获得正分配。A可加性Additivityφ(v+w)=φ(v)+φ(w)两个独立博弈的合成博弈的分配等于各自分配之和，保证分配规则对项目分解具有一致性。Shapley唯一定理满足有效性、对称性、虚拟人公理和可加性四条公理的分配规则φ存在且唯一，即为Shapley值——这一定理确立了Shapley值在合作博弈理论中的核心地位。COOPERATIVEGAMESShapley值计算例题通过与核心计算相同的三人博弈演示Shapley值的完整计算过程：枚举所有6个排列，计算每个排列下各局中人的边际贡献，取平均得到Shapley值。结果显示φ=(5/6,11/6,14/6)，与核心分配(1,2,2)不同但同属合理分配，体现了解概念的多样性。01博弈回顾N={1,2,3}，v({1})=v({2})=v({3})=0，v({1,2})=2，v({1,3})=3，v({2,3})=4，v(N)=5。与核心计算例题相同，便于对比两种解概念。02排列枚举共3!=6个排列：(1,2,3)、(1,3,2)、(2,1,3)、(2,3,1)、(3,1,2)、(3,2,1)。对每个排列依次计算三人的边际贡献。03边际贡献计算以(1,2,3)为例：Δ₁=v({1})−v(∅)=0，Δ₂=v({1,2})−v({1})=2，Δ₃=v(N)−v({1,2})=3。类似计算其余5个排列下各局中人的边际贡献。04Shapley值结果φ₁=5/6，φ₂=11/6，φ₃=14/6。验证：5/6+11/6+14/6=30/6=5=v(N)，满足效率性公理。05与核心对比Shapley值(5/6,11/6,14/6)≈(0.83,1.83,2.33)与核心分配(1,2,2)不同。Shapley值不一定属于核心，但在凸博弈中一定属于核心。边际贡献计算表排列Δ₁Δ₂Δ₃合计(1,2,3)0235(1,3,2)002—(2,1,3)2035(2,3,1)004—(3,1,2)300—(3,2,1)020—Σ/65/6——Shapley值分配φ₁=5/6≈0.83φ₂=11/6≈1.83φ₃=14/6≈2.33对比核心(1,2,2)：Shapley值将更多收益分配给局中人3（边际贡献最大），局中人1所得略少。两种解均满足效率性与个体理性，体现了合作博弈中"公平"的多重定义。M矩阵对策讲义COOPERATIVEGAMESOWENVALUE联盟结构博弈与Owen值当合作博弈中存在预定义的联盟结构C={C₁,...,Cₘ}时，Owen值将Shapley值推广为两步分配：先在商博弈中按Shapley值分配各联盟的总收益，再在各联盟内部按Shapley值二次分配。Owen值兼顾了联盟间与联盟内的公平性，是处理分层合作结构的标准解概念。联盟结构博弈三元组(N,v,C)，其中C={C₁,…,Cₘ}是N的划分（Cᵢ互不相交且并为N）。每个Cₖ称为一个联盟或union，是对标准TU博弈的结构化扩展。商博弈以联盟为玩家的博弈(M,v^C)，其中M={1,…,m}，v^C(Q)=v(∪_{k∈Q}Cₖ)对Q⊆M。商博弈描述了联盟层面的合作收益。Owen值两步法第一步，在商博弈中计算各联盟的Shapley值Shₖ(M,v^C)，得到联盟k的总收益；第二步，在联盟Cₖ内部的诱导子博弈中再次用Shapley值分配该总收益给成员。公平性双重保障Owen值既保证了联盟间的公平（商博弈Shapley值），又保证了联盟内成员间的公平（内部Shapley值）。当C为平凡划分时退化为标准Shapley值。应用场景政党议会席位分配、企业集团利润分割、跨国合作项目收益分配、供应链联盟成本分摊等存在自然分