逆向归纳法的认知基础
崔晓红
1.引言
逆向归纳法是博弈论中一个比较古老的概念，它的提出最早可以追溯到泽梅罗（1913）针对国际象棋有最优策略解的证明，后来人们将其推广到了更广泛的博弈中，例如，在有限完美信息扩展型博弈中，就是用逆向归纳法（BI）来证明子博弈完美均衡（SPE）的存在以及求解SPE，其基本思路是从动态博弈中的最后一个阶段开始，局中人都遵循效用最大化原则选择行动，然后逐步倒推至前一个阶段，一直到博弈开始局中人的行动选择，其逻辑严密性毋庸置疑。然而，当从终点往前推到某一决策点时，BI完全忽略了到达该决策点的以往历史行动，而这一历史行动当然会影响处于该决策点的局中人有关其对手将来如何采取行动的信念，例如，一个局中人如果观察到对手在过去没有按照BI进行行动选择，那么他就有理由相信他的对手仍会采取同样的模式进行下去，但是通过这种信念修正以后所做的选择就会与BI矛盾。为了达到均衡解，为了能按BI进行推理求解，我们需要对局中人的信念或者说知识增加一些限制性条件，也就是说在什么样的前提下，BI是合理的，显然，仅仅要求每个局中人都理性是不够的，所有的局中人都必须知道所有的局中人都是理性的，所有的局中人都必须知道所有局中人都知道所有局中人都是理性的……等等以至无穷，在这样的认知条件基础下，我们就不会偏离BI，即，“在完美信息扩展型博弈中，理性的公共知识蕴含了BI”（Aumann 1995）。本文旨在通过构造完美信息扩展型博弈的认知模型来考察BI的这一认知条件。文章第二部分先通过一些简单例子对一些问题进行非形式上的讨论；第三部分介绍Aumann结构如何表达知识和信念；第四部分给出完美信息扩展型博弈的认知模型并用形式化的方给出BI的认知条件。
2. 实例分析
2.1 蜈蚣博弈
图1是一个长度为3的蜈蚣博弈，博弈每前进一个阶段，桌子上就增加一美元，局中人1，2轮流采取行动，轮到某个局中人采取行动时，他可以拿走桌子上的钱，博弈结束，或者钱留在桌子上继续博弈，另外，局中人都是理性的，也就是说都遵循期望效用最大化原
则。如图所示：
3
图1 蜈蚣博弈1
根据BI，此博弈有唯一子博弈完美均衡，那就是局中人1采取行动T1，拿走桌子上的一美元博弈结束。假设局中人1采取的行动是L1，并且桌子上又增加了一美元，此时由局中人2开始行动，这时的局中人2会觉得很奇怪，他最初是确定局中人1会根据BI进行推理拿走桌上的钱的，但局中人1并没有那样做，局中人2就想局中人1可能不理性，如果再来一次的话，说不定会给他留下三美元，如此盘算之后，局中人2就会理性地选择行动L2，希望继续博弈。现假设局中人1非常理性，并且认为局中人2也是理性人而且知道局中人2会对自己采取行动L1有如上分析的信念，那么局中人1一开始没有拿走那一美元是为了下一步行动能得到三美元。
那么在随后的博弈阶段即局中人1采取行动L1之后我们能不能假设存在有理性的公共信念，从而得到BI解呢？不可以。局中人1行动L1之后理性的公共信念是不可能的：如果局中人2相信局中人1是理性的，行动L1之后，他会拿走桌上的二美元；如果局中人1一开始相信局中人2是理性的并且相信局中人2在她采取行动L1之后仍然相信局中人1是理性的，那么她一开始就会拿走一美元结束博弈，现在局中人1在她采取行动L1后对局中人2的信念并没有发生变化，这样的话就有两种可能：（a）局中人1不理性选择了行动L1，或者（b）局中人1是理性的，采取行动T1，但是相信如果她选择策略L1的话，局中人2是理性的并且相信局中人1也是理性的，（a）和（b）相互排斥，局中人2在观察到行动L1后不会同时相信这两种可能。
2.2 有限次重复囚徒困境博弈
在一次性囚徒困境博弈中如图2所示，局中人各自从个人利益出发的理性选择结果（博弈解）就是（D，D）即（坦白，坦白），个体理性选择的结果并非帕累托最优，不符合集体理性的要求，囚徒陷入了理性的困境。
D
图2 有限次重复囚徒困境博弈
若这一博弈重复进行k 次，情况会有什么不同呢？假设局中人都知道重复的次数，并且能够观察到以往所有的博弈历史，即局中人在以往各阶段所实际采取的行动，且各阶段的支付如上图所示，显然这一博弈是完美信息扩展型博弈，且存在唯一子博弈完美均衡（SPE ）：局中人均采用坦白策略。这很容易由BI 推理得出：在最后一个阶段，局中人理性选择的结果就是囚徒困境唯一的纳什均衡，双方均“坦白”；这样，逆向归纳至前一阶段，局中人仍然以“坦白”策略为唯一理性选择。依次类推，可以知道SPE 中，局中人在每一阶段均会采用“坦白”策略作为自己的唯一选择。
但是，经由BI 得到的SPE 很不符合直观，现实生活中处于如此情境的局中人更愿意采取“针锋相对”（tit-for-tat ）策略，这一策略可以简述为：“你上次如何对我，我下次就怎么对你”，也就是说局中人都试图为了下次的博弈建立合作的声誉。现在我们来分析如果局中人都是理性的，并且都具有理性的公共知识（CKR ），最终得到的博弈解是“针锋相对”还是SPE 。现假设在CKR 基础上局中人采取策略C （合作）而不是D （对抗也即坦白），我们已经知道局中人采取合作的目的是为了下一次合作建立良好的声誉同时鼓励对方也这么做。但在博弈的最后阶段，双方都知道这是最后一次博弈并且是理性的，这里的理性独立于对对手采取策略的信念，于是在这一阶段大家都没有合作的动机，都将采取对抗（占优策略），而且，由于CKR ，他们也知道对方也会采取D ；而在博弈的倒数第二个阶段，局中人为下次博弈建立合作声誉是没有用的，于是局中人仍会采用对抗策略，如此反复直至博弈的第一个阶段，对抗策略一直是博弈的最优策略。
3. 知识和信念的语义表达
3.1 单个主体的知识和信念的表达
我们先从单个主体的信念出发，首先假设要考察的对象是一系列状态（state ）或可能世界，这里的状态或世界一般解释为局中人面对的所有与决策有关的外在因素的客观描述，记
3，3 1，4 4，1 2，2
C C D
为ω∈Ω，其中为状态空间。Ω的一个子集称为一个事件，用以描述博弈中发生的种种事件。如果ΩE ?ΩE ω∈，我们就说事件E 在状态ω处发生了。定义一个可能函数
:P ΩΩ→2是将每个状态ω∈Ω映射为Ω的一个非空子集，表示局中人在状态ω处认为()P ω中的状态都是可能的，它应满足如下性质：
性质3.1.1（1）()P ω≠?
（2）如果()P ωω′∈，那么()()P P ωω′? （3）如果()P ωω′∈，那么()()P P ωω′?.
定义3.1.1（信念框架）一个信念框架就是一个二元组F=,P Ω，其中状态集Ω≠，P 满足性质3.1的三条性质，它们分别又对应于关系的持续性，传递性以及欧性。
? 如果某一事件E 在局中人认为可能的状态()P ω中的每一状态都发生了，我们称局中人相信该事件，于是从可能函数P 就可以得到一个信念算子，定义为
:22B Ω→Ω},{:()E BE P E ωω??Ω=∈Ω?，满足如下三条性质：
性质3.1.2（1）B Ω=Ω （必然性） （2）()B E F BE BF =∩∩ （合取性） （3）如果，那么. （单调性） E F ?BE BF ?另外，对应于可能函数的三条性质，信念还有如下三条性质： 性质3.1.3（1） （一致性） ,E BE B ??Ω???E E BE E （2） （正内省） ,E BE BB ??Ω? （3） （负内省）
,E BE B ??Ω???（这里的符号“?”表示集合的补，即\E ?=Ω）另外我们都知道局中人相信的事件不一定真的发生，也就是说局中人相信的也可能是一个假象，但他相信自己所相信的是正确的。于是，我们说可能函数不具有自反性，但它具有二阶自反性：
,,ωω′?∈Ω如果(),P ωω′∈那么().P ωω′′∈于是也有：
,()E B BE E ??Ω?=Ω∪ 知识具有许多与信念相同的性质，但它们之间有一个显著的区别就是信念不必为真，而 所知道的一定是真的。为了表达它们之间的不同，我们首先引入信息函数。
设为一个状态集，上的一个划分可以表示局中人的信息或者说知识，我们说函数
ΩΩ:I ΩΩ→2是信息函数，如果它满足如下两条性质：
性质3.1.4（1）()I ωω∈
（2）如果()I ωω′∈，那么()()I I ωω′=
注意如果I 是满足以上性质的信息函数，它就是Ω的一个划分，相反，任何的一个划分 Ω也会生成一个信息函数I 。
由信息函数I ，我们同样能得到知识算子:22K ΩΩ→定义为： {:()}KE I E ωω=∈Ω?
于是我们有不同于信念的知识的性质：,E KE E ??Ω?又称为知识公理。 如果可能函数和信息函数有如下关系：,ωω′?∈Ω 性质3.1.5（R1）()()P I ωω?
（R2）如果()I ωω′∈，那么()()P P ωω′=
我们就说此时的信念是以信息为基础，且仅仅依赖于信息。从而有KB -框架; 定义3.1.2 ：一个KB -框架（知识和信念的框架）是一个三元组F =,.I P Ω使
得状态集，并且I 满足自反性，传递性和欧性，P 满足持续性，传递性和欧性且都 Ω≠?满足性质（R1）和（R2）.
相应于性质（R1）和（R2），知识和信念算子满足下面两个性质： 性质3.1.6 （1） ,E KE B ??Ω?E E （2）
,E BE KB ??Ω?在KB -框架下，局中人相信的仍有可能不是真的，而且仍然相信自己所相信的是正确的，但 是否相信自己知道自己所相信的却不一定。例如，设{,}ωω′Ω=，{}E ω′=，
()(){}P P ωωω′′==，()(){,}I I ωωωω′′==，显然有BE ω∈，但BKE ω?。现假设这
一条件成立，即 （C1） 成立，于是知识就坍塌成信念， ,E BE BK ??Ω?E E 即 （C2） ,E BE K ??Ω=这两个条件其实是等价的，我们现在给出证明。 命题3.1.1 （C1）等价于（C2）
证 （1）（C1）?(C2)
这个方向我们只需要证明，先假设BE KE ?ω?∈Ω，如果BE ω∈，由（C1）可知
BKE ω∈，由B 的定义，就有()P KE ω?，此时，ω′?∈Ω，如果()P ωω′∈，则KE ω′∈，
由K 的定义，有()I E ω′?，由性质3.1.5（R1）知()()P I ωω?，于是()I ωω′∈，再由 性质3.1.4（2）()()I I ωω′=，得到()I E ω?，从而有KE ω∈。 （2）（C2）(C1)
?假设,ω?∈Ω如果BE ω∈，由B 的定义，有()P E ω?，同时，由条件（C2）,我们有KE ω∈， 再由K 的定义，有()I E ω?，现对()P ωω′?∈，由性质3.1.5（R1）()I ωω′∈,再根据性 质3.1.4（2）有()()I I ωω′=，从而()I E ω′?，于是KE ω′∈，则()P KE ω?，再由B 的定义，就有BKE ω∈。 证毕
3.2 交互信念和公共信念
博弈论主要强调局中人策略选择的相互影响，在这种情况下，局中人对外部世界的信念尤其对其他局中人策略选择的信念以及信念的信念的分析就显得尤为重要。这一节我们设信念是初始概念，把知识看作一种特殊形式的信念，来讨论交互信念（或知识）以及公共信念（或知识）的语义表述。
定义3.2.1 一个交互信念框架是一个三元组F ＝,,{}i i N N P ∈Ω使得{1,,}N n =…是有穷 个体集，是状态的集合，并且对每个个体Ωi N ∈，:i P 2ΩΩ→是的满足持续性，传递 i 性和欧性的可能函数。个体i 的信念算子:22i B ΩΩ→定义为
,{:()i i E B E P }E ωω??Ω=∈Ω?。
为了定义公共信念算子B ?，我们先来定义e B 和k
B ，E ??Ω，令e i N i B E B ∈=∩E 意 思是每个人都相信E ；，，令E ??Ω1k ≥0
B E E =且1
k
k B E BB
E ?=，B ?可以定义如下：
1k e e e e e e k e B E B E B B E B B B E B E ?=∩∩∩…∩≥=2 也就是说某一事件被大家公共相信如果每个人都相信这一事件，每个人都相信每个人都相信这一事件，等等以至无穷。相应的公共可能函数可定义为：:P Ω?Ω→,(){:{}}P B ααωαω???∈Ω=∈Ω∈??满足如下性质：,,(P )ωωω?′′?∈Ω∈ω当且仅当存在N 中的序列1,,m
i i …和中序列
Ω
01,,m ηηη…使得（1）0ηω=
（2）m ηω′=
（3）对每个0,,1k m =?…，11()k k i P k ηη++∈ 即是的传递闭包。
P ?i N i P ∈∪这里有一点需要注意的是具有持续性和传递性，但不一定具有欧性。相应的公共信念算 P ?子B ?满足一致性（B E B ?????E ）和正内省（B E B B E ????），但不一定满足负内省（
B E B B E ??????）。例如，设123{,,}ωωωΩ=，11121()(){}P P ωωω==，133(){}P ωω=； 211222323(){},()(){,}P P P ωωωωωω===，则
112312(){},()(){,,}P P P 3ωωωωωωω???===，令1{}E ω=，则有3B E ω?∈?，但
3B B E ω????。
另外，我们有如果某一事件是被公共相信的，当且仅当每个人都相信这一事件是被公共相信的，即,i N i E B E B B ?∈E ???Ω=∩。
与公共信念算子的定义相类似，为定义公共算子K ?，我们先定义1n e i i K E K ==∩E 表示每个都知道E ，1m m e K E K ?≥=∩E ，于是I ?就可定义为(){:{}}I K αωαω??=∈Ω∈??，即i N i I ∈∪的传递闭包。
定义3.2.2 一个交互的KB -框架是一个四元组,,{},{}}i i N i i N F N P I ∈∈=Ω使得N 是有穷个体集，Ω是状态的集合，并且对每个个体i N ∈，:i P 2ΩΩ→是i 的可能函数，:2i I ΩΩ→是的信息函数。所满足的性质与单个主体的可能函数和信息函数以及KB -框架中所满足的性质一样。 i
4. 完美信息扩展型博弈的认知模型
4.1 完美信息扩展型博弈
扩展型博弈是对局中人序列采取行动这一动态特征的描述，而完美信息则是指局中人在
行动中知道博弈的所有以往行动历史。
定义4.1.1 一个完美信息扩展形式结构S 由以下几个部分组成：
? 有向图T = ( X, E )： X 是有穷结点集，是有穷有向边的集合。结点表示博弈中发生的情境；边（x ，y ）表示局中人从情境x 到情境y 时所采取的行动；对任意两个结点E X X ?×,x y X ∈，一个有向边的序列1122((,),(,),,(,))n n x y x y x y …称为从x 到y 的一条路径，如果1,n x x y y ==并且1k k y x +=对每个{1,,1}k n ∈?…；如果有一条从x 到y 的路径，我们就说x 是y 的前列结点，表示成x y ；设结点0x X ∈，对任意
0\{}x X x ∈，都有唯一一条从0x 到x 的路径，则称0x 为T 的根；结点x X ∈是终点如
果其后没有结点，终点集用Z 表示，不是终点的结点称为决策点。
? 局中人的集合N 和一个移动函数表示非终点x 处，由局中人
采取行动，对每个局中人i 来说，集合:\m X Z N →()m x N ∈{\|()i H x X Z m x i }=∈=为该局中
人的信息集的集合，完美信息就是指每个局中人的信息集为单点集。 ? 行动集：对每个局中人i 和i 的每个信息集i h H i ∈，如下有向边的集合 称为i 在信息集处的行动的集合。(){(,)|,(,)}i i i A h h y y X h y E =∈∈i h ()i i i h H i A A h ∈=∪为局中人i 全部可选行动构成的集合，()h H A A ∈h =∪表示所有行动的集合。
下面再定义策略，直观上来说，策略是局中人的行动计划，即在由局中人移动的每一 结点处该局中人应采取什么行动的一个方案，即使该结点并没有到达，但却可以看作是其他局中人对该局中人策略选择的一种信念。
定义4.1.2 局中人i 的策略是一个函数，对每一:i i s H A →i i i h H ∈，。局中人i 的策略空间为这样的的集合，也就相当于各个处的行动空间的笛卡尔乘积，即
。对于每一个策略组合()()i i i s h A h ∈i S i s i h ()i i
i h H S A ∈=×i h s S ∈，()i i N s s ∈=，我们定义该组合上局中人i 的效
用函数(R 是实数)。我们用b 来表示逆向归纳策略组合，如果局中人i 在信息集处，那么
:i u S R →i h 对于，就有
()()i i i s h b h ≠()(/())i i h h i u b u b s h i
这里表示策略组合s 在信息集处i 的所获得的支付。表示局中人i 在信息集处用策略代替策略组合s 在该信息集处的策略。 ()i h u s i h /()i i s t h i h ()i i t h 4.2 完美信息扩展型博弈的认知模型
定义4.2.1 一个完美信息扩展型博弈的认知模型是一个四元组,,{},{}i i N i i N M N I σ∈∈=Ω,其中,,{}i i N N I ∈Ω是一个交互知识框架，对每个局中人i ，函数:i S i σΩ→满足性质：
如果()i I ωω′∈，那么()()i i σωσω′=，()i σω是局中人i 在状态ω所选择的策略。 这条性质的直观意思就是局中人i 知道自己的策略。于是，令{:()i i E s }ωσω=∈Ω=，对于所有的，有，我们就说局中人i 是自明的（self-evident ）。
i s S ∈i i E K E ?定义4.2.2 局中人i 在信息集处是理性的，如果在该信息集处，i 并知道不存在有别的策略比他当前所选的策略能给他带来更高的支付。
i h 下面我们通过对局中人理性要求的分析来考察BI 的认知条件，也就是说来考察什么样的理性条件蕴含BI ，首先来看两个不同理性的定义。
定义4.2.3 完美信息扩展型博弈中的局中人是实质理性的（material rationality ）当且仅当该局中人在实际到达的每一个信息集处都是理性的。
定义4.2.4 完美信息扩展型博弈中的局中人是真实理性的（substantive rationality ）当且仅当该局中人在他的所有信息集处都是理性的。
给定策略组合s ，令表示s 的一条路径，结点x （与路径相对应，以后就用结点代替前面的信息集，相应地，符号用x 而不用h ）在状态()p s ω处是可到达的当且仅当
(())x p σω∈。
定义 4.2.5 给定一个认知模型，对每个结点x ，{:(())}x x p ωσω=∈Ω∈表示事件“x 是可到达的”。
令rn i R 表示事件“局中人i 在可到达的点处是理性的”（即实质理性），如果i x X ∈，
()rn i i i i i i x s K x t s R →??∩∩ 于是
((i i i i i
rn i i i x X s S t S ))i i i R x s K x t s ∈∈∈?=→∪∪∪∩∩
而rn rn i N i R R ∈=∩表示所有的局中人都是理性的。
下面我们给出一个模型来说明完美信息扩展型博弈中实质理性的公共知识并不蕴含逆向归纳解（BI ），设{}ωΩ=，12()(){}I I ωωω==，()(,)b de σω=，如图3所示：
2
2
a
b
c
d
e f
x
y z
3 0 1 0 3 0 1 0
1
1：
ω
2：
1的策略： b
2的策略： de
图3 完美信息扩展型博弈及其认知模型
图中的博弈逆向归纳解是ac ，而在上图给出的认知模型中，我们可知*{}rn K R ω=，而博弈解却是be 。由此可知，实质理性的公共知识并不蕴含BI 。另外要说明的是模型中给出的解虽然不是逆向归纳解，但却是纳什均衡解，但我们却不能由此模型得出实质理性的公共知识蕴含纳什均衡解，具体过程这里不再验证。我们下面再看真实理性的公共知识会带来什么。 令i x X ∈是局中人i 的决策点，x i S 表示局中人i 在由点x 开始的子博弈中的策略。设
,x x i i i s t S ∈x 是局中人i 在由点x 开始的子博弈中的两个策略。
x x i i i s t 表示“局中人i 在由点x 开始的子博弈所采取的策略中，策略x i s 要优于策略x i t ”
。 x x i i i s t 在状态ω中为真，如果由点x 开始，相对于()i σω?，局中人i 采取策略x i s 所获得的
支付要高于x i t 。
x x i i i s t 表示x x i i i s t 为真的状态的集合。
如果x x i s S ∈i ，令{:()|x x i i i s s ωσω=∈Ω=}x x ，其中()|i σω表示()i σω限制在由x 点开始的子博弈上。令sr i R 表示“局中人i 是真实理性的”。如果i x X ∈，则
()x x x i i i i i s K t s R ??∩ sr i ，于是(()x x i i i i i
sr x x x i i i i x X s S t S R s K t ∈∈∈?=∪∪∪∩ )i i s
sr i N i sr R R ∈=∩表示“所有局中人都是真实理性的”。我们通过下图的蜈蚣博弈来分析真实理
相应地构造一个认知模型: 123{,,}ωωωΩ=
，11
1121323(),()(){,}I I I ωωωωωω===，
212212233
()(){,},(
)I
I I ωωωωω===ω，
123()(,),()(,),()(,)be d ae d ae c σωσωσω===
如下图所示：
1： 1ω 2ω 3ω
2：
1的策略： be ae ae 2的策略： d d c
图4 蜈蚣博弈2及其认知模型
博弈中可以看出逆向归纳解是（ae,c ）,认知模型中可以验证22{,}rn
R 3ωω=，
23{}sr R ω=3{}sr K R ω?=，于是就有如下两个命题:
命题4.2.1 在每一个完美信息博弈中，sr K R B ??I 。（Aumamm, 1995）
命题4.2.1并不是说理性的局中人在完美信息扩展型博弈中一定会按BI 进行策略选择，而是说如果局中人在某一结点处偏离了BI ，那么在该结点或博弈随后的结点处，我们就不
能得到理性的公共知识。真实理性是一个非常强的概念，它要求局中人在博弈的每个结点处都选择支付最大的策略，如果某个局中人偏离了这一策略，他就不再是理性的了，但其他局中人可能会认为偏离者在以后的博弈中是理性的，如果是这样的话，对于一个理性的局中人来说如何再通过偏离BI来增加自己的收益就很难确定，但在大多数情况下，偏离者更有可能采取另外一个策略，而不是BI，这种假设似乎更合理一些。
我们现在来分析一旦某个局中人偏离了BI，局中人的理性情况以及策略的选择会随之发生什么样的变化。先来看如下图所示的完美信息扩展型博弈及其认知模型。
1：
i
ω
2
ω
3
ω
4
ω
5
ω
2：
1的策略：af bf be bf be
2的策略： c c c d d
图5 蜈蚣博弈3及其认知模型
我们说局中人在某一状态中是真实理性的如果该局中人在此状态中由他采取行动的结
点处是理性的。那么，在状态
1
ω中，局中人2是不是真实理性的呢？在状态
1
ω，局中人2并没有采取任何行动，因为博弈没有进行到结点y处就结束了，但我们说局中人2在此状态中是不理性的，因为如果结点y到达了的话，2计划选择策略c而不是d，显然d能给他带来更大的收益。此时，如果我们把局中人针对其他局中人策略选择的信念考虑进去的话，我们就得到另外一种理性——Stalnaker理性。在定义这一理性之前，先介绍完美信息扩展型博弈认知模型的一个扩张模型。
定义 4.2.6完美信息扩展型博弈认知模型的扩张模型是一个二元组,
M f
Γ=使得M是如定义4.2.1给出的认知模型，函数:f X
Ω×→Ω可定义为(,)
f x
ωω′
=通过结点x且离
ω最近的状态，该函数满足下列性质：
（1）x 在(,)f x ω中是可以到达的，也就是说，x 在由((,))f x σω决定的路径上； （2）如果x 在ω是可以到达的，则(,)f x ωω=；
（3）((,))f x σω与()σω在由结点x 开始的子博弈中是合同的。也就是说局中人在由
ω决定且通过结点x 的行动与离ω最近的状态且也通过结点x 的行动是一样的。
定义4.2.7 局中人i 在状态ω中是Stalnaker 理性的，记为s
R ，当且仅当局中人i 在所有由i 到达的结点x 且离ω最近的状态(,)f x ω处都是理性的。
如图5所示，局中人2在y 结点且离1ω最近的状态2ω（1(,)f x 2ωω=）中是理性的，因为他考虑到局中人1在z 处有可能采取策略e （因为2223(){,}I ωωω=）；同样，局中人1在z 结点且离1ω最近的状态4ω中也是理性的（1(,)f z 4ωω=）。于是在1ω处，局中人有Stalnaker 理性的公共知识，却没有BI 解，但这并不与命题3.2.1相矛盾，因为局中人并没有真实理性的公共知识。相对于真实理性，Stalnaker 理性的局中人更注重于一旦对手策略选择偏离BI ，如何修正自己的信念，而不是对手是否理性的问题。如果我们给函数f 增加一个限制条件：
（4）对于所有的局中人i 和所有结点x ，如果((,))i I f x ωω′∈，那么存在状态
()i I ωω′′∈，使得()σω′和()σω′′在结点x 开始的子博弈中合同。于是我们有如下命题：
命题4.2.3 对于完美信息扩展型博弈的扩张认知模型Γ来说，如果函数f 满足性质（1）—（4），则s K R B ??I 。
我们现在来分析一下局中人的策略，对于局中人1来说，11()|z f σω=（这里的f 是指如图所示的局中人1的行动）是不是意味着“如果结点z 能够到达的话，局中人1选择策略f ”呢？这里应该把局中人1对局中人2采取什么行动的信念也考虑就去，但对于局中人1来说，“给定他当前有关局中人2采取什么行动的信念，如果z 能够到达的话，他将采取策略f ”与“在与当前状态最近且z 能够到达的状态中，他选策略f ”是等价的，函数f 的性质（3）保证了这一点。但对于局中人2来说，就不是这种情况了，他当前有关局中人
1采取何种行动的信念同与当前状态最近且z能够到达的状态中有关局中人1的信念是不一样的，但最后增加的性质（4）保证了它们是相同的，从而有了命题4.2.3。
参考文献：
Andres, Perea, (2007). Epistemic Foundation for Game Theory: An overview
Http://www.personeel.unimaas.nl/a.perea/
Aumann, R. J. (1976). Agreeing to disagree. Annals of Statistics 4(6), 1236-1239
Aumann, R. J. (1995). Backwards induction and common knowledge of rationality. Games and Economic Behavior 8, 6-19.
Battigalli, Pierpaolo and Bonanno Giacomo. (1999) Recent results on belief, knowledge and the epistemic foundations of game theory. Research in Economics.
Bonanno Giacomo. (2000) Information, Knowledge and Belief
Gabby, D and Guenthner, F. (2003) Handbook of Philosophical Logic. V olume 10,1-38 Halpern. J. (2001). Substantive Rationality and Backward Induction. Games and Economic Behavior 37: 425-435
Martin J. Osborne, Ariel Rubinstein. (1994). A Course in Game Theory. Massachusetts Institute of Technology
Stalnaker, R.(1996). Knowledge and Games with Perfect Information. Game and Economic Behavior 7:230-251
高一数学归纳法分析及解题步骤 当我第一遍读一本好书的时候，我仿佛觉得找到了一个朋友;当我再一次读这本书的时候，仿佛又和老朋友重逢。我们要把读书当作一种乐趣，并自觉把读书和学习结合起来，做到博览、精思、熟读，更好地指导自己的学习，让自己不断成长。让我们一起到一起学习吧! 高一数学归纳法 《2.3数学归纳法》教学设计 青海湟川中学刘岩 一、【教材分析】 本节课选自《普通高中课程标准实验教科书数学选修2-2(人教A 版)》第二章第三节《2.3数学归纳法》。在之前的学习中，我们已经用不完全归纳法得出了许多结论，例如某些数列的通项公式，但它们的正确性还有待证明。因此，数学归纳法的学习是在合情推理的基础上，对归纳出来的与正整数有关的命题进行科学的证明，它将一个无穷的归纳过程转化为有限步骤的演绎过程。通过把猜想和证明结合起来，让学生认识数学的本质，把握数学的思维。本节课是数学归纳法的第一课时，主要让学生了解数学归纳法的原理，并能够用数学归纳法解决一些简单的与正整数有关的问题。 二、【学情分析】 我校的学生基础较好，思维活跃。学生在学习本节课新知的过程中可能存在两方面的困难：一是从骨牌游戏原理启发得到数学方法的
过程有困难;二是解题中如何正确使用数学归纳法，尤其是第二步中如何使用递推关系，可能出现问题。 三、【策略分析】 本节课中教师引导学生形成积极主动，勇于探究的学习精神，以及合作探究的学习方式;注重提高学生的数学思维能力;体验从实际生活理论实际应用的过程;采用教师引导学生探索相结合的教学方法，在教与学的和谐统一中，体现数学的价值，注重信息技术与数学课程的合理整合。 四、【教学目标】 (1)知识与技能目标： ①理解数学归纳法的原理与实质，掌握数学归纳法证题的两个步骤; ②会用数学归纳法证明某些简单的与正整数有关的命题。 (2)过程与方法目标： 努力创设愉悦的课堂气氛，使学生处于积极思考，大胆质疑的氛围中，提高学生学习兴趣和课堂效率，让学生经历知识的构建过程，体会归纳递推的数学思想。 (3)情感态度与价值观目标： 通过本节课的教学，使学生领悟数学归纳法的思想，由生活实例，激发学生学习的热情，提高学生学习的兴趣，培养学生大胆猜想，小心求证，以及发现问题、提出问题，解决问题的数学能力。 五、【教学重难点】
归纳法基本步骤 （一）第一数学归纳法： 一般地，证明一个与自然数n有关的命题P(n)，有如下步骤： （1）证明当n取第一个值n0时命题成立。n0对于一般数列取值为0或1，但也有特殊情况； （2）假设当n=k（k≥n0，k为自然数）时命题成立，证明当n=k+1时命题也成立。 综合（1）（2），对一切自然数n（≥n0），命题P(n)都成立。 （二）第二数学归纳法： 对于某个与自然数有关的命题P(n)， （1）验证n=n0时P(n)成立； （2）假设n0≤n
交通大学博弈论课程概要 (I) 周林 二零零四年十二月 主要教材：博弈论（Fudenberg & Tirole ） 引言： 博弈论与决策论的差别. 例子：田忌赛马，换钱. 第一部分：完全信息策略式博弈 — 静态博弈 1. 策略式博弈的基本三要素：博弈者，策略空间，收益函数 2. 策略式博弈的基本三解法： a. 占优策略. 例子: 囚徒困境，二价拍卖（Ebay ， 易趣网） b. 重复剔除劣策略. 例子：双寡头Cournot 竞争（线性需求） c. Nash 均衡 (最重要的概念) 三种解法的合理性依次减低，而三种解法的适用范围(存在性)依次增加. 3. Nash 均衡存在性定理：如果策略空间是凸紧集，收益函数连续和自拟凹，至少存在一个Nash 均衡. 证明基本思路：最佳反应映射是从策略空间到策略空间的(上半)连续映 射(Berge 定理), 最佳反应映射的不动点就是Nash 均衡. 利用(Kakutani 不动点定理)Brouwer 不动点定理找出不动 点.（注意：这里的最佳反应映射不是一个压缩映射, 因 此不能用迭代法逼近不动点.） 推论：任何有限策略博弈至少有一个混合策略Nash 均衡. 4. Nash 均衡一般非唯一，非Pareto 最优. 可以通过外在信号机制改善收益. 相关均衡：公共信号仅将不同的Nash 均衡混合，私人信号更为有效. 作业：1.1，1.2, 1.5, 1.7, 1.10, 1.12, 2.2 （F&T ）. 以及下面的题目： A ． 证明任何一个满足Nash 均衡存在性定理的对称博弈(首先给出一个合 理的定义)一定存在一个对称的Nash 均衡. B ． 画出下列博弈中所有的相关均衡生成的收益向量: 博弈者 2 博弈者 1 T W
§数学归纳法 1．数学归纳法的概念及基本步骤 数学归纳法是用来证明某些与正整数n有关的数学命题的一种方法．它的基本步骤是： (1)验证：n＝n0 时，命题成立； (2)在假设当n＝k(k≥n0)时命题成立的前提下，推出当n＝k＋1时，命题成立． 根据(1)(2)可以断定命题对一切正整数n都成立． 2．归纳推理与数学归纳法的关系 数学上，在归纳出结论后，还需给出严格证明．在学习和使用数学归纳法时， 需要特别注意： (1)用数学归纳法证明的对象是与正整数n有关的命题； (2)在用数学归纳法证明中，两个基本步骤缺一不可． 1．用数学归纳法证明命题的第一步时，是验证使命题成立的最小正整数n，注意n不一定是1. 2．当证明从k到k＋1时，所证明的式子不一定只增加一项；其次，在证明命题对n＝k＋1成立时，必须运用命题对n＝k成立的归纳假设．步骤二中，在 由k到k＋1的递推过程中，突出两个“凑”：一“凑”假设，二“凑”结论．关键是明确n＝k＋1时证明的目标，充分考虑由n＝k到n＝k＋1时命题 形式之间的区别与联系，若实在凑不出结论，特别是不等式的证明，还可以应用比较法、分析法、综合法、放缩法等来证明当n＝k＋1时命题也成立，这也是证题的常用方法． 3．用数学归纳法证命题的两个步骤相辅相成，缺一不可．尽管部分与正整数 有关的命题用其他方法也可以解决，但题目若要求用数学归纳法证明，则必须 依题目的要求严格按照数学归纳法的步骤进行，否则不正确． 4．要注意“观察——归纳——猜想——证明”的思维模式，和由特殊到一般的数学思想的应用，加强合情推理与演绎推理相结合的数学应用能力．
5．数学归纳法与归纳推理不同．(1)归纳推理是根据一类事物中部分事物具有某种属性，推断该类事物中每一个都有这种属性．结果不一定正确，需要进行严格的证明．(2)数学归纳法是一种证明数学命题的方法，结果一定正确． 6．在学习和使用数学归纳法时，需要特别注意： (1)用数学归纳法证明的对象是与正整数n 有关的命题，要求这个命题对所有的正整数n 都成立； (2)在用数学归纳法证明中，两个基本步骤缺一不可． 数学归纳法是推理逻辑，它的第一步称为奠基步骤，是论证的基础保证，即通过验证落实传递的起点，这个基础必须真实可靠；它的第二步称为递推步骤，是命题具有后继传递的保证，即只要命题对某个正整数成立，就能保证该命题对后继正整数都成立，两步合在一起为完全归纳步骤，称为数学归纳法，这两步各司其职，缺一不可．特别指出的是，第二步不是判断命题的真伪，而是证明命题是否具有传递性．如果没有第一步，而仅有第二步成立，命题也可能是假命题． 证明：12＋122＋123＋…＋12 n －1＋12n ＝1－1 2n (其中n ∈N ＋)． [证明] (1)当n ＝1时，左边＝12，右边＝1－12＝1 2，等式成立． (2)假设当n ＝k (k ≥1)时，等式成立，即 12＋122＋123＋…＋12k －1＋12k ＝1－12k ， 那么当n ＝k ＋1时， 左边＝12＋122＋123＋…＋12k －1＋12k ＋1 2k ＋1 ＝1－12k ＋12k ＋1＝1－2－12k ＋1＝1－1 2k ＋1＝右边． 这就是说，当n ＝k ＋1时，等式也成立． 根据(1)和(2)，可知等式对任何n ∈N ＋都成立． 用数学归纳法证明：1－12＋13－14＋…＋12n －1－ 1 2n
数学归纳法经典练习及 解答过程 文稿归稿存档编号：[KKUY-KKIO69-OTM243-OLUI129-G00I-FDQS58-
第七节数学归纳法 知识点数学归纳法 证明一个与正整数n有关的命题，可按下列步骤进行： (1)(归纳奠基)证明当n取第一个值n0(n0∈N*)时命题成立． (2)(归纳递推)假设n＝k(k≥n0，k∈N*)时命题成立，证明当n＝k＋1时命题也成立． 只要完成这两个步骤，就可以断定命题对从n0开始的所有正整数n都成立．易误提醒运用数学归纳法应注意： (1)第一步验证n＝n0时，n0不一定为1，要根据题目要求选择合适的起始值． (2)由n＝k时命题成立，证明n＝k＋1时命题成立的过程中，一定要用到归纳假设，否则就不是数学归纳法． [自测练习] 1．已知f(n)＝1 n ＋ 1 n＋1 ＋ 1 n＋2 ＋…＋ 1 n2 ，则( ) A．f(n)中共有n项，当n＝2时，f(2)＝1 2 ＋ 1 3 B．f(n)中共有n＋1项，当n＝2时，f(2)＝1 2 ＋ 1 3 ＋ 1 4 C．f(n)中共有n2－n项，当n＝2时，f(2)＝1 2 ＋ 1 3 D．f(n)中共有n2－n＋1项，当n＝2时，f(2)＝1 2 ＋ 1 3 ＋ 1 4 解析：从n到n2共有n2－n＋1个数，所以f(n)中共有n2－n＋1项，且f(2)＝1 2 ＋ 1 3 ＋ 1 4 ，故选D. 答案：D
2．(2016·黄山质检)已知n 为正偶数，用数学归纳法证明1－12＋13－14＋…＋1 n ＋1 ＝ 2? ???? 1n ＋2＋1n ＋4 ＋…＋12n 时，若已假设n ＝k (k ≥2为偶数)时命题为真，则还需要用归纳假设再证n ＝( )时等式成立( ) A ．k ＋1 B ．k ＋2 C ．2k ＋2 D ．2(k ＋2) 解析：根据数学归纳法的步骤可知，则n ＝k (k ≥2为偶数)下一个偶数为k ＋2，故选B. 答案：B 考点一 用数学归纳法证明等式| 求证：(n ＋1)(n ＋2)·…·(n ＋n )＝2n ·1·3·5·…·(2n －1)(n ∈N *)． [证明] (1)当n ＝1时，等式左边＝2，右边＝21·1＝2，∴等式成立． (2)假设当n ＝k (k ∈N *)时，等式成立，即(k ＋1)(k ＋2)·…·(k ＋k )＝2k ·1·3·5·…·(2k －1)． 当n ＝k ＋1时，左边＝(k ＋2)(k ＋3)·…·2k ·(2k ＋1)(2k ＋2) ＝2·(k ＋1)(k ＋2)(k ＋3)·…·(k ＋k )·(2k ＋1) ＝2·2k ·1·3·5·…·(2k －1)·(2k ＋1) ＝2k ＋1·1·3·5·…·(2k －1)(2k ＋1)． 这就是说当n ＝k ＋1时，等式成立． 根据(1)，(2)知，对n ∈N *，原等式成立． 1．用数学归纳法证明下面的等式： 12－22＋32－42＋…＋(－1)n －1·n 2＝(－1)n －1n ?n ＋1? 2 . 证明：(1)当n ＝1时，左边＝12＝1， 右边＝(－1)0 ·1×?1＋1? 2 ＝1， ∴原等式成立． (2)假设n ＝k (k ∈N *，k ≥1)时，等式成立，
逆向归纳法的认知基础 崔晓红 1.引言 逆向归纳法是博弈论中一个比较古老的概念，它的提出最早可以追溯到泽梅罗（1913）针对国际象棋有最优策略解的证明，后来人们将其推广到了更广泛的博弈中，例如，在有限完美信息扩展型博弈中，就是用逆向归纳法（BI）来证明子博弈完美均衡（SPE）的存在以及求解SPE，其基本思路是从动态博弈中的最后一个阶段开始，局中人都遵循效用最大化原则选择行动，然后逐步倒推至前一个阶段，一直到博弈开始局中人的行动选择，其逻辑严密性毋庸置疑。然而，当从终点往前推到某一决策点时，BI完全忽略了到达该决策点的以往历史行动，而这一历史行动当然会影响处于该决策点的局中人有关其对手将来如何采取行动的信念，例如，一个局中人如果观察到对手在过去没有按照BI进行行动选择，那么他就有理由相信他的对手仍会采取同样的模式进行下去，但是通过这种信念修正以后所做的选择就会与BI矛盾。为了达到均衡解，为了能按BI进行推理求解，我们需要对局中人的信念或者说知识增加一些限制性条件，也就是说在什么样的前提下，BI是合理的，显然，仅仅要求每个局中人都理性是不够的，所有的局中人都必须知道所有的局中人都是理性的，所有的局中人都必须知道所有局中人都知道所有局中人都是理性的……等等以至无穷，在这样的认知条件基础下，我们就不会偏离BI，即，“在完美信息扩展型博弈中，理性的公共知识蕴含了BI”（Aumann 1995）。本文旨在通过构造完美信息扩展型博弈的认知模型来考察BI的这一认知条件。文章第二部分先通过一些简单例子对一些问题进行非形式上的讨论；第三部分介绍Aumann结构如何表达知识和信念；第四部分给出完美信息扩展型博弈的认知模型并用形式化的方给出BI的认知条件。 2. 实例分析 2.1 蜈蚣博弈 图1是一个长度为3的蜈蚣博弈，博弈每前进一个阶段，桌子上就增加一美元，局中人1，2轮流采取行动，轮到某个局中人采取行动时，他可以拿走桌子上的钱，博弈结束，或者钱留在桌子上继续博弈，另外，局中人都是理性的，也就是说都遵循期望效用最大化原
交通运输学院硕士研究生入学考试自命题科目考试范围 一、806电子商务系统分析与设计 1. 了解关于电子商务的三种理解；理解信息系统、电子商务系统与互联网产品之间的关系；理解信息系统的组成； 2. 理解软件的特点及软件危机的主要表现；了解软件工程的基本原则；掌握瀑布模型、SDLC、RUP、RAD等过程模型；理解敏捷方法及极限编程；了解互联网产品研发过程。 3. 了解电子商务系统建设项目管理的目标及主要工作内容；掌握项目计划的方法及主要工具；了解项目执行过程中的变更管理及配置管理。 4. 理解电子商务系统规划的主要内容；理解明确市场定位、估计市场规模的基本方法及竞品分析的目的与内容；理解进行产品（服务）设计的基本原则与方法；理解MECE法则并掌握思维导图的绘制方法；理解电子商务生态圈的构成。 5. 理解传统信息系统分析的目的、内容、方法、成果；理解需求的分类及其内涵；理解需求分析的内容、过程、成果及原则。 6. 理解系统分析设计的两种思路及其可视化建模；了解UML的组成；理解用例的概念，掌握用例间的关系；理解类、对象的概念，掌握类之间的关系；掌握用例图、状态图、活动图、交互图、类图的绘制，了解包图、构件图与部署图；了解基于UML的分析设计过程。 7. 了解系统设计的内容；理解架构设计的成果形式；理解常见的软件系统架构；掌握电子商务系统的性能指标；掌握提高响应能力、可用性、可伸缩性、可扩展性的主要架构设计技术；了解数据库设计的内容及基本原则；理解面向品牌建设的门户设计要点；理解云计算的基本概念；理解Cookie在互联网广告业务中的应用原理及主要方式。8. 了解电子商务系统实现阶段的主要任务；理解系统测试的基本评价指标及分类；理解电子商务系统切换的主要方式；了解电子商务系统维护的主要内容；理解应用软件维护的分类。 二、871运筹学理论与方法 1.线性规划。掌握和理解线性规划问题特点和基本模型、单纯形法、改进单纯形法、对偶问题、线性规划的对偶理论、影子价格的含义、对偶单纯形法、灵敏度分析的主要内容和计算。 2.运输问题。掌握运输问题的数学模型及表上作业法，熟悉产销不平衡运输问题及求解方法。 3.整数规划。重点掌握整数规划问题求解的分枝定界法、0-1整数规划的表示及指派问题的求解方法，理解并掌握割平面法。 4.动态规划。理解动态规划的基本概念和基本方程，掌握典型动态规划应用如资源分配问题与生产与存贮问题。 5.图与网络分析。理解并掌握图的基本概念、最短路问题、网络最大流问题、最小费用最大流问题。 6.排队论。理解并掌握排队论的基本概念、到达时间和服务时间分布、单服务与多服务台负指数分布排队系统、一般服务时间M/G/1模型。 三、942管理运筹学 1.线性规划 （1）线性规划模型的特点； （2）线性规划标准型； （3）线性规划的可行解、基、基解、基可行解、可行解、最优解； （4）线性规划解的四种情况； （5）线性规划的基本定理； （6）单纯形表的结构；检验数的概念和计算；最优性判断； （7）影子价格；对偶问题；对偶定理； （8）对偶单纯形法的基本原理； （9）灵敏度分析； 2.运输问题 （1）产销平衡的表上作业法 初始解的求解方法：最小元素法、差值法； 解的最优性判断：闭回路法、位势法； 解的改善：换入变量的确定、换出变量的确定、调整量的确定、解的调整；
“数学归纳法”教学设计 一、教材与内容解析 （一）内容与内容解析 数学归纳法是人教B版普通高级中学教科书数学选修2-2第二章第三节的内容。本节课的主要内容是介绍数学归纳法的原理。 由于正整数具有无穷无尽的特点，有些关于正整数n的命题,难以对n进行一一的验证，从而需要寻求一种新的推理方法，以便能通过有限的推理来证明无限的结论，这是数学归纳法产生的根源。 数学归纳法是一种证明与正整数n有关命题的重要方法。它的独到之处便是运用有限个步骤就能证明无限多个对象，而实现这一目的的工具就是递推思想。 数学归纳法的两个步骤中，第一步是证明的奠基，第二步是递推。递推是实现从有限到无限飞跃的关键，没有它我们就只能停留在对有限情况的把握上。 数学归纳法是以归纳为基础、以演绎为手段证明结论的一种方法，是归纳法与演绎法的完善结合．这也许是数学归纳法不是归纳法但又叫“数学归纳法”的原因． （二）地位与作用解析 从应用上看，数学归纳法是解决与正整数有关命题的一种推理方法，它将无限多个归纳过程转化为一个有限步骤的演绎过程，是证明与正整数有关问题的重要工具。数学归纳法本质是归纳递推，但它与归纳法有着一定程度的关联。在数学结论的发现过程中，不完全归纳法发现结论，最终利用数学归纳法证明解决问题。 从思想方法上看，数学归纳法蕴含了无限转化为有限的思想，体现了奠基、递推、总结一体的整体思想。 从美学上看，数学归纳法展现了无限与有限的统一美；揭示了有限推证无限，把无限“沦为”有限的思维美；数学归纳法的发展历程展现了数学文化美。 二、教学问题诊断 1．学生已有的经验和基础：(1)学生已有数学归纳法的萌芽和相关经验．虽然学生没有正式学过数学归纳法，但小学的数数、找一列数的规律、高中等差数列和等比数列通项公式的推导过程等等，都蕴含着数学归纳法的萌芽和基础．(2)学生已经有用具有代表性的元素来代替任意的、无穷多的元素的经验．如在线面垂直的定义和证明中，用“平面内
第四章 完全信息动态博弈的基本理论 一．回顾如何用标准型表述、刻画博弈？回顾如何用扩展型表述、刻画博弈？ 二．信息集 1.观察下列两个扩展型博弈在结构上有什么区别？ 2.参与人i 的信息集是指由这样一些决策节点组成的集合，第一，i 的信息集中每个节点都是i 的决策节点，即如果博弈进行到这一步，轮到i 行动；第二，当博弈到达i 的某个信息集，参与人i 并不知道自己究竟已经到了信息集中的哪个节点。 3.对信息集的进一步理解 A 信息集用于表示博弈参与人在轮到他行动时所掌握的信息。 B 信息集定义的第二点意味着在同一个信息集的节点有着相同的可行的行动集（思考：为什么？）。 C 同一个信息集的节点不能相互构成前续节点与后续节点的关系。 4.思考：画出下列博弈的博弈树或扩展型表示。 第一步，参与人甲从行动集（L ，R ）中进行选择；第二步，参与人乙观察到参与人甲的行动选择后从自己的行动集（M ，N ）中进行选择；最后一步，参与人甲只能观察到过去的选择是否是（R ，N ），并从行动集（V ，W ）中进行选择。 5.完全完美信息（complete and perfect ）博弈与完全不完美信息(complete and imperfect)博弈 （1）完全信息与不完全信息：区分完全信息与否的标准就看每个博弈参与人的支付函数是否是博弈的公共知识。 （2）完美信息与不完美信息：区分完美信息与否的标准就看该博弈的每个信息集是否都是单点的（singleton ）。完美信息意味着该博弈的每个信息集都是单点集。思考：完美信息博弈意味着博弈参与人对所参与的博弈究竟知道些什么？意味着在博弈的每个行动时刻轮到行动的参与人知道博弈迄今为止的全部历史。 夫 夫
一个逆向归纳法的经典例子，其原型来自I.Stewart在《科学美国人》杂志上的一篇文章《凶残海盗的逻辑》。这个例子曾经被微软公司作为招募员工的面试题目。 话说有五个海盗抢来了100枚金币，大家决定分赃的方式是：由海盗1提出一种分配方案，如果同意这种方案的人数达到半数，那么该提议就通过并付诸实践；若同意这种方案的人数未达半数，则提议不能通过且提议人将被扔进大海喂鲨鱼，然后由接下来的海盗继续重复提议过程。假设每个海盗都聪明绝顶，也不互相合作，并且每个海盗都想尽可能多的得到金币，那么，第一个提议的海盗将怎样提议既可以使得提议被通过又可以最大限度得到金币呢？ 使用逆向归纳法可以求解如下： ●首先，考虑只剩下最后的海盗5，显然他会分给自己100枚，并且赞成自己●再回到只剩下海盗4和海盗5的决策，海盗4可以分给自己100枚并赞成自 己；海盗5被分得0枚，即使反对也无用。 ●回到海盗3，海盗3可以分给海盗5一枚得到海盗5的同意；分给自己99 枚，自己也同意；分给海盗4零枚，海盗4反对但无用。 ●回到海盗2，海盗2可以分给海盗4一枚得到海盗4的同意；分给自己99 枚，自己也同意；海盗3,5分得0枚，他们会反对但反对没有用。 ●回到海盗1，他可以分给海盗3,5各一枚，获得海盗3,5的同意；分给自己 98，自己也同意；分给海盗2,4各零枚，他们会反对但反对没有作用。 因此，这个海盗分赃的问题答案是（98，0，1，0，1）：海盗1提出分给自己98枚，分给海盗2,4各零枚，分给海盗3,5各一枚，该提议会被通过。因为海盗1,3,5会投赞成票。 对于上述海盗分赃问题，我们还可以演化出不同的版本。比如说：（1）如果要求包括提议海盗在内的所有海盗过半数（超过1/2）同意才能使提议通过，那么海盗1应该怎么提方案？(2)如果要求提议海盗之外的海盗过半数同意才能通过，那么海盗1又该怎样提出方案？（3）或者海盗的数目增加到10个，100个，海盗1又怎么提方案？ 答案：变种问题（1）中，海盗1提出的分配方案是（97，0，1，2，0）或（97，0，1，0，2）；变种问题(2)中，海盗1提出的方案应是（97，0，1，1，1）；变种问题（3）中，奇数号海盗各得一枚，偶数号海盗不得金币。 这学期选修的益智数学，颇觉有意思。一向知道数学是一门严谨严格的学科，这特点本已让数学充满了神奇，而这神奇而演绎出来的灵活与实用，也为数学带来了足具艺术的气质。不得不让人为数学折服，为数学无怨无悔，尽情尽意奉献一生。 海盗分赃这类问题虽说简单，却也能锻炼人的逆向思维能力，思维的灵活程度一般说来也是可以锻炼强化的。通过诸多数学游戏，也慢慢能够熟悉一些数学模型，而思维的模型化能够让人更加快捷的熟悉并掌握新的事物，也能为探索未知的模型奠定一定的思维技巧。
教材背景： 归纳是一种由特殊事例导出一般规律的思维方法．归纳推理分完全归纳推理与不完全归纳推理两种．不完全归纳推理只根据一类事物中的部分对象具有的共同性质，推断该类事物全体都具有的性质，这种推理方法，在数学推理论证中是不允许的．完全归纳推理是在考察了一类事物的全部对象后归纳得出结论来．数学归纳法是用来证明某些与正整数n有关的数学命题的一种推理方法，在数学问题的解决中有着广泛的应用． 教学课题：数学归纳法 教材分析： “数学归纳法”既是高中代数中的一个重点和难点容，也是一种重要的数学方法。它贯通了高中代数的几大知识点：不等式，数列，三角函数……在教学过程中，教师应着力解决的容是：使学生理解数学归纳法的实质，掌握数学归纳法的证题步骤（特别要注意递推步骤中归纳假设的运用和恒等变换的运用）。只有真正了解了数学归纳法的实质，掌握了证题步骤，学生才能信之不疑，才能用它灵活证明相关问题。本节课是数学归纳法的第一节课，有两大难点：使学生理解数学归纳法证题的有效性；递推步骤中归纳假设的利用。不突破以上难点，学生往往会怀疑数学归纳法的可靠性，或者只是形式上的模仿而不知其所以然。这会对以后的学习造成极大的阻碍。根据本节课的教学容和学生实际水平，本节课采用“引导发现法”和“讲练结合法”。通过课件的动画模拟展示，引发和开启学生的探究热情，通过“师生”和“生生”的交流合作，掌握概念的深层实质。 教学目标 1、知识和技能目标 (1)了解数学推理的常用方法（归纳法） (2)了解数学归纳法的原理及使用围。 (3)初步掌握数学归纳法证题的两个步骤和一个结论。 (4)会用数学归纳法证明一些简单的等式问题。 2、过程与方法目标 通过对归纳法的复习，说明不完全归纳法的弊端，通过多米诺骨牌实验引出数学归纳法的原理，使学生理解理论与实际的辨证关系。在学习中培养学生探索发现问题、提出问题的意识，解决问题和数学交流的能力,学会用总结、归纳、演绎类比探求新知识。
博弈论基础作业 一、名词解释 纳什均衡占优战略均衡纯战略混合战略子博弈精炼纳什均衡 贝叶斯纳什均衡精炼贝叶斯纳什均衡共同知识 见PPT 二、问答题 1.举出囚徒困境和智猪博弈的现实例子并进行分析。 囚徒困境的例子：军备竞赛；中小学生减负；几个大企业之间的争相杀价等等； 以中小学生减负为例：在当前的高考制度下，给定其他学校对学生进行减负，一个学校最好不减负，因为这样做，可以带来比其他学校更高的升学率。给定其他学校不减负，这个学校的最佳应对也是不减负。否则自己的升学率就比其他学校低。因此，不论其他学校如何选择，这个学校的最佳选择都是不减负。每个学校都这样想，所以每个学校的最佳选择都是不减负，因此学生的负担越来越重。 请用同样的方法分析其他例子。 智猪博弈的例子：大企业开发新产品；小企业模仿；股市中，大户搜集分析信息，散户跟随大户的操作策略 以股市为例：给定散户搜集资料进行分析，大户的最佳选择是跟随。而给定散户跟随，大户的最佳选择是自己搜集资料进行分析。但是不论大户是选择分析还是跟随，散户的最佳选择都是跟随。因此如果大户和散户是聪明的，并且大户知道散户也是聪明的，那么大户就会预见到散户会跟随，而给定散户跟随，大户只有自己分析。 请用同样的方法分析其他例子。 2.请用博弈论来说明“破釜沉舟”和“穷寇勿追”的道理。 破釜沉舟是一个承诺行动。目的是要断绝自己的退路，让自己无路可退，让自己决一死战变得可以置信。也就是说与敌人对决时，只有决一死战，这样才可以取得胜利。否则，如果不破釜沉舟，那么遇到困难时，就很有可能退却，也就无法取得胜利。穷寇勿追就是要给对方一个退路，由于有退路，对方就不会殊死抵抗。否则，对方退无可退，只有坚决抵抗一条路，因而必然决一死战。自己也会付出更大的代价。 3.当求职者向企业声明自己能力强时，企业未必相信。但如果求职者拿出自己的各种获奖证书时，却能在一定程度上传递自己能力强的信息。这是为什么？ 由于口头声明几乎没有成本，因此即便是能力差的求职者也会向企业声明自己能力强。当然能力强的人也会声明自己的能力强。也就是说不同类型的求职者为了赢得职位
数学归纳法 2015高考会这样考 1.考查数学归纳法的原理和证题步骤；2.用数学归纳法证明与等式、不等式或数列有关的命题，考查分析问题、解决问题的能力． 复习备考要这样做 1.理解数学归纳法的归纳递推思想及其在证题中的应用；2.规范书写数学归纳法的证题步骤． 一、知识梳理 数学归纳法 一般地，证明一个与正整数n 有关的命题，可按下列步骤进行： (1)(归纳奠基)证明当n 取第一个值n 0 (n 0∈N *)时命题成立； (2)(归纳递推)假设n ＝k (k ≥n 0，k ∈N *)时命题成立，证明当n ＝k ＋1时命题也成立． 只要完成这两个步骤，就可以断定命题对从n 0开始的所有正整数n 都成立．上述证明方法叫作数学归纳法． [难点正本 疑点清源] 1．数学归纳法是一种重要的数学思想方法，主要用于解决与正整数有关的数学问题．证明时步骤(1)和(2)缺一不可，步骤(1)是步骤(2)的基础，步骤(2)是递推的依据． 2．在用数学归纳法证明时，第(1)步验算n ＝n 0的n 0不一定为1，而是根据题目要求，选择合适的起始值．第(2)步，证明n ＝k ＋1时命题也成立的过程，一定要用到归纳假设，否则就不是数学归纳法． 小试牛刀 1．凸k 边形内角和为f (k )，则凸k ＋1边形的内角和为f (k ＋1)＝f (k )＋________. 答案 π 解析 易得f (k ＋1)＝f (k )＋π. 2．用数学归纳法证明：“1＋12＋13＋…＋1 2n －1
目录 摘要 (2) 一、完全信息静态博弈 (2) 1、背景 (2) 2、博弈的假设与建模 (2) 3、结合案例博弈分析 (3) 4、结论与思考 (4) 5、建议 (4) 6、小结 (5) 二、完全信息动态博弈 (5) 1、背景 (5) 2、模型的建立与假设 (6) 3、分析过程 (7) 4、结论 (8) 5、建议 (8) 6、小结 (9)
完全信息问题的博弈分析 摘要： 通过用博弈分析方法对日常生活中具有现实意义的社会现象和人力资源管理专业问题分析事件发生的本质，从而在各种复杂因素的影响下，找到利益最大化的均衡策略，不仅可以预测参与人的策略选择，更重要是提高自身决策水平和决策质量，实际即是博弈论在现实的运用。本文选取两个案例作为完全信息静态和动态分析的背景。 关键词：博弈论、现实运用、社会现象、招聘 一、完全信息静态博弈 完全信息：每个参与人对其他所有参与人的战略选择和支付收益完全了解。 静态博弈：所有参与人在共同决策环境中同时选择行动策略，每个参与人只选择一次。 纳什均衡：在给定的其他参与人选择的前提下，参与人根据自身收益选择的最优战略。 1、背景： “除非有人证物证，否则我不会再去扶跌倒的老人！”广东肇庆的阿华在扶起倒地的70多岁阿婆却遭诬陷后表示。事发7月15日早上，阿华开摩托车上行人道准备买早餐,看到路边有位老太太跌倒在求救，阿华立刻停下来，扶起老奶奶，殊不知却遭到阿婆的诬陷，随后和阿婆的女婿发生争执。阿婆被送到医院住院观察。为调查真相，交警暂扣了阿华的摩托车。事发后几天，阿华说没睡过一次好觉，还向单位请了几天假，天天在附近找证人，就是为了证实自己清白。 这起社会事件引发了我们的深思：阿婆在路边跌倒，路人是否应该扶起？在这个过程中，跌倒的阿婆是否讹钱与是否采取帮忙的路人构成博弈问题，以下通过完全信息静态博弈模型分析，解析这一社会现象。 2、博弈的假设与建模： 假设：参与博弈的双方是理性人，都会选择个人利益最大化的行动。
备课 时间 教学 课题 教时 计划 1 教学 课时 1 教学 目标 1．了解归纳法的意义，培养学生观察、归纳、发现的能力． 2．了解数学归纳法的原理，能以递推思想作指导，理解数学归纳法的操作步骤． 3．抽象思维和概括能力进一步得到提高． 重点难点 重点：借助具体实例了解数学归纳的基本思想，掌握它的基本步骤，运用它证明一 些与正整数n （n 取无限多个值）有关的数学命题。 难点：1、学生不易理解数学归纳的思想实质，具体表现在不了解第二个步骤的作 用，不易根据归纳假设作出证明； 2、运用数学归纳法时，在“归纳递推”的步骤中发现具体问题的递推关系。 教学过程 （一）创设情景 对于数列{an}，已知11=a ， a a a n n n +=+11(n=1,2,…), 通过对n=1,2,3,4前4项的归纳，猜想其通项公式为n a n 1= 。这个猜想是否正确需要证明。 一般来说，与正整数n 有关的命题，当n 比较小时可以逐个验证，但当n 较大时，验证就很麻烦。特别是n 可取所有正整数时逐一验证是不可能的。因此，我们需要寻求一种方法：通过有限个步骤的推理，证明n 取所有正整数都成立。 （二）研探新知 1、了解多米诺骨牌游戏。 可以看出，只要满足以下两条件，所有多米诺骨牌就都能倒下： （1）第一块骨牌倒下； （2）任意相邻的两块骨牌，前一块倒下一定导致后一块倒下。 思考：你认为条件（2）的作用是什么？ 可以看出，条件（2）事实上给出了一个递推关系： 当第k 块倒下时，相邻的第k+1块也倒下。 这样，要使所有的骨牌全部倒下，只要保证（1）（2）成立。 2、用多米诺骨牌原理解决数学问题。 思考：你认为证明数列的通过公式是n a n 1= 这个猜想与上述多米诺骨牌游戏有相似性吗？你能 类比多米诺骨牌游戏解决这个问题吗？ 分析： 多米诺骨牌游戏原理 通项公式 n a n 1= 的证明方法 （1）第一块骨牌倒下。 （1）当n=1时a1=1，猜想成立 （2）若第k 块倒下时，则相邻的第k+1块也倒下。 （2）若当n=k 时猜想成立，即 k a k 1= ，则当n=k+1时猜想也成立，即 111+=+k a k 。
学习-----好资料 第十章 博弈论初步 第一部分 教材配套习题本习题详解 一、简答题 １．什么是纳什均衡？纳什均衡一定是最优的吗？ 解答：（１）所谓纳什均衡，是参与人的一种策略组合，在该策略组合上， 任何参与人单独改变策略都不会得到好处。 （２）不一定。如果纳什均衡存在，纳什均衡可能是最优的，也可能不是最优的。例如，在存在多个纳什均衡的情况下，其中有一些纳什均衡就不是 最优的；即使在纳什均衡是唯一时，它也可能不是最优的，因为与它相对应的支付组合可能会小于与其他策略组合相对应的支付组合。如：囚徒 困境。 ２．在只有两个参与人且每个参与人都只有两个策略可供选择的情况下， 纯策略的纳什均衡最多可有几个？为什么？ 解答：在只有两个参与人 （如 Ａ和 Ｂ）且每个参与人都只有两个策略可供选择的情况下，纯策略的纳什均衡最多可有四个。例如，当Ａ与Ｂ的支付矩阵可分别表示如下时，总的支付矩阵中所有四个单元格的两个数字均有下划线，从而，总共有四个纳什均衡。 A 的支付矩阵＝??????22211211a a a a B 的支付矩阵＝??? ???2221 1211b b b b 例如：a 11=a 12=a 21=a 22，b 11=b 12=b 21=b 22就会得到以上四个纳什均衡。 具体事例为： 73737373?? ????
３．在只有两个参与人且每个参与人都只有两个策略可供选择的情况下，纯策略的纳什均衡可能有三个。试举一例说明。 解答：在只有两个参与人且每个参与人都只有两个策略可供选择的情况下，纯策略的 纳什均衡可能有４个、３个、２个、１个和0个五种情况，所以可能有３个。例如，当参与 人Ａ与Ｂ的支付矩阵可分别表示如下时，总的支付矩阵中恰好有三个单元格的两个数字均有下划线，从而，总共有三个纳什均衡。 A 的支付矩阵＝ ??? ???22211211a a a a B 的支付矩阵＝11122122b b b b ??????? ? A 、B 共同的支付矩阵＝1111121222222121a b a b a b a b ???????? 具体事例为： 76157323?? ?? ?? ４．在只有两个参与人且每个参与人都只有两个策略可供选择的情况下，如何找到所 有的纯策略纳什均衡？ 解答：可使用条件策略下划线法。具体步骤如下：首先，把整个博弈的支付矩阵分解 为两个参与人的支付矩阵；其次，在第一个 （即位于整个博弈矩阵左方的）参与人的支付矩阵中，找出每一列的最大者，并在其下画线；再次，在第二个 （在位于整个博弈矩阵上 方的）参与人的支付矩阵中，找出每一行的最大者，并在其下画线；然后，将已经画好线的两个参与人的支付矩阵再合并起来，得到带有下划线的整个博弈的支付矩阵；最后，在带有下划线的整个的支付矩阵中，找到两个数字之下均画有线的支付组合。由该支付组合 代表的策略组合就是博弈的纳什均衡。 ５．设有Ａ、Ｂ两个参与人。对于参与人Ａ的每一个策略，参与人Ｂ的条件策略有无 可能不止一个？试举一例说明。 解答：例如，在如表１０—１的二人同时博弈中，当参与人 Ａ选择上策略时，参与人 Ｂ 既可以选择左策略，也可以选择右策略，因为他此时选择这两个策略的支付是完全一样 的。因此，对于参与人Ａ的上策略，参与人Ｂ的条件策略有两个，即左策略和右策略。 表１０—１
数学归纳法证题步骤与技巧 １.数学归纳法的范围 因此,数学归纳法的适用范围仅限于与自然数有关的命题。它能帮助我们判断种种与自然数n 有关的猜想的正确性。 2.数学归纳法两个步骤的关系 第一步是递推的基础,第二步是递推的根据，两个步骤缺一不可。 3.第一、二数学归纳法 第一数学归纳法可以概括为以下三步:（1)归纳奠基:证明n=1时命题成立；（2)归纳假设:假设ｎ=k 时命题成立;(3)归纳递推:由归纳假设推出n ＝k+1时命题也成立。从而就可断定命题对于从所有正整数都成立 第二数学归纳法的证明步骤是： １、证明当n ＝1时命题是正确的; 2、k 为任意自然数，假设n
数学归纳法证题步骤与技巧 在数学问题中，有一类问题是与自然数有关的命题。自然数有无限多个，不可能就所有自然数—一加以验证，所以用完全归纳法是不可能的。但就部分自然数进行验证即用不完全归纳法得到的结论，又是不可靠的。这就需要寻求证明这一类命题的一种切实可行而又满足逻辑严谨性要求的新方法——数学归纳法。1.数学归纳法的范围 数学归纳法是以自然数的归纳公理做为它的理论基础的。因此，数学归纳法的适用范围仅限于与自然数有关的命题。它能帮助我们判断种种与自然数n有关的猜想的正确性。 2.数学归纳法两个步骤的关系 第一步是递推的基础，第二步是递推的根据，两个步骤缺一不可，有第一步无第二表，属于不完全归纳法，论断的普遍性是不可靠的；有第二步无第一步中，则第二步中的假设就失去了基础。只有把第一步结论与第二步结论联系在一起，才可以断定命题对所有的自然数n都成立。 3.第二数学归纳法 第二数学归纳法的证明步骤是： 证明当n=1时命题是正确的； ②k为任意自然数，假设n＜k时命题都是正确的，如果我们能推出n=时命题也正确，就可以肯定该命题对一切自然数都正确。数学归纳法和第二归纳法是两个等价的归纳法，我们把数学归纳法也叫做第一归纳法。有些命题用第一归纳法证明不大方便，可以用第二归纳法证明。 4.数学归纳法的原理 数学归纳法证明的是与自然数有关的命题，它的依据是皮亚诺提出的自 然数的序数理论，就是通常所说的自然数的皮亚诺公理，内容是： （1）l是自然数。 （2）每个自然数a有一个确定的“直接后继”数a’，a也是自然数。 （2）a’≠1，即1不是任何自然数的“直接后继”数。 （4）由a’=b’，推得a=b，即每个自然数只能是另外的唯一自然的“直接后继” 数。 （5）任一自然数的集合，如果包含1，并且假设包含a，也一定包含a的“直接后继”数a’，则这个集合包含所有的自然数。皮亚诺公理中的（5）是数学归纳法的依据，又叫归纳公理数学归纳法的应用及举例。 2k+1k+2 因为由假设知4 +3能被13整除，13·42k+1也能被13整除，这就是说，当n=k ＋1时，f（k＋l）能被13整除。根据（1）、（2），可知命题对任何n∈N都成立。下面按归纳步中归纳假设的形式向读者介绍数学归纳法的几种不同形式以及它们的应用。 （l）简单归纳法。即在归纳步中，归纳假设为“n=k时待证命题成立”。这是最