1、博弈论博弈论 威胁和承诺威胁和承诺game猜数字游戏猜数字游戏 任选一名学生与老师共同完成任选一名学生与老师共同完成 老师在老师在0-100之中任选一个数字写好；之中任选一个数字写好； 学生在学生在0-100之间猜数字，有之间猜数字，有5次机会，每次次机会，每次猜完后老师告知大于或小于目标数字。猜完后老师告知大于或小于目标数字。目录 4.1 动态博弈的描述动态博弈的描述 4.2 威胁与承诺的可信性威胁与承诺的可信性 4.3 序贯理性序贯理性 4.4 逆推归纳法逆推归纳法 尝试考虑以下问题尝试考虑以下问题 1、是不是信息越多越有利？、是不是信息越多越有利？ 2、过程是否重要？、过程是否重要？ 3
2、、动态博弈与静态博弈有哪些异同之处？、动态博弈与静态博弈有哪些异同之处？ 4、人们对已经过去的博弈是更注重结果还、人们对已经过去的博弈是更注重结果还是更注重过程？其意义何在？是更注重过程？其意义何在？4.1 动态博弈的描述4.1 动态博弈的描述 动态博弈：博弈方动态博弈：博弈方先后、依次先后、依次进行选择、行动，进行选择、行动，且后行动方知道先行动方的选择。且后行动方知道先行动方的选择。静态博弈：静态博弈：同时或可看做同时同时或可看做同时动态博弈动态博弈序贯博弈序贯博弈一方在行动一方在行动时不知道对时不知道对方策略方策略 行动有先后顺序，不同的参与人在不同时点行动，行动有先后顺序，不同的参与人
3、在不同时点行动，先行动者的选择影响后行动者的选择空间，后行动先行动者的选择影响后行动者的选择空间，后行动者可以观察到先行动者做了什么选择。者可以观察到先行动者做了什么选择。 为了做出最优的行动选择，每个参与人都必须这样为了做出最优的行动选择，每个参与人都必须这样思考问题：思考问题： 如果我如此选择，对方将如何应对？如果我是他，我将如果我如此选择，对方将如何应对？如果我是他，我将会如何行动？给定他的应对，什么是我的最优选择？会如何行动？给定他的应对，什么是我的最优选择？ 下棋、买东西、谈婚论嫁下棋、买东西、谈婚论嫁4.1 动态博弈的描述为进入一行为进入一行业，进入者业，进入者必须付出必须付出40
4、00万元的万元的（沉没）成（沉没）成本建工厂。本建工厂。 进入者不进进入者不进入，在位者能入，在位者能继续定高价，继续定高价，享受垄断利润享受垄断利润10000万元。万元。 进入者进入：进入者进入：在位者可以在位者可以“容忍容忍”，维，维持高价，此时持高价，此时在位者只能赚在位者只能赚到到5000万元，万元，进入者将赚到进入者将赚到1000万元的净万元的净利润；在位者利润；在位者可以可以“阻挠阻挠”，把价格压低，把价格压低，这种商战导致这种商战导致双方的低利润：双方的低利润：在位者的利润在位者的利润下降到下降到3000万万元，进入者将元，进入者将有有1000万元的万元的净损失。净损失。 进入不
5、进入，进入不进入，阻挠不阻挠？阻挠不阻挠？4.1 动态博弈的描述 每一种可能行动组合下的收益是共同知识每一种可能行动组合下的收益是共同知识 如果企图进入者不进入，则在位者独享如果企图进入者不进入，则在位者独享10000万元利润；万元利润； 如果进入而在位者容忍，则在位者得如果进入而在位者容忍，则在位者得5000万元万元,进入者利润进入者利润1000万元；万元； 如果进入并且在位者阻挠，则在位者利润如果进入并且在位者阻挠，则在位者利润3000万元而进入者万元而进入者-1000万元。万元。4.1 动态博弈的描述信息完全且完美信息完全且完美4.1 动态博弈的描述不进入不进入进进入入容忍容忍阻挠阻挠(
6、0,10000)(1000,5000)(-1000,3000)扩展形表示法扩展形表示法( (博弈树）博弈树）扩展形表示法扩展形表示法( (博弈树博弈树) )的构成：的构成：节点节点（nodesnodes）决策节点（决策节点（decision nodesdecision nodes） 终点节（终点节（terminal nodesterminal nodes）树枝树枝（branchesbranches）：每一条树枝代表一个行动）：每一条树枝代表一个行动信息集信息集（information setsinformation sets）：参与人在决策节）：参与人在决策节点选择行动时，需要有关信息；对此前
7、博弈过程点选择行动时，需要有关信息；对此前博弈过程的一个全部而明确的认识就构成一个信息集。的一个全部而明确的认识就构成一个信息集。4.1 动态博弈的描述 战略战略 在动态博弈中，博弈方的战略是在不同时在动态博弈中，博弈方的战略是在不同时点做出的，因此战略不再是单一的行动。点做出的，因此战略不再是单一的行动。 是一个是一个完备的行动计划完备的行动计划，为博弈方在每个，为博弈方在每个时点上规定一个动作。时点上规定一个动作。 “华容道”、刘备“过江招亲”4.1 动态博弈的描述 战略战略 一种无条件的回应规则一种无条件的回应规则 限制限制/规定自己的行动，达到博弈的目的规定自己的行动，达到博弈的目的（
8、提前说明规则）（提前说明规则） 一种威胁或承诺一种威胁或承诺 楚国孙叔敖令治水渠4.1 动态博弈的描述4.2 威胁与承诺的可信性 4.2.1 威胁与承诺威胁与承诺 4.2.2 一个威胁可信性问题一个威胁可信性问题 4.2.3 一个承诺可信性问题一个承诺可信性问题 4.2.4 威胁与承诺的可行性威胁与承诺的可行性 可信性可信性 动态博弈中，先行为的博弈方动态博弈中，先行为的博弈方是否应该是否应该相信相信后行为博弈方会采取某种策略或行为。后行为博弈方会采取某种策略或行为。 后行为博弈方的许诺是否可信呢？后行为博弈方的许诺是否可信呢？ 后行为博弈方的威胁是否可信呢？后行为博弈方的威胁是否可信呢？4.
9、2.1 威胁与承诺 威胁威胁对不肯与你合作的对手进行惩罚的对不肯与你合作的对手进行惩罚的一种回应规则。一种回应规则。 强迫性威胁强迫性威胁 人质事件 阻吓性威胁阻吓性威胁 核武器4.2.1 威胁与承诺 承诺承诺对愿意与你合作的人提供回报的一对愿意与你合作的人提供回报的一种回应规则。种回应规则。 强迫性许诺强迫性许诺 证人 阻吓性许诺阻吓性许诺 劝诱 威胁与承诺有时难以区分威胁与承诺有时难以区分 打卡扣钱制度打卡扣钱制度 威胁：迟到一次罚款威胁：迟到一次罚款10元（元（警告警告） 承诺：不迟到就不扣钱（承诺：不迟到就不扣钱（保证保证）4.2.1 威胁与承诺 当实施威胁策略或承诺策略时，首先当实施
10、威胁策略或承诺策略时，首先考虑的应该是可信度问题。考虑的应该是可信度问题。 进口食材的威胁 曹操寿宴 兄弟之间 承诺与威胁的可信度有多大，策略成承诺与威胁的可信度有多大，策略成功的概率就有多大。功的概率就有多大。4.2.1 威胁与承诺4.2.2 一个威胁可信性问题“只要进入就阻挠”的威胁是否可信？不进入不进入进进入入容忍容忍阻挠阻挠(0,10000)(1000,5000)(-1000,3000)4.2.2 一个威胁可信性问题事实事实上，上，这个这个威胁威胁是不是不可信可信的的，因为因为理性理性的在的在位者位者知道知道（如（如同潜同潜在进在进入者入者所所知）知），一旦一旦进入进入已经已经发生发生
11、了，了，容忍容忍并保并保持高持高价是价是符合符合自己自己利益利益的。的。容忍容忍得得5000万元，万元，阻挠阻挠得得3000万元。万元。不进入不进入进进入入容忍容忍阻挠阻挠(0,10000)(1000,5000)(-1000,3000)稳定的结果是稳定的结果是（进入，容忍）进入，容忍） 新的博弈格局：新的博弈格局：4.2.2 一个威胁可信性问题不进入不进入(0,7000)进进入入容忍容忍阻挠阻挠(1000,2000)(-1000,3000) 设设在位在位者现者现在在（而（而不是不是后）后）投资投资于万于万一进一进入发入发生时生时增加增加产量产量和进和进行价行价格战格战所需所需要的要的额外额外的
12、生的生产能产能力，力，成本成本是是3000万元。万元。 当当然，然，如果如果今后今后在位在位者保者保持高持高价价（不（不管是管是否有否有进进入），入），这个这个额外额外成本成本将减将减少在少在位者位者的得的得益益。不进入不进入 (0,7000)进进入入容忍容忍阻挠阻挠(1000,2000)(-1000,3000)4.2.2 一个威胁可信性问题 阻阻挠的威挠的威胁是完胁是完全可全可信的信的，它是在它是在位者投位者投资额外资额外生产能生产能力的决力的决策的结策的结果。果。（3000万元万元2000万万元）元） 潜潜在进入在进入者现在者现在知道知道进入的进入的结果是结果是商战，商战，所以不所以不进入
13、该进入该行业是行业是理智的。理智的。 20世纪70年代，美国杜邦公司在二氧化钛行业中阻止进入，投资近4亿美元增加生产能力4.2.2 一个威胁可信性问题 先来后到的启示先来后到的启示 后进者信息多，但利润不如先进入者。后进者信息多，但利润不如先进入者。4.2.3 一个承诺可信性问题开金矿开金矿 甲去开采一价值甲去开采一价值4万元的金矿，缺万元的金矿，缺1万元，乙恰好万元，乙恰好有有1万元可以投资。甲向乙借万元可以投资。甲向乙借1万元开金矿，并万元开金矿，并“许诺许诺”成功后与其对半分成。成功后与其对半分成。 乙是否该借钱给甲呢？乙是否该借钱给甲呢？ 如果乙借钱给甲，甲是如果乙借钱给甲，甲是 否该
14、分钱给乙呢？否该分钱给乙呢？甲的承诺是否可信？甲的承诺是否可信？4.2.3 一个承诺可信性问题 根据自身利益最大化原则，根据自身利益最大化原则，甲的选择是不分，而乙清楚甲的选择是不分，而乙清楚甲的行为准则，则选择不借。甲的行为准则，则选择不借。对乙来讲，本博弈中甲有一对乙来讲，本博弈中甲有一个不可信的承诺。个不可信的承诺。 怎样使甲的承诺变为可信，既让乙能保住本钱，又能有怎样使甲的承诺变为可信，既让乙能保住本钱，又能有更多的收益呢？关键在于增加一些对甲行为的约束。更多的收益呢？关键在于增加一些对甲行为的约束。4.2.3 一个承诺可信性问题 若乙采取法律手若乙采取法律手段，即打官司保护自段，即打
15、官司保护自己的利益，则产生了己的利益，则产生了一个新的博弈过程如一个新的博弈过程如图所示。图所示。 在新的博弈中，在新的博弈中，乙的唯一选择是打官乙的唯一选择是打官司，对甲来讲，乙打司，对甲来讲，乙打官司的威胁是可信的，官司的威胁是可信的，是肯定会信守的，他是肯定会信守的，他最理智的选择就是分。最理智的选择就是分。4.2.3 一个承诺可信性问题乙乙甲甲乙乙打打（2，2）不分不分分分不借不借借借（0，4）（1，0）不打不打（1，0）法律保障的开金矿博弈法律保障的开金矿博弈分钱打官司都可信分钱打官司都可信 乙的策略：第一乙的策略：第一阶段借，如甲在第二阶段借，如甲在第二阶段选择不分，则第阶段选择不
16、分，则第三阶段选择打；甲的三阶段选择打；甲的策略：若乙第一阶段策略：若乙第一阶段借，则他在第二阶段借，则他在第二阶段就选择分。就选择分。 在双方这样的策在双方这样的策略组合下，略组合下，本博弈的本博弈的路径是（借，分），路径是（借，分），双方得益为（双方得益为（2 2，2 2），实现有效率的），实现有效率的理想结果。理想结果。4.2.3 一个承诺可信性问题乙乙甲甲乙乙打打（2，2）不分不分分分不借不借借借（0，4）（1，0）不打不打（1，0） 若乙采取法律若乙采取法律手段，但结果是劳手段，但结果是劳民伤财，使自己经民伤财，使自己经济上受损。济上受损。 在新的博弈中，在新的博弈中，乙的唯一选择是
17、不乙的唯一选择是不打官司，对甲来讲，打官司，对甲来讲，乙打官司的威胁是乙打官司的威胁是不可信的，甲最理不可信的，甲最理智的选择就是不分。智的选择就是不分。4.2.3 一个承诺可信性问题法律保障不足的开金矿博弈法律保障不足的开金矿博弈分钱打官司都不可信分钱打官司都不可信乙乙甲甲乙乙打打（2，2）不分不分分分不借不借借借（0，4）（-1，0）不打不打（1，0） 开金矿的启示开金矿的启示 让别人有机会对你发出一个威胁永远不让别人有机会对你发出一个威胁永远不是好事。你大可以选择按照对方的希望行动，是好事。你大可以选择按照对方的希望行动，却没有必要等到听见一个威胁。却没有必要等到听见一个威胁。4.2.3
18、 一个承诺可信性问题4.2.4 威胁与承诺的可信性 以色列的一贯原则：以色列的一贯原则：坚决不跟恐怖分子谈判坚决不跟恐怖分子谈判 这是一个威胁，意在阻吓恐怖分子，打消他们这是一个威胁，意在阻吓恐怖分子，打消他们企图劫持人质，以此索取赎金或者要求释放犯企图劫持人质，以此索取赎金或者要求释放犯人的念头。假如这个决不谈判的威胁是可信的，人的念头。假如这个决不谈判的威胁是可信的，那么，恐怖分子就会意识到他们的行动注定徒那么，恐怖分子就会意识到他们的行动注定徒劳无功。劳无功。项羽破釜沉舟：巨鹿之战项羽破釜沉舟：巨鹿之战 项羽率领大军渡河。然后项羽率领大军渡河。然后“破釜沉舟破釜沉舟”,命令士兵只命令士兵
19、只携带三日粮，以此表示有进无退。于是历史上闻名的携带三日粮，以此表示有进无退。于是历史上闻名的巨鹿之战上演了：当时，诸侯军救巨鹿的十多支队伍，巨鹿之战上演了：当时，诸侯军救巨鹿的十多支队伍，却没有人敢向围城的秦军挑战。却没有人敢向围城的秦军挑战。 而只有项羽的军队勇猛、而只有项羽的军队勇猛、视死如归，以一当十。这视死如归，以一当十。这一战不但打垮了秦军主力，一战不但打垮了秦军主力，也将秦军不可战胜的神话也将秦军不可战胜的神话彻底击破，更一举奠定了彻底击破，更一举奠定了“楚兵冠诸侯楚兵冠诸侯”的英明。的英明。 在军事上，孤注一掷有时并不是一个愚蠢的策略。在军事上，孤注一掷有时并不是一个愚蠢的策略
20、。军队通常借助断绝自己后路的做法而达成遵守承诺的军队通常借助断绝自己后路的做法而达成遵守承诺的目标。目标。4.2.4 威胁与承诺的可信性4.3 序贯理性 4.3.1 动态博弈中的理性要求动态博弈中的理性要求 4.3.2 子博弈子博弈 4.3.3 子博弈完美纳什均衡子博弈完美纳什均衡4.3.1 动态博弈中的理性要求 在动态博弈中，博弈方如果是理性的，他应在动态博弈中，博弈方如果是理性的，他应该该“向前看向前看” 不管不管事前制订的计划事前制订的计划如何，如何，他在新的时点上做决策都应该他在新的时点上做决策都应该根据当前的情根据当前的情况选择况选择最优的行动。最优的行动。 运筹帷幄，决胜于千里之外
21、 将在外，军令有所不受 序贯理性序贯理性 要求博弈方在一个接一个的决策节点上都要选要求博弈方在一个接一个的决策节点上都要选择最优行动。择最优行动。 进一步，如果某个博弈方是序贯理性的，那么他所进一步，如果某个博弈方是序贯理性的，那么他所使用的战略将是由他在每个时点上的最优行动组成。使用的战略将是由他在每个时点上的最优行动组成。 该战略不仅在事前最优，也是事后最优的该战略不仅在事前最优，也是事后最优的， 将满足动态一致性原则。将满足动态一致性原则。4.3.1 动态博弈中的理性要求4.3.2 动态博弈中的子博弈 动态博弈要求博弈方是序贯理性的，这动态博弈要求博弈方是序贯理性的，这意味着从任意一个决
22、策点开始的决策情意味着从任意一个决策点开始的决策情形就像是在原有博弈基础上开始一个形就像是在原有博弈基础上开始一个“新的博弈新的博弈”。4.3.2 动态博弈中的子博弈 子博弈：能够自成子博弈：能够自成一个博弈，由一个一个博弈，由一个动态博弈的某阶段动态博弈的某阶段（第一阶段除外）（第一阶段除外）开始的后续博弈阶开始的后续博弈阶段构成段构成。具备进行。具备进行博弈所需的各种信博弈所需的各种信息。息。乙4.3.2 动态博弈中的子博弈 注意：注意： 原博弈的初始节点开始的博弈为原博弈本身，原博弈的初始节点开始的博弈为原博弈本身，不称它为原博弈的子博弈，即第一个节点不不称它为原博弈的子博弈，即第一个节
23、点不能作为子博弈的初始节点。能作为子博弈的初始节点。 可以看出，每个子博弈都代表这博弈方所面临的可以看出，每个子博弈都代表这博弈方所面临的一个决策时机或情形，即每个子博弈都是一个独一个决策时机或情形，即每个子博弈都是一个独立的博弈，那么也有它的纳什均衡。立的博弈，那么也有它的纳什均衡。 一个博弈中有多个子博弈，那么博弈方在每一个一个博弈中有多个子博弈，那么博弈方在每一个子博弈上选择的最优行为就构成相应子博弈的纳子博弈上选择的最优行为就构成相应子博弈的纳什均衡。什均衡。4.3.3 子博弈完美纳什均衡4.3.3 子博弈完美纳什均衡 在动态博弈中由于博弈过程是逐步深入的，这一过程由在动态博弈中由于博
24、弈过程是逐步深入的，这一过程由每个阶段所采取的策略构成，由此引出每个阶段所采取的策略构成，由此引出“路径路径”的概念。的概念。 路径：从第一阶段开始通过每阶段一个行为，最后达到路径：从第一阶段开始通过每阶段一个行为，最后达到博弈结束的一个终端各博弈方的行为组合。博弈结束的一个终端各博弈方的行为组合。 找到了路径也就找到了一个分阶段的策略组合，这一策找到了路径也就找到了一个分阶段的策略组合，这一策略组合恰似一个完整的计划，计划的最终实现取决于过略组合恰似一个完整的计划，计划的最终实现取决于过程中各阶段的实现。程中各阶段的实现。4.3.3 子博弈完美纳什均衡在开金矿案例中，在开金矿案例中， 策略组
25、合（借，分）是策略组合（借，分）是 一个稳定的策略组合，一个稳定的策略组合， 因为如果不分，则有因为如果不分，则有 乙打官司的威胁，这乙打官司的威胁，这 是双方都不愿得到的结果。是双方都不愿得到的结果。 “稳定稳定”意味着博弈方都不会单独意味着博弈方都不会单独 改变策略，这恰似纳什均衡的概念。改变策略，这恰似纳什均衡的概念。乙4.3.3 子博弈完美纳什均衡 由于动态博弈与静态博弈有较大的差异，那么如何才由于动态博弈与静态博弈有较大的差异，那么如何才能使静态博弈中的纳什均衡在动态博弈中亦有相应的能使静态博弈中的纳什均衡在动态博弈中亦有相应的概念发展？概念发展？ 以开金矿为例（注意此例与以前开金矿
26、例子的差异）以开金矿为例（注意此例与以前开金矿例子的差异） 开金矿博弈的变形开金矿博弈的变形 甲开金矿，向乙借钱，如果甲在获利之后不分钱给乙，甲开金矿，向乙借钱，如果甲在获利之后不分钱给乙，而乙打官司对自己并没有好处，不能增加自己的利益时，而乙打官司对自己并没有好处，不能增加自己的利益时，博弈发生了变化。博弈发生了变化。4.3.3 子博弈完美纳什均衡4.3.3 子博弈完美纳什均衡 逆推可得，乙不借，乙打官司的威胁不可信。甲在第逆推可得，乙不借，乙打官司的威胁不可信。甲在第二阶段分的许诺也变为不可信。二阶段分的许诺也变为不可信。 结局是，结局是，甲开不成金矿，乙保本，甲失去挣钱的机会甲开不成金矿
27、，乙保本，甲失去挣钱的机会。（2 2，2 2）（1 1，0 0）（1 1，0 0）乙乙借借不借不借分分不分不分不打不打打打（0 0，4 4）开金矿开金矿（2 2，2 2）（1 1，0 0）（1 1，0 0）乙乙借借不借不借分分不分不分不打不打打打（0 0，4 4）开金矿开金矿变形变形 按照静态博弈的分析方法，（借，分，打）的策略组按照静态博弈的分析方法，（借，分，打）的策略组合为一个纳什均衡，因为任何一方都不会单独改变策合为一个纳什均衡，因为任何一方都不会单独改变策略而降低自己的得益略而降低自己的得益 这与逆推法得到的结论相矛盾，原因在于路径（借，这与逆推法得到的结论相矛盾，原因在于路径（借，
28、分）的纳什均衡策略组合包含了一个分）的纳什均衡策略组合包含了一个不可信的威胁不可信的威胁，即乙在第三阶段会选择打官司的行为是不可信的即乙在第三阶段会选择打官司的行为是不可信的. .4.3.3 子博弈完美纳什均衡4.3.3 子博弈完美纳什均衡由此需要对静态博弈中的纳什均衡的概念有所调整，由此需要对静态博弈中的纳什均衡的概念有所调整，即应满足：即应满足： 是纳什均衡，从而具有策略稳定性是纳什均衡，从而具有策略稳定性 不能包含任何不可信的许诺或威胁不能包含任何不可信的许诺或威胁 这样的动态博弈组合策略称为子博弈完美纳什均衡。这样的动态博弈组合策略称为子博弈完美纳什均衡。4.3.3 子博弈完美纳什均衡
29、 定义（定义（SeltenSelten泽尔滕，泽尔滕，19651965）：）： 如果动态博弈中各博弈方的策略在动态博弈本身和所如果动态博弈中各博弈方的策略在动态博弈本身和所有子博弈中都构成一个纳什均衡，则称该策略组合为一个有子博弈中都构成一个纳什均衡，则称该策略组合为一个“子博弈完美纳什均衡子博弈完美纳什均衡”。 Subgame-Perfect Nash Equilibrium 。 直观上看到的是：直观上看到的是：各参与人稳定的行动选择，它们各参与人稳定的行动选择，它们 构成一条走得通的路构成一条走得通的路均衡路径均衡路径(equilibrium path)(equilibrium path)
30、。 动态博弈所应注意的两点动态博弈所应注意的两点 要求各博弈方的策略对每阶段每种可能情况要求各博弈方的策略对每阶段每种可能情况都设定一个行为方案都设定一个行为方案 假定所有博弈方都是理性的且不会犯错误假定所有博弈方都是理性的且不会犯错误4.3.3 子博弈完美纳什均衡4.4 逆推归纳法 4.4.1 逆推归纳法逆推归纳法海盗分金海盗分金 4.4.2 逆推归纳法应用逆推归纳法应用 4.4.3 理性与非理性理性与非理性4.4.1 逆推归纳法 在动态博弈中如何求解？在动态博弈中如何求解？ 动态博弈的特点是：在采取某一种决策时必须对其后动态博弈的特点是：在采取某一种决策时必须对其后可能进行的子博弈有充分的
31、了解，这样才能很好的进可能进行的子博弈有充分的了解，这样才能很好的进行博弈并得到合理的结果（基于理性和可信性，相当行博弈并得到合理的结果（基于理性和可信性，相当于对后博弈行为方的合理假设）。于对后博弈行为方的合理假设）。 由此，对于完全且完美信息的动态博弈其基本求解方由此，对于完全且完美信息的动态博弈其基本求解方法，可由最后阶段的子博弈逆推来决定采取合适的策法，可由最后阶段的子博弈逆推来决定采取合适的策略略-逆推归纳法。逆推归纳法。4.4.1 逆推归纳法 逆推归纳法：从动态博弈的最后一个阶段或逆推归纳法：从动态博弈的最后一个阶段或最后一个子博弈开始，最后一个子博弈开始，逐步向前倒推逐步向前倒推
32、以求解以求解动态博弈的方法。动态博弈的方法。 用逆推归纳法求解开金矿用逆推归纳法求解开金矿乙4.4.1 逆推归纳法 5 5个海盗抢了个海盗抢了100100颗宝石，每颗大小一样价值连城。颗宝石，每颗大小一样价值连城。 1. 1. 抽签决定自己的号码（抽签决定自己的号码（1,2,3,4,51,2,3,4,5），）， 2. 2. 首先，由首先，由1 1号提出分配方案，然后大家号提出分配方案，然后大家 5 5人进行表决，当且仅当人进行表决，当且仅当超过半数超过半数的人同意时，的人同意时， 按照他的提案进行分配，否则将被扔进大海喂鲨鱼按照他的提案进行分配，否则将被扔进大海喂鲨鱼 3. 3. 如果如果1
33、1号死了，再由号死了，再由2 2号提出分配方案，然号提出分配方案，然 后大家后大家4 4人进行表决，当且仅当人进行表决，当且仅当超过半数超过半数人同人同 意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼 4. 4. 以次类推，直到找到一个每个人都接受的方案以次类推，直到找到一个每个人都接受的方案4.4.1 逆推归纳法 假设假设每个海盗都是很聪明的人，都能很理智的判断得失每个海盗都是很聪明的人，都能很理智的判断得失 第一个海盗提出怎样的分配第一个海盗提出怎样的分配 方案方案 才能使自己得到最多才能使自己得到最多 的宝石呢？的宝石呢？4.4.1
34、逆推归纳法逆推过程逆推过程 1 2 3 4 5 1 2 3 4 5 0 100 0 100 99 1 0 99 1 0 97 0 2 1 97 0 2 1 97 0 1 0 2 97 0 1 0 2结果结果: : (97,(97,0,1,0,2)0,1,0,2)4.4.1 逆推归纳法 强盗分金的启示强盗分金的启示 在该模型中，任何在该模型中，任何“分配者分配者”想让自己的方案获得通过的想让自己的方案获得通过的关键是事先考虑清楚关键是事先考虑清楚“挑战者挑战者”的分配方案是什么，并用的分配方案是什么，并用最小的代价获取最大收益，最小的代价获取最大收益，拉拢拉拢“挑战者挑战者”分配方案中最分配方案
35、中最不得意的人们。不得意的人们。 “不谋万事者，不足谋一时；不谋全局者，不足谋一域。不谋万事者，不足谋一时；不谋全局者，不足谋一域。” 4.4.1 逆推归纳法 先发优势和后发劣势先发优势和后发劣势 1号看起来最有可能被喂鲨鱼，但他牢牢地把号看起来最有可能被喂鲨鱼，但他牢牢地把握住先发优势，结果不但消除了死亡威胁，还握住先发优势，结果不但消除了死亡威胁，还收益最大。这不正是全球化过程中先进国家的收益最大。这不正是全球化过程中先进国家的先发优势吗？先发优势吗？ 而而5号看起来最安全，甚至还能坐收渔人之利，号看起来最安全，甚至还能坐收渔人之利，却因不得不看别人脸色行事而只能分得一小杯却因不得不看别人
36、脸色行事而只能分得一小杯羹。这难道不是后发劣势的写照？羹。这难道不是后发劣势的写照？4.4.1 逆推归纳法4.4.1 逆推归纳法动态规划 动态规划的理论基础是最优性原理。它是一种解决多动态规划的理论基础是最优性原理。它是一种解决多阶段决策（序贯决策）过程最优化的一种数学方法。阶段决策（序贯决策）过程最优化的一种数学方法。 应用：最优路径问题、资源分配问题、生产调应用：最优路径问题、资源分配问题、生产调 度、库存、装载、排序、设备更新、最度、库存、装载、排序、设备更新、最 优工艺等优工艺等 4.4.2 逆推归纳法应用 A、游戏中的逆推归纳、游戏中的逆推归纳 全班同学分为全班同学分为a、b两组，相
37、对而立，中间地面竖两组，相对而立，中间地面竖立立21支小旗。支小旗。 a、b两组一次轮流拿走这些小旗；两组一次轮流拿走这些小旗； 每组可选择取走每组可选择取走1支、支、2支、支、3支旗，不能一直支旗，不能一直都不取，也不能取走都不取，也不能取走4支或支或4支以上。支以上。 哪个小组取走最后一只旗，就算获胜。不管这支哪个小组取走最后一只旗，就算获胜。不管这支旗是最后旗是最后1支、支、2支还是支还是3支中的支中的1支。支。 A、游戏中的逆推归纳、游戏中的逆推归纳获胜的秘诀是：获胜的秘诀是： 不管如何选择，最后一轮留给对方不管如何选择，最后一轮留给对方4支旗支旗 上一轮留给对方上一轮留给对方8支旗支
38、旗 再上一轮留给对方再上一轮留给对方12支旗支旗 前一轮留给对方前一轮留给对方16支旗支旗 前一轮留给对方前一轮留给对方20支旗支旗4.4.2 逆推归纳法应用 B、商业中的逆推归纳法、商业中的逆推归纳法“编辑部的启事编辑部的启事”： 亲爱的读者朋友，从亲爱的读者朋友，从1月月1日起，征订本报的金额将增加，日起，征订本报的金额将增加，全年费用为全年费用为460元。这很遗憾，但我们不得不这样做，现在纸元。这很遗憾，但我们不得不这样做，现在纸张涨价，销售劳务费也太提高了，报社要生存。在这种新形张涨价，销售劳务费也太提高了，报社要生存。在这种新形势下，我们增加了订费。对于你们来说，完全有权拒绝订阅势下
39、，我们增加了订费。对于你们来说，完全有权拒绝订阅本报，因为它涨价了。您可以把这本报，因为它涨价了。您可以把这460元用在比订费更急需的元用在比订费更急需的地方：比如地方：比如460元就是一张短途机票的价格，可以去朋友一起元就是一张短途机票的价格，可以去朋友一起去酒吧喝一次，或者是购买一条香烟去酒吧喝一次，或者是购买一条香烟但是，这些消费都但是，这些消费都是一次性的，而如果您订阅本报，将全年持有天天都有一份。是一次性的，而如果您订阅本报，将全年持有天天都有一份。亲爱的读者，不管您明年是否继续订阅本报，最后我们仍要亲爱的读者，不管您明年是否继续订阅本报，最后我们仍要感谢您多年来的支持。感谢您多年来
40、的支持。4.4.2 逆推归纳法应用 “逆推法逆推法”处理问题是报社成功的关键。先处理问题是报社成功的关键。先退出读者的想法，再为读者分析，这样想并退出读者的想法，再为读者分析，这样想并不是最好的选择。不是最好的选择。 “逆推归纳法逆推归纳法”教给我们教给我们善于打动人心的经善于打动人心的经销策略和手段销策略和手段。 “超市洗衣粉售卖案例超市洗衣粉售卖案例”4.4.2 逆推归纳法应用 C、生活中的逆推归纳法、生活中的逆推归纳法 李恕权李恕权 台湾歌手，唯一获得格莱美音乐台湾歌手，唯一获得格莱美音乐 大奖提名的华裔歌手。大奖提名的华裔歌手。 挑战你的信仰挑战你的信仰4.4.2 逆推归纳法应用 你今
41、天的生活，是由几年前所做的选择决你今天的生活，是由几年前所做的选择决定的；而你今天的选择，会影响你今后几定的；而你今天的选择，会影响你今后几年的生活。年的生活。 人生博弈的法则人生博弈的法则什么样的选择决定什什么样的选择决定什么样的人生。么样的人生。4.4.2 逆推归纳法应用你的时间去哪儿了？4.4.3 理性与非理性如：海盗分金博弈中如：海盗分金博弈中 1 2 3 4 5 1 2 3 4 5 0 100 0 100 99 1 0 99 1 0 97 0 2 1 97 0 2 1 97 0 1 0 2 97 0 1 0 2 若其他海盗联合起来选择若其他海盗联合起来选择“非理性非理性”，建议重，建
42、议重新分配，这种非理性行为恰恰是理性的。新分配，这种非理性行为恰恰是理性的。 又如：又如： 后续可能性太多而无法分析，于是考虑仅知后续可能性太多而无法分析，于是考虑仅知道有限后续阶段的情况？道有限后续阶段的情况？ 许诺有限非理性，如何考虑？比如假设非理许诺有限非理性，如何考虑？比如假设非理性的次数小于等于性的次数小于等于k k？下棋？下棋 K K叉树算法叉树算法 博弈构成的博弈构成的“长短长短”与稳定性，不可预测性与稳定性，不可预测性等等4.4.3 理性与非理性旅行者困境旅行者困境 两个旅行者从一个以出产细瓷花瓶著名的地方旅行回来，两个旅行者从一个以出产细瓷花瓶著名的地方旅行回来，他们都买了花
43、瓶。提取行李的时候，发现花瓶被摔坏了。他们都买了花瓶。提取行李的时候，发现花瓶被摔坏了。他们向航空公司索赔。他们向航空公司索赔。 航空公司知道花瓶的价格总在八九十元的价位浮动，但航空公司知道花瓶的价格总在八九十元的价位浮动，但是不知道两位旅客买的时候的确切价格。是不知道两位旅客买的时候的确切价格。4.4.3 理性与非理性 航空公司请两位旅客在航空公司请两位旅客在100元以内自己写下花瓶的价格。元以内自己写下花瓶的价格。 如果两人写的价格一样如果两人写的价格一样(合作合作)，航空公司将认为他们讲真，航空公司将认为他们讲真话，于是按照他们写的数额赔偿话，于是按照他们写的数额赔偿 如果两人写的不一样
44、（如果两人写的不一样（背叛背叛），航空公司就认定写得低的），航空公司就认定写得低的旅客讲的是真话，并且原则上照这个低的价格赔偿，而且旅客讲的是真话，并且原则上照这个低的价格赔偿，而且对讲真话的旅客奖励对讲真话的旅客奖励2元钱，对讲假话的旅客罚款元钱，对讲假话的旅客罚款2元。元。 就为了获取最大赔偿而言，本来甲乙双方最好的策略就是就为了获取最大赔偿而言，本来甲乙双方最好的策略就是都写都写100元，这样两人都能获赔元，这样两人都能获赔100元。元。 该博弈为一个该博弈为一个蜈蚣博弈。蜈蚣博弈。4.4.3 理性与非理性 该博弈是说明逆推归纳法和博弈分析困难的经典博弈，该博弈是说明逆推归纳法和博弈分析
45、困难的经典博弈，1 1 和和 2 2 两个博弈方轮流选择的多阶段博弈，共两个博弈方轮流选择的多阶段博弈，共198198个阶段。个阶段。如下图如下图n根据逆推归纳法分析可得，博弈方会在第一阶段选择根据逆推归纳法分析可得，博弈方会在第一阶段选择 D D 结束博弈，双方得益都是结束博弈，双方得益都是 1 1 。蜈蚣博弈问题 蜈蚣博弈可看出，完全理性下的逆推归蜈蚣博弈可看出，完全理性下的逆推归纳法存在缺陷：纳法存在缺陷： 从逻辑上推理，一开始应开始选择不合作；从逻辑上推理，一开始应开始选择不合作； 但事实是，一开始就合作的收益为但事实是，一开始就合作的收益为100，不，不合作的收益仅为合作的收益仅为1
46、，合作才是最优的。，合作才是最优的。4.4.3 理性与非理性 另一个事实是：即使双方一开始都采取合作策略，另一个事实是：即使双方一开始都采取合作策略，一直往前走，这种合作也坚持不到最后一步一直往前走，这种合作也坚持不到最后一步只只要是理性的人，处于自己利益的考虑，在某一个时要是理性的人，处于自己利益的考虑，在某一个时刻，肯定会采取不合作策略。刻，肯定会采取不合作策略。 逆推归纳法试分析动态博弈的有效方法，不能因为逆推归纳法试分析动态博弈的有效方法，不能因为其预测和实际不符就完全否定其在分析和预测中的其预测和实际不符就完全否定其在分析和预测中的可行性可行性。4.4.3 理性与非理性End of chapter 4Thanks
