完全信息静态博弈及其纳什均衡解.docx

第三章 完全信息静态博弈及其纳什均衡解
1. 完全信息静态博弈
定义 3.1.完全信息静态博弈。完全信息静态是指，博弈中的参与人同时采取行动，或者尽管参与人行动的采取有先后顺序，但后行动的人在行动时不知道先采取行动的人采取的是什么行动；同时博弈参与人的策略空间及策略组合下的支付是博弈中所有参与人的“公共知识”。
两个特点：（1）静态；（2）完全信息。
完全信息静态博弈例子。
例1：锤子-剪刀-布
例2：交通行驶
甲
乙
左
右
左
1,1
0,0
右
0,0
1,1

非“完全信息静态博弈”例子：英式拍卖——动态博弈；第一密封价格及第二密封价格拍卖——不完全信息博弈。
2. 纳什均衡及其判定
定义3.2 纳什均衡。在一个n人博弈的标准式G={S1,S2，…,Sn; u1,u2,…,un}中，一个策略组合{s1*,s2*,…，sn*}，若满足ui(s1*,…,si*,…sn*)≥ui(s1*,…si,…，sn*)（i=1…n），则称这个策略组合为{s1*,s2*,…，sn*}为该博弈G的一个纳什均衡。
某策略组合是纳什均衡指的是，在该策略组合上任何一个参与人的收益在其他人策略不改变的情况下都至少是弱优的。
特点：（1）每个人没有单独改变策略的动机；（2）局部最优。
纳什均衡判定方法：用定义来判定：某点是均衡看它是否符合纳什均衡的定义。
求解纳什均衡的方法：
（1）剔除严格被占优策略。
例3：囚徒困境
甲
乙
不合作
合作
不合作
2,2
1,4
合作
4，1
3,3
缺点：只有当仅有一个纯策略均衡点的时候，该方法才是有效的。
（2）用定义来求解
（3）对于策略空间为连续的博弈，用求极值的方法来求得。

3. 纳什均衡存在定理：
（纳什）定理3.1.在一个n人博弈的标准式G={S1,S2，…,Sn; u1,u2,…,un}中，如果n是有限的，且对每个i, Si是有限的，则博弈至少存在一个纳什均衡。这里的均衡可能包含混合策略均衡。
证明：略
例子3：囚徒困境的均衡
例1：“锤子-剪刀-布”的均衡？
甲
乙
锤子
剪刀
布
锤子
0,0
1,-1
-1,1
剪刀
-1,1
0,0
1，-1
布
1，-1
-1,1
0,0

4. 混合策略与混合策略的均衡
纯策略与混合策略概念。
定义.3.3.一个策略是纯策略指的是参与人策略空间中的某个确定策略；而一个混合策略是参与人策略空间上的一个概率分布，一般地，某个人i的策略空间为{si1,si2,…，sik},则参与人i在策略空间上的一个概率分布pi=(pi1,pi2,…，pik)构成他的一个混合策略，其中pi1+pi2+…+pik=1。
如：在取经的过程中猪八戒的策略空间为{西天取经，散伙（回高老庄）}，“采取西天取经”（或“采取回高老庄”）是纯策略。而“70%的可能性采取西天取经、30%的可能性回高老庄”为猪八戒的一个混合策略。沙僧采取纯策略（西天取经）；而孙悟空也在采取混合策略，只不过“西天取经”的概率比较高。由此可见，这里的混合策略中的概率分布体现了参与人采取某个策略的意志或忠诚程度。
混合策略体现了参与人选择纯策略的不确定性，它的引入使博弈有完美的数学解。然后，该概念自上世纪80年代一直被人们认为“直觉上有问题的”。混合策略的核心是随机性。但它缺乏支持：人们怎么会通过投掷骰子来进行选择呢？人们不会随身带着随机发生器。
三个解释：第一，Ariel Rubinstein（1991）解释说，它反映我们对参与人的信息和进行决策的过程没有足够的知识；但这种解释不令人满意。第二，想象一个参与人群体。混合策略反映被选择的纯策略的分布；但这种解释不能说明个体进行这样选择时的选择。第三， Aumann and Brandenburger (1995)将纳什均衡重新解释成信念中的均衡而不是行动中的均衡：参与人对其他人采取各个策略的可能性的信念。这种解释弱化了纳什均衡的解释力，因为这是可能的：在这样的均衡中每个参与人实际上采取纯策略。
混合策略均衡案例：
例4.田忌赛马
分析：
1. 田忌每次均输，是因为他采取了纯策略，对方也采取了纯策略——不是均衡点（表中的对角线上的点）；
2. 田忌改变策略，采取了孙膑的方法，偏离均衡点，此时，在对方不改变策略的情况下收益提高，而获胜。此点（如图中*标明的点）是均衡点吗？
3. 均衡策略是什么？

