4均衡解的求法 当参与者人数和每个人的纯策略数不太大时，我们完全可以像例1和例2 的分析那样，用枚举法逐个验证每个纯策略情形是否是纳什均衡。对于高维情形， 这里给出了两种确定均衡解的方法。 4.1优势法 如果对任何n维策略向量$，p($;S)>p($;s),那么就称s比s严格优。 这就是说不管其他人采取何种策略，参与人ⅰ采取混合策略s得到的支付总是大 于采取s所得到的支付。为了判断出s是否较s严格占优，由于支付函数p的n元 线性性质，我们只需考虑其他参与人的纯策略就够了。 一对混合策略的占优关系往往带来其他占优关系。假设s比S严格优，且t 用到了在$中系数比在$，中系数大的所有纯策略，则对充分小的整数p t=t+p(s;-si) 是一个混合策略，并且据线性性质，t比t严格优。 由均衡解的定义显然可知，均衡解必不包括严格劣策略$。这给我们启发， 在找均衡解的过程中，严格劣策略的集合可以排除。 我们可以证明非劣势策略集的一些性质。它是单连通的，由策略单纯形的一 些面组成。 定理3严格劣策略消去法必不会消去Nash eq. 证明： 设(s1,S2,,Sn)是一个纳什均衡，且在某个过程中s*是上述策略向量 中第一个被消去的策略。则在该时刻存在某s,使得 p(S1,S2,,Si-1,S*,Si+1,,Sn <p(S1,S2,,S-1,S,Si+1,,Sn) 对当时所有未被消去的s1,S2,,S-1,S+1,…,Sn成立 因s*是第一个被消去的
4 均衡解的求法 当参与者人数 n 和每个人的纯策略数不太大时，我们完全可以像例 1 和例 2 的分析那样，用枚举法逐个验证每个纯策略情形是否是纳什均衡。对于高维情形， 这里给出了两种确定均衡解的方法。 4.1 优势法 如果对任何 n 维策略向量$， pi $；s i ' > pi $；si ，那么就称s i '比si严格优。 这就是说不管其他人采取何种策略，参与人 i 采取混合策略s i '得到的支付总是大 于采取si所得到的支付。为了判断出s i '是否较si严格占优，由于支付函数pi的 n 元 线性性质，我们只需考虑其他参与人的纯策略就够了。 一对混合策略的占优关系往往带来其他占优关系。假设s i '比si严格优，且ti 用到了在si中系数比在s i '中系数大的所有纯策略，则对充分小的整数ρ t i ' = ti + ρ s i ' − si 是一个混合策略，并且据线性性质，t i '比ti严格优。 由均衡解的定义显然可知，均衡解必不包括严格劣策略si。这给我们启发， 在找均衡解的过程中，严格劣策略的集合可以排除。 我们可以证明非劣势策略集的一些性质。它是单连通的，由策略单纯形的一 些面组成。 定理 3 严格劣策略消去法必不会消去 Nash eq. 证明： 设 s1 ∗，s2 ∗，……，sn ∗ 是一个纳什均衡，且在某个过程中si∗是上述策略向量 中第一个被消去的策略。则在该时刻存在某s i '，使得 pi s1，s2，…，si−1，si∗，si+1，…，sn < pi s1，s2，…，si−1，s i '，si+1，…，sn 对当时所有未被消去的s1，s2，…，si−1，si+1，…，sn成立. 因si∗是第一个被消去的
故上式对s1*,S2,…,5-1*,S+1,,Sn*成立，即 p(S1*,S2*,,sn）<p(S1*,S2,…,S1-1*,Si,S+1,,sn*) 这与(S1,S2*,,Sn)是纳什均衡矛盾。 定理4有限博弈中，严格劣策略消去法最后留下的必是Nash eq. 证明： 设最后留下的是(S1*,S2,,Sn)且它不是纳什均衡，则存在s,使 p(S1,s2,,5n)<p(S1,52*,,Si-1*,Si,S+1*,,Sn*)① 而$在某个过程中被消去，说明在某个时刻 P1(S1,S2,,Si-1,S,Si+1,,Sn) <p(S1,s2,,S-1,S,S+1,,Sn) 对剩下的所有策略成立 因此 p(S1*,S2,,S-1*,S,Si+1',,Sn*) <p(S1,s2',…,S-1,S,Si+1,,Sn')② (1)若s=s,①与②矛盾。 (2)若s≠S,重复上述过程，存在s",使 p(S1*,S2,,S-1*,S,S+1*,,Sn <p(S1*,S2*,,51-1*,S",Si+1',,5n) 如此下去总能找到某个s0=S,矛盾 例3囚徒困境 甲、乙两个嫌疑人涉嫌谋杀，被警方逮捕。他们被关在两个独立的牢房里， 警长告诉他们，如果两人均承认罪行，则都要被监禁8年；如果一人认罪一人抵 赖，则抵赖者将被监禁15年，另一人无罪释放。但他们心里明白，如果两人都 拒不承认，均只需被监禁1年。这个博弈问题的支付矩阵如下
故上式对s1 ∗，s2 ∗，…，si−1 ∗，si+1 ∗，…，sn ∗成立，即 pi s1 ∗，s2 ∗，……，sn ∗ < pi s1 ∗，s2 ∗，…，si−1 ∗，s i '，si+1 ∗，…，sn ∗ 这与 s1 ∗，s2 ∗，……，sn ∗ 是纳什均衡矛盾。 定理 4 有限博弈中，严格劣策略消去法最后留下的必是 Nash eq. 证明： 设最后留下的是 s1 ∗，s2 ∗，……，sn ∗ 且它不是纳什均衡，则存在s i '，使 pi s1 ∗，s2 ∗，……，sn ∗ < pi s1 ∗，s2 ∗，…，si−1 ∗，s i '，si+1 ∗，…，sn ∗ ……① 而s i '在某个过程中被消去，说明在某个时刻 pi s1，s2，…，si−1，s i '，si+1，…，sn < pi s1，s2，…，si−1，s i ''，si+1，…，sn 对剩下的所有策略成立. 因此 pi s1 ∗，s2 ∗，…，si−1 ∗，s i '，si+1 ∗，…，sn ∗ < pi s1 ∗，s2 ∗，…，si−1 ∗，s i ''，si+1 ∗，…，sn ∗ …………………② （1） 若s i ' ' = si∗，①与②矛盾。 （2） 若s i ' ' ≠ si∗，重复上述过程，存在s i '''，使 pi s1 ∗，s2 ∗，…，si−1 ∗，s i ''，si+1 ∗，…，sn ∗ < pi s1 ∗，s2 ∗，…，si−1 ∗，s i '''，si+1 ∗，…，sn ∗ 如此下去总能找到某个s i ' n = si∗，矛盾 例 3 囚徒困境 甲、乙两个嫌疑人涉嫌谋杀，被警方逮捕。他们被关在两个独立的牢房里， 警长告诉他们，如果两人均承认罪行，则都要被监禁 8 年；如果一人认罪一人抵 赖，则抵赖者将被监禁 15 年，另一人无罪释放。但他们心里明白，如果两人都 拒不承认，均只需被监禁 1 年。这个博弈问题的支付矩阵如下