第一讲 走近博弈论.ppt

《趣味博弈论》 杨驭云 华南师范大学南海校区 第一讲 走近博弈论 Game：策略、计谋 Game Theory：博弈论、对策论 从策略到博弈 因利益而发生冲突或对抗是人类社会的普遍现象。小到人生棋局、日常生活、赌博游戏，大到国家政治、生死之地、存亡之道，策略性对抗都是最为常见的局势。 游戏——下棋、石头剪刀布 经济——寡头产量决策、价格战、投标拍卖 政治、军事——投票选举、中东战争 博弈就是策略互动，就是一些个人、队组或其他组织，面对一定的环境条件，在一定的规则下，同时或先后，一次或多次，从各自允许选择的策略中进行选择并加以实施，各自取得相应结果或收益的过程。 任何一场博弈中，每个参与者所得到的赢利不仅取决于自己如何“出招”，也取决于其他人如何“出招”。正是这种战术上的互动，使得博弈充满了趣味、新奇，甚至惊险、刺激。 定义 博弈论（ Game Theory）就是专门研究互动局势下人们的策略行为的理论。 基本要素 局中人(Player) ：博弈的参与者 策略(Strategies)：各参与者可以选择的应对手段、方法 收益或支付(Payoffs)：各参与者可能得到的赢利 基本假设 人都是完全理性的。 人们不会有任何道德、良心和情感上的考虑，在一场博弈中，每个局中人的唯一目标就是使自己的收益最大化。 猜硬币 两个参与者甲、乙各出示一枚硬币，在不让对方看见的情况下，将硬币放在桌上。若两个硬币都呈正面或反面，则甲得1分，乙付出1分；若两个硬币一正一反，则乙得1分，甲付出1分。 这是一个典型的两人有限零和博弈。 收益矩阵 石头、剪刀、布 田忌赛马 分钱博弈 两个人因为如何分配10美元的问题争执不休，最后他们决定按如下方法来分配：每个人都说出一个自己的预期金额，该金额在0到10美元之间且允许出现两位小数。两人需要同时做出选择。 如果两个人的预期金额的和不超过10美元，那么每个人获得自己的预期金额，剩余的钱被销毁。 否则，每个人都一无所获并且钱也会被销毁。 囚徒困境 囚徒困境是阿尔伯特·塔克（Albert Tucker）1950年提出的。 囚徒困境是博弈论最经典、最著名的博弈模型。 囚徒困境本身讲的是一个法律刑侦或犯罪学方面的问题，但可以扩展到许多经济问题，以及各种社会问题。 两个人因盗窃被捕，警方怀疑其有抢劫行为但未获得确凿证据可以判他们犯了抢劫罪，除非有一个人供认或两个人都供认。即使两个人都不供认，也可以判他们犯盗窃物品的轻罪。 囚徒被分离审查，不允许他们之间互通消息，并交代政策如下： 如果两个人都供认，则两个人都将因抢劫罪加盗窃罪被判5年监禁； 如果两个人都拒供，则两个人都将因盗窃罪被判处1年监禁； 如果一个人供认而另一个拒供，则供认者被认为有立功表现而免受处罚，拒供者将因抢劫罪、盗窃罪以及抗拒从严而被重判10年。 辩诉交易（plea bargain）是指在法院开庭审理之前，作为控诉方的检察官和代表被告人的辩护律师进行协商，以检察官撤销指控、降格指控或者要求法官从轻判处刑罚为条件，来换取被告人的有罪答辩，进而双方达成均可接受的协议。 两个囚徒该如何选择呢？ 收益矩阵 囚徒1：供认 囚徒2：供认 囚徒困境通常被看作个人理性与集体理性冲突的经典情形，反映了个人最佳选择并不一定是集体最佳选择 。 优势策略 优势策略：不论其他局中人采取什么策略，对一个局中人而言都是最好的策略。 劣势策略 纳什均衡 一个策略组合中，所有的局中人都面临这样的一种情况：当其他人不改变策略时，他此时的策略是最好的。 在纳什均衡点上，每一个理性的参与者都不会有单独改变策略的冲动。 理性的人永远不会选择其劣势策略。 可以通过不断剔除劣势策略的方法来寻找纳什均衡点。 不是每个博弈都存在纳什均衡点，比如石头剪刀布。 纳什均衡点可以是一个，比如囚徒困境；也可以是多个，比如分钱博弈。 纳什均衡是博弈的一种稳定结局，可能出现，也可能不出现。 选票博弈 某场选举有两位候选人。 一系列政治主张中，共有10个立场，每个政治立场都有10%的得票。 选民会投票给与自己立场最接近的候选人。若某立场与两位候选人等距，那么持该立场选民的选票会平均分给两位候选人。 立场1劣于立场2？ 基于对称性，可知立场10严格劣于立场9。 立场2劣于立场3？ 同样基于对称性，可知立场