齐王
田忌
上中下
上下中
中上下
中下上
下上中
下中上
上中下
-3,3
-1,1
-1,1
1*，-1*
-1,1
-1,1
上下中
-1,1
-3,3
1，-1
-1,1
-1,1
-1,1
中上下
-1,1
-1,1
-3,3
-1,1
-1,1
1，-1
中下上
-1,1
-1,1
-1,1
-3,3
1，-1
-1,1
下上中
1，-1
-1,1
-1,1
-1,1
-3,3
-1,1
下中上
-1,1
1，-1
-1,1
-1,1
-1,1
-3,3

均衡策略是：齐王与田忌均随机化他的出马顺序，即双方都应当采取混合策略。对于齐王与田忌，将“上”、“中”、“下”安排在第一次、第二次及第三次的概率是相同的，均为1/3。每次比赛是上述36个可能性中的一个，并且它们是等可能性的。因此，当他们采取这样的均衡策略下， 齐王能够“赢”的概率为30/36=5/6，田忌能够“赢”的概率为6/36=1/6。此时，
田忌的期望收益为:-3*6/36+1*6/36+-1*6/36=-1，
齐王的期望的收益为1
例2：交通通行中有三个纳什均衡点。这三个均衡为（左，左）、（右，右）和甲乙均以1/2走“左”，1/2的概率走“右”。

4. 混合策略均衡的计算
因为参与人决不会使用较低期望支付的策略，在一个纳什均衡中，如果参与人的两个纯策略都有正的概率，那么这两个策略在这个均衡中一定给他相同的期望支付。即在均衡中，一个参与人必须对他在其随机策略中具有正概率的策略表现出无差异。
例5.性别之战。
妻子
丈夫
拳击q
歌剧1-q
拳击p
3,1
0,0
歌剧1-p
0,0
1,3

三个均衡:两个纯策略均衡（拳击，拳击）和（歌剧，歌剧）和一个混合策略均衡（随机策略均衡）：
若妻子选择“拳击”：
U2’=1*p+0*(1-p)
若妻子选择“歌剧”
U2’’=0p+3(1-p)
U2’=U2’’
P=0.75
同样可得：q=0.25
混合策略均衡为（0.75[拳击]+0.25[歌剧]，0.25[拳击]+0.75[歌剧]）
此时的期望收益均为0.75.

例6.警察与小偷的故事。
特征：零和博弈。
小偷
警察
A
B
A
3，0
2，1
B
1，2
3，0
给定警察选择A地的概率p,B地的概率1-p,
小偷：
Ua=2(1-p)
Ub=p
Ua=Ub:
p=2/3
给定小偷选择A地的概率为q,B地1-q，
警察：
U’a=3q+2(1-q)
U’b=q+3(1-q)
U’a=U’b:
Q=1/3
于是警察的期望收益：7/3;小偷的期望收益:2/3.

5. 案例：
例7.古诺模型。
两个厂商同时行动，各自决定产量。市场需求函数为p=a-Q。厂商的单位产品的成本c。这些是他们的公共知识。问：厂商所决定的生产产量q1,q2是多少采纳使他们利润最大？
分析：利润L1,2=p×q1,2-c×q1,2
=（a-Q）×q1,2-c×q1,2
其中Q=q1+q2
因此，原问题变为：
求L1,2=（a- q1-q2）×q1,2-c×q1,2极值
根据纳什均衡定义，均衡点处满足：
dL1,2/dq1,2=0
于是：
q1,2=(a-c)/3

Q=q1+q2
P=a-Q

