第四章_对策论.pptVIP

方法3：方程组法 由定理3知，求矩阵对策的解等价于求解不等式方程组（1），（2）。又由定理4和5知，若最优策略中的 均不为0，则可将以上的两个不等式组的求解问题转化为下面两个方程组的求解问题： 注：此方法要求 均不为0，所以，当最优策略的某些分量实际为0时，以上两个方程组可能无解。 这说明此方法在实际应用中有一定的局限性。 特别：对2×2的矩阵，若局中人的赢得矩阵没有鞍点时，各局中人的最优策略中的 都大于0。即对于这种问题，是可以采用方程组法求解的。 例：求解矩阵对策G，其中A为 解：利用优势原则，化简矩阵： 因为a4优超于a1，a3优超于a2，所以化简为 又因为b1优超于b3，b2优超于b4,b5，所以化简为 又因为a1优超于a3，化简为 容易看出矩阵A3没有鞍点，所以可以用方程组法解之。 对应的方程组为： 求解，得 所以，以矩阵A为赢得矩阵的对策的一个解为 例（齐王与田忌赛马） 这个问题中齐王和田忌各自拥有的策略为： S1={(上中下),(上下中),(中上下),(中下上),(下中上),(下上中)} S2={(上中下),(上下中),(中上下),(中下上),(下中上),(下上中)} 则对应的齐王的赢得矩阵为 解：易知齐王的赢得矩阵没有鞍点，即没有最优纯策略 设齐王和田忌的最优混合策略分别为 由于齐王和田忌对策略集中的所有策略都有可能选择， 所以，可设 求解方程组 和 得 方法4：线性规划方法 由定理4知，求解矩阵对策可等价于求解互为对偶的线性规划问题（P）和（D）。 在问题（P）中，令 则问题（P）变为 上述问题等价于 同理，若令 问题（D）等价于 算 例 解得，最优策略为（1/3，0，2/3）和（1/3，0，2/3）， 最优值为7/3。 Nash 均衡 对前面所述的二人有限零和博弈，其中的均衡解就是Nash 均衡。 下面，针对一般的n人博弈，给出Nash均衡的定义。 博弈的标准式：称 叫做博弈的标准式， 其中，Si为第i个局中人的策略集； 是每个局中人选定某一策略时形成的局势； 是相应于该局势的第i个局中人的支付函数； Nash均衡：在有n个局中人的标准式 中，如果局势 满足：对每一个局中人i， 是至少不劣于他针对其他n-1个局中人所选策略 的最优反应策略，则称局势 是该博弈的一个 Nash均衡，即对任意的 ，有 或 是最优化问题 的解。 结论：在任何非合作有限博弈中，都至少存在一个Nash均衡。 定理2: 则 为对策G的解的充要条件 为：对任意的i=1,2,…,m;j=1,2,…,n,有 证明：设 为对策G的解，则由定理1，成立 因为纯策略是混合策略的特例，所以，（*）成立。 反之，若（*）成立，则 定理2说明：要验证 为对策G的解时，只需要 对上式给出的有限个（m×n）不等式进行验证即可，大大简化了验证过程。 如此，便有了下面的等价定理－定理3 定理2得证。 定理3: 则 为：存在数v，使得 为对策G的解的充要条件 分别为不等式组(1),(2)的解, 且v=VG 定理4:任一矩阵对策G，一定存在混和策略意义下的解。 证明:由定理2知，只需证明存在 使得（*）式成立。所以，考虑如下规划问题 易知，规划问题（P）和（D）互为对偶问题，且 分别为（P）和（D）的一个可行解。由对偶定理知，他们都存在最优解，且最优目标值相等。即，存在 和 使得对任意的i=1,2,…,m;j=1,2,…,n有 或 又由 得 所以,(*)得证。 定理5:设 是矩阵对策G的解，v=VG，则 证明:由 有 又因为 所以，当 时，必有 当 时，必有 同理，可证（2），（4）。 优 超（优势原则） 算 例 简 化 简 化 第四节 混和策略的解法 方法1：图解法 　　以　　分别表示局中人　的第1、2纯策略；　　　表示局中人 　的第1、2、3个纯策略。 　　设局中人　采用混合策略　　　　　　，这里　　　　，当 　　　代表纯策略　；　　代表纯策略　。 　　若局中人 采用纯策略　，当　　时，局中上人A获得的期望支付为　，当 时，局中人A获得的期望支付为 ，连接直线　，则线段 上点的纵坐标表示局中人　采用混合策略 　　 ，而局中人　采用纯策略　时的期望支付。 　 同样 ,　和　上点的纵坐标分别表示局中人　采用混合策略 ，而局中人　采用纯策略　和　时的期望支付。 a b c d f e x 1-x 局中人A 局中人B 图　4-1 　　对于局中人　的每一个混合策略　，他至少得到三条直线在 处纵坐标的最小值，即 图4-1中的粗折线表示 这个最小值函数。 　　局中人　希望选择一个　，使上面这个最小值