假如市场上只有一个企业，即：垄断下的市场情况如何：
企业所确定的产量为Q：
L=pQ-cQ
=(a-Q)Q-cQ
dL/dQ=0:a-Q-Q-c=0
Q=（a-c）/2 (小于两个企业的产量总和：2(a-c)/3)
此时的价格为：p=(a+c)/2 (大于两个企业时的价格：(a+2c)/3)
利润为（a-c）2/4,(大于两个企业时的利润之和：2（a-c）2/9)

例8.鹰鸽博弈
三个均衡：（鹰，鸽）、（鸽，鹰）及一个混合策略均衡。

甲
乙
鹰
鸽
鹰
-3,-3
2,-2
鸽
-2，2
-1,-1

6.均衡的拓展：谢林的聚点均衡与奥曼的相关均衡
博弈论所研究的模型是现实的抽象。博弈论专家研究博弈期目的是为了预测，预测博弈参与人的策略选择及博弈结果。然而，当一个博弈包含不止一个纳什均衡时，我们往往无法对之预测。
为了解决这个问题，博弈论专家进行尝试。
焦点效应。在一个具有多重均的博弈中，某些事情使得一个博弈的参与人将注意力集中到一个均衡，使他们预期并实现这个均衡，这便是谢林所说的焦点效应。
一个焦点均衡（focal equilibrium）就是一个具有某种使它显著地区别于所有其他均衡之性质的均衡。
焦点又称为谢林点（Schelling point），这一概念最早由诺贝尔奖获得者谢林于1960年在《冲突的策略》一书中提出：“人们如果得知别人也正试图做出和自己同样的行为时，常常能使他们的意图或期望达成一致。大多数情况——或许每一种情况都能为此种博弈参与人的合作提供一些线索，为每个人的期望提供‘聚点’（focal point），其中每个人的期望是别人期望他期望被期望去做的事。” T. C. Schelling, The Strategy of Conflict . Harvard University Press, 1960, pp: 57.
也就是说，聚点是在协调博弈中博弈参与人通过相互期望所做出的共同选择形成的那个均衡点，它显示出了博弈中人们在没有沟通的情况下的共同选择倾向；或者说聚点就是参与人所选的最突出的那个解。
焦点均衡的两个例子。
例1.谢林曾经有过这样的实验：
“请选择下列数字中的一个，如果你们的选择相同，你们都将获胜。”
7 100 13 261 99 555
实验结果是在41人中37人选择了前三项，7略微领先于100，13位于第三位。 T. C. Schelling, The Strategy of Conflict . Harvard University Press, 1960, pp: 56.
可以看出，在这三项中，选择人数按数字排列的位置呈递降趋势。在谢林的实验中，聚点在选择第一个数上形成，协调博弈的结果与被选择对象呈现的次序有关。“如果问到在所有正数当中哪个是最明显独特的，或者什么样的选择规则将导致明确结果，人们将会受到这种事实的强烈影响：即最普遍的选择是‘第一个’或‘最小’的那个正数。” T. C. Schelling, The Strategy of Conflict . Harvard University Press, 1960, pp: 94.

谢林进行的其他一系列实验也验证了这种“位置优先性”：在“正面”和“反面”二者之间，聚点在选择“正面”形成；在十六个方块列成的矩阵之间，聚点在选择第一个方块时形成。从谢林的实验可以看出，在无差异的选择对象之间，被试往往倾向于选择位置处于第一个的对象。
另外的例子。
我们进行了一个关于协调博弈的实验：
请从‘2、7、8、9’这4个数字中选出一个数字，若你所选的数字为在座的同学中最多的人所选的，那么你将是获胜者，请解释你的选择。
该博弈作为南京大学文化素质课“逻辑与科学方法基础”选课学生考试题之一，即该实验是在考试中进行的（本题略带欺骗的性质，因为学生预先不知道该题做任何选择都给满分）。实验总人数：167人。在实验之前，学生没有听说过该类测试，在实验中学生之间没有任何交流。

表1
数字
2
7
8
9
其他
人数
54
15
86
7
5
比例（%）
32.34%
8.98%
51.50%
4.19
2.99%%

图1
实验数据如附表1所示，有51.50%的人“不约而同”地选择了“8”。按照题意，选“8”的人为胜出者。再进一步考察选“8”的理由可以看出，选“8”的86个答案中，有69个是根据公共知识进行推理得出的。他们的理由是：“8”在中国人心中有特殊意义，人们对8代表“发”了解最为广泛，买车牌号码、电话号码等都喜欢带8的，寓发财发达之意、是国人喜欢的吉利数字、幸运发财之数，这是公共知识。
奥曼的相关均衡
定义。相关均衡。在一个有通讯的博弈中一个相关均衡是博弈中所有参与人在调节人的帮助下能够自动执行的相关策略，而调解人向每个参与人做出不具约束力的秘密推荐。
这里，推荐的概率是公共知识；该均衡是自我强制的或自我约束力的。

X2
Y2
X1
5,1
0,0
Y1
4,4
1,5
两个纯策略均衡点（5,1）（1,5）和一个混合策略均衡，此时的支付为（2.5,2.5）。
相关均衡有多个，其中1/3[x1,x2]+1/3[y1,x2]+1/3[y1,y2]是使所有参与人的支付之和取得最大值的相关均衡（6.5）。

思考题：
1.例4中，假定市场上有n个企业,分析各个企业的均衡产量，并分析此时企业的利润、市场总产量。
2.两人分100美元，若各自提出的份额之和不超过100美元，则按照两人提议的分配；若超过，则两人一无所得。此时的纳什均衡是什么。
3.一条街上均匀分布着居民，有两个投资者准备在这条街道上开设商店。假定距离是唯一决定居民选择商店购买物品的因素，即居民选择离他最近的商店购买物品。问：这两个投资者选择何处开设商店才是均衡点？若投资者为个，情况如何？

附录
n人博弈的均衡点
J.纳什
普林斯顿大学
由莱夫舍茨（S. Lefschetz）推荐，1949年11月16日
我们可以定义n人博弈的概念：该博弈中，每一个参与人有一个纯策略的有限集，并且赋予每个参与人而构成的确定的支付集对应于每一个n维纯策略组（每一个参与人选择一个纯策略）。对于混合策略，它为纯策略上的概率分布，支付函数即为参与人的期望（expecta- tions），它是不同参与人选择不同的纯策略的概率的多重线性形式。
任何n维策略（每一个策略对应于一个参与人）可以看做是一个点，该点在这些参与人的n个策略空间的乘积而得到的积空间之中。一个这样的n维策略对抗另一个n维策略，指的是在这个n维对抗策略中，相对于其他n-1个参与人在被对抗的n维策略中的策略选择，每一个参与人都选择了能使他获得最高期望支付的策略。一个自我对抗的n维策略就称为均衡点。
每一个n维策略与它对抗的n维策略的集合的对应，给出了一个从积空间到其自身的一对多的映射。从对抗的定义我们可以看出，一个点的对抗点的集合是凸的。由支付函数的连续性可知，这个映射的图像是闭的。闭性等于说：如果P1，P2,…,Pn，…和Q1，Q2,…Qn，…均是积空间中的点列，其中Qn→Q，Pn→P，Qn与Pn对抗，那么Q与P对抗。
由于映射的图像是闭的并且每个点在该映射下的像是凸的，我们由角谷静夫（Kakutani）定理 Kakutani, S., Duke Math. J., 8, 457-459 (1941).
可推断出该映射有一个不动点（即，该点包含于它的象集里）。由此可知存在一个均衡点。
在二人零和博弈情形，其“主要定理”Von Neumann, J., and Morgenstern, O., The Theory of Games and Economic Be-haviour, Chap. 3, Princeton University Press, Princeton, 1947.
与均衡点的存在性是等价的。在这种情况下，参与人在两个均衡点都得到相同的预期值，但在一般的情况下，这不是必然的。
*作者感谢大卫.盖尔（David Cale）博士，是他建议利用角谷静夫定理来简化证明，同时感谢原子能委员会（A.E.C）在财力上的支持。
（原文：John F. Nash ，Equilibrium Points in n-Person Games，Proceedings of the National Academy of Sciences of the United States of America, Vol. 36, No. 1 (Jan. 15, 1950), pp. 48-49。韩飞译，潘天群校）

10