1、1（20_届）本科毕业设计信息与计算科学初探博弈论及其应用2摘要本文介绍博弈过程中涉及的基本概念及基本假设，然后举例说明博弈的表达方式，针对博弈的分类和概念，本文只是做了简单的文字介绍，重点放在博弈的应用上面，在列举实例时分析博弈中的策略及各个局中人的最优策略。关键词博弈策略分析纳什均衡囚徒困境GAMETHEORYANDITSAPPLICATIONABSTRACTINTHISPAPER,THEBASICCONCEPTSOFGAMETHEORYANDASSUMPTIONINVOLVEDINTHEPROCESSAREINTRODUCED,THENWECITEDEXAMPLESTOINTRODUCE
2、THEEXPRESSIONOFTHEGAMETHEORY,ANDWEJUSTDIDASIMPLETEXTDESCRIPTIONFORTHECONCEPTANDCLASSIFICATIONOFTHEGAMETHEORYWEFOCUSEDONTHEAPPLICATIONOFGAME,THATISWEANALYZEDSTRATEGYOFTHEGAMEANDTHEOPTIMALSTRATEGYFORTHEPLAYERSINTHEFOLLOWINGLISTEDCASESKEYWORDSGAMETHEORYSTRATEGIESANALYSISNASHEQUILIBRIUMPRISONERSDILEMMA3
3、1引言11博弈论的发展简介博弈论是20世纪50年代新兴的研究领域，因其在商业、拍卖、军事、生物学和博彩等方面的广泛应用，越来越被人们所关注1。1994年纳什与人分享了当年的诺贝尔经济学奖，2001年根据纳什生平改编电影的成功上映，使人们更加关注博弈论。博弈论源于数学，但从一开始，它的研究就不仅包含着数学方法，还融入了实验手段。在之后的发展中，博弈论逐渐跨越多个学科，广泛应用于经济学、政治学、哲学、商业活动和国际关系中，成为理解人类行为的有力工具。20年前，如果想要了解博弈论的非技术性介绍，也只能参阅戴维斯的博弈论非技术导论，当然谢林的战略冲突也可以供我们参考2。但经过这些年的发展，博弈论的理论
4、已深入人心。我国对博弈论的研究也越来越重视，博弈论也成为国内目前最有发展前途的学科之一。12博弈论的研究内容、对象在生活中的各个角落中，我们都无可避免的碰到各种各样具有竞争或利益相对抗的现象，譬如打牌、下棋等，而且竞争的各方总是希望击败对手，从而取得可能好的利益或结果。但在这过程中就需要采取好的战术，这就是博弈现象。而双方针对彼此所采取的战术的过程就是博弈的过程，这也就是博弈的主要研究内容。博弈论的研究对象主要是参与博弈的决策人，不管参与的人多或少都是我们的研究对象，常见的是二人博弈。13博弈论的研究意义博弈论在现实社会生活中的运用有的学者认为已经遍及经济学、社会科学、工商业活动以及日常的生活
5、之中。从博弈论的角度可以解释价格战、环境污染、军备竞赛、考试或体育竞技导致过多的参与者和加剧收入不平等的因素光从博弈论的涉及范围及发展速度我们就可以发现它的重要意义，正因为此，基于不同的抽象水平，形成了三种博弈表述方式，标准型、扩展型和特征函数型。利用这三种表述形式,可以研究形形色色的问题。因此,它被称为“社会科学的数学”3。从理论上讲，博弈论提供了分析和解决问题的独特和新颖的具有战略思维的思想方法，而且是研究理性的行动者相互作用的形式理论，而实际上正深入到经济学、政治学、社会学等等，被各门社会科学所应用。2博弈入门421博弈论基本概念参与人（PLAYER）是指在博弈中独立的决策主体。在一个对
6、立的博弈模型中，至少会有两个参与人，否则就无法确立互动的主体。博弈论在思考问题时，指考虑被界定在模型内的参与人之间的互动。参与人也可以有多方。当存在多方的情况下，参与人之间可以有结盟和不结盟之分。在建模时，哪些是参与人也需要认真审定，因为这与被研究的问题的性质及目的有关。收益向量（PAYOFFVECTOR）是对参与人行动及其他人行动组合实施时所产生结果的评价，它反映了参与人的偏好。也即一局博弈后各局中人的输赢得失，用UUUNU,21表示，其中NIUI,1为局中人I的收益。通常用正的数字表示局中人的赢得，负的数字表示局中人的损失。策略（STRATEGIES）指局中人所拥有的对付其他局中人的手段、
7、方案的集合，用SI表示第I个局中的策略集合，SI为局中人I的某一个策略。信息（INFORMATION）4是参与人有关博弈的知识，参与人在特定的行动点所知道的有关其他参与人的特征、“自然”的选择、其他参与人已选择的的行动等有关知识。信息使某些情况得以排除，同时，在给定的信息范围内又有些情况不能区分。公共知识5是指参与人都知道的知识，并且任何参与人在公共知识上，没有因为掌握这一知识而具有优势。战略是指参与人选择行动的规则。在参与人同时行动一次博弈就结束的问题中，战略和策略是直接对应的，即采取某种战略与选择某个行动是等价的。然后在行动有先后的多次行动的博弈问题中，这时战略就不能与某个策略相对应，由于
8、博弈进行后使得某些参与人在行动选择时已经观察到其他参与人如何行动的一些信息，参与人将依据信息制定选择行动的规划。规划的常用形式是“如果就”。对所有的可能观察到的信息确定行动规则，这样的行动规则就叫战略。换句话说，如果有了战略，就能“计算”出在相应的信息下该选择什么策略。在博弈的过程中，关键的不是采取什么策略，而是看参与人采取什么战略，参与人追求的是最优战略，这样才能达到利益最大。各个参与人在博弈中所选择具体战略的集合，就叫做战略组合。均衡是指按特定的意义规定的博弈模型的解，由于博弈是各参与人战略之间的较量，一个战略组合被称为均衡就是在某种规定的意义下达到了最优。博弈实际发生的行为序列称为均衡结
9、果。但是在动态博弈中，均衡结果会有所不同。22基本假设博弈论的研究是建立在下述假设的前提下，即参与博弈的各局中人都是理性的。所谓理性人，5有人认为是指有一个很好的偏好，在给定的约束条件下使自己的偏好最大化。不过我们也可以这样来描述在博弈的过程中，一个理性的策略或战略肯定是建立在其他局中人的决策上，此时的局中人将自己置身于其他局中人的位置上，换位思考，来预测他们将所采取的行动，在这个基础上该局中人决定使自己利益最大化的策略。23博弈研究的三种表示方法博弈论是研究理性参与人在竞争冲突的环境下如何用智慧的决策行为，使用的基本工具也就是数学的模型和推理。不同的博弈问题所采用的数学模型是不一样的。博弈论
10、研究的三种表示方法如下231规范式囚徒困境6因为某个案件，警察拘捕了两个犯罪嫌疑人并把他们隔离审讯。如果他们中间至少有一人供罪，那就可以确定罪名成立。为了获得嫌疑人的口供，警察将他们两个人分别关押审问以防止他们串供。如果两人都承认了，则两人都将判刑8个月。如果两人都不承认，那由于证据不足，两人各判1个月。如果其中一个人承认，而另一个不承认，那么承认罪行的那个人将得到宽大处理，不判刑立即释放。而不承认的那个人将受到严惩，判刑10个月。这样的话，犯罪嫌疑人将如何采取自己的行动呢如上所述，犯罪嫌疑人的行为和所产生的后果可以用下图表示。囚徒困境嫌疑人B承认不承认嫌疑人A承认（8，8）（0，10）不承认
11、（10,0）（1，1）在这个模型中，局中人N嫌疑犯A，嫌疑犯B，我们把他们简记为A和B。那么他们的策略集S也可以表示为SA承认，不承认，SB承认，不承认。那么相对应的收益向量也可以表示如下UA（承认，承认），UA（承认，不承认），UA（不承认，承认），UA（不承认，不承认）；UB（承认，承认），UB（承认，不承认），UB（不承认，承认），UB（不承认，不承认）。现在我们站在的立场考虑一下的最大偏好肯定是UA（承认，不承认），这时能使6自己无罪释放，可是这必须建立在B选择不承认的基础上。这样想的同时B肯定也这样想，由于两人不能沟通，也即不知道对方是承认还是不承认，只是都希望对方不承认，自己承认，
12、这样的话自己的利益就能最大化。正因为如此，自己不能选择不承认，这样就可能“便宜”了对方。所以A只能选择UA（承认，承认）。同样的道理，B的话也是一样，选择承认。232扩展式所谓的扩展式就是把博弈的过程画成图形，我们有时称博弈树或博弈图7。拿上述囚徒困境的例子，那么它的扩展式就应该如下在扩展式中重要的是博弈的先后顺序，因此，我们可以看出囚徒困境的模型有两种扩展式，但由于两人都是在不知道对方选择的情况下作出决策的，所以两种方法都正确的。233联盟式（特征函数式）投票博弈一个董事会由四名董事组成董事长、副董事和两名董事。在董事会进行会议表决时，董事长有3票，副董事有2票，两名董事各有1票。4个人分别
13、投票，并且规定赞成票超过半数时就表示该议题通过。那么他们每个人的权势有多大很明显，这是一个合作博弈。在这个博弈中，4名董事组成了一个董事会，即有外生的合作。局中人仍记作N，局中人集合N的任意一个子集S，即NS，称为该博弈中的一个联盟，若SN，则称为一个大联盟。特征函数指对任何一个联盟S对应一个实数S，同时要求V（）0，且NVIVNI18。我们规定议题通过记为1，未通过记为0，第I个局中人所拥有的票数为QI，则特征函数为7SIISIIQQSV4,14,0，不同的联盟S具有不同的特征函数值。其中V（）V（1）V（2）V（3）V（4）0,V（2,3）V（2,4）V（3,4）0。而V（1,2）V（1,
14、3）V（1,4）1,V（1,2，3）V（1,2，4）V（1,3，4）V（2,3，4）V（1,2，3,4）1。如果每个局中人所拥有的票数变化，或者投票规则发生了变化（达到2/3才能通过），那么特征函数也发生变化了，博弈也变成了另一个博弈。24博弈类型241完全信息静态博弈完全信息静态博弈是博弈论的基础，其两个关键特征是静态及完全信息。其中静态是指参与人同时选择行动，或实际上等效于同时选择。例如我们常见的猜拳游戏，在出拳前都同时在考虑自己该出什么，剪刀、石头或者是布。如果其中有一人比较了解另一个人出拳的习惯，像常出剪刀之类的信息，这样就不等效于同时行动了，因为前者有了可以利用的信息。总之，静态是指
15、没有其他参与人选择了什么的信息可以利用的情况。完全信息是指自然不首先行动或者自然的初始行动能被所有的参与人准确观察到的情况，即博弈模型没有事先规定的不确定性。例如，两家企业在市场上进行竞争，可以把市场需求的状况作为自然的选择。这时，完全信息的要求就是两家企业都知道市场需求是什么，如果只有一家知道的话就不是完全信息。总之，完全信息就是博弈过程中没有来自外界不确定性，也即博弈结构中没有不确定的东西。纳什均衡我们建立博弈模型的最主要的目的无非是要预测博弈的最终结局。经济学中的均衡理论指出，当一个系统处于平衡状态时，系统中的各个参与者都不会主动采取行动偏离这个状态。因为当其他的参与者不采取行动时，任何
16、偏离平衡状态只会给自己带来损失。所以，任何参与人单方面偏离均衡不会带来收益的增加是理性人自觉遵守选择的必须条件,这是纳什均衡的最重要特征。定义在战略式UUUSSSNNG,2121表示的博弈中，战略组合8,21SSSSN是一个纳什均衡，是指对任意I，S满足一下条件,MAXSSUSSUIIIIIISSII，或,SSUSSUIIIIII其中I1,2,，N9从纳什均衡的定义中我们可以发现实际上它给出了一个战略组合是否为纳什均衡的检验条件。要判断是否为纳什均衡只要其中一个参与人存在一个更好的策略就意味着该战略组合不是纳什均衡。同时，纳什均衡一般研究的是两人博弈的情况，当参与人较多时，通过逐个检验来证实或
17、寻找纳什均衡的工作量就明显太大了。242完全信息动态博弈完全信息是指自然不首先行动或自然的初始行动没有不确定性，并且自然的确定选择是参与人的公共知识10。这一点和完全信息静态博弈中一样。而动态博弈是指参与人行动有先后顺序的博弈。最简单的情况是两个人博弈，一人先行动，另一人后行动且参与人只有一次行动。有时候博弈也会出现交叉顺序行动的情况，如众所周知的象棋，它就是一个动态博弈。对动态博弈来说，分析的重要任务仍然是求出相应的均衡。虽说是动态博弈，但我们知道扩展式可以转换为标准式，然后就可以用策略式来求出该模型的均衡。子博弈动态博弈中博弈树的一个子树其实就是一个子博弈11。它的起点是某个人选择的结点。
18、包括这个结点及所有后续结点及枝及终结点之后的收益，这些就构成了一个子博弈树，也就代表着一个子博弈。子博弈中分析最重要的一点是确定这个子博弈的起点和初始信息。这一点是很重要的。243不完全信息静态博弈不完全信息博弈中的不完全信息具有特定含义，它专指在一种博弈局势中，局中人对其他局中人与该种博弈局势有关的事前信息了解不充分，而不是博弈中产生的与局中人实际策略选择有关的信息。这种事前信息是指关于博弈开始前局中人所处地位或状态的信息，当然这种地位与状态对博弈的局势和结果会产生影响。这种博弈中的不完全信息有多种形式，我们只是把它们统归为一种不完全信息。244不完全信息动态博弈在动态博弈中，有一种信息也得
19、说下。因为动态博弈中有先后顺序，当你作为猜的一方，你很可能会注意观察对方的行动细节，并指望从观察中获得有用的信息。这样的话就存在极端的情况（结果你看到了），这就是完美信息了12。不完全信息动态博弈的描述仍然可以用博弈树的方法，然而由于不完全信息的特征，博弈树也9将需要引入能够反映不完全信息的要素。3博弈应用31谁是胆小鬼在电视和电影中我们常可以看到这样一种场景两个人用开车比胆量，两车相向的加速，看谁胆小先转车头。让我们来分析下。谁是胆小鬼B不转开转开A不转开（10，10）（5，5）转开（5,5）（0,0）首先这是一个明显的二人博弈。在上图我们可以发现该博弈有两个纳什均衡，即一车转开，另一车直行
20、。由于没有足够的信息所以我们无法确定哪一种均衡会发生，还有就是双方都选择转开，那双方的收益都为0。因此这又是一个零和博弈。看到这个情形我们不免想到20世纪5080年代美苏关系紧张期间，当时两国正在进行核冷战，局面与胆小鬼博弈很相似。如果双方都选择发射导弹，且没有控制导弹的能力，将导致“两败俱伤”，如果导弹发射后有控制的能力，那就变成上述的这个博弈了。32停车场的修建问题我国目前停车场的建设远不如购车的速度，因为目前停车场的利润普遍不高，难以吸引投资商的兴趣。如果只靠政府建设的话，难以满足大众的需求，也怕形成停车者的“搭便车”。所以最好的办法是引进社会资金，也就是吸引投资商，作为一个新兴的产业要
21、得到发展当然少不了政府的扶持。那么双方该如何呢收益矩阵政府扶持不扶持投资商投资（1,1）（1,1）不投资（0，2）（0，1）双方效益分析1、政府给予政策扶持，同时投资商愿意出资建设政府成功的引进社会资金解决了社会停车问题、改善了道路拥挤，实现了交通的便利和社会效益的提高。而投资商在得到政府的扶持后，比路边停车更有优势，因此双方收益都是正的。2、政府不给予政策扶持，而投资商愿意出资建设很明显，这种情况下投资商的利润较低，比路边停车相差较大。投资商的收益是负的。当然政府的收益是正的。3、政府给予政策扶持，而投资商不愿意出资建设政府付出但没有成功地引进社会资金，社会停车10问题得不到解决，停车者的需
22、求得不到满足，效益是负的。4、政府不给予政策扶持，同时投资商不愿意出资建设政府没有得到社会资金来提供更多的停车场，问题没有解决，政府的效益是负的。因此，此时的纳什均衡组合是第一种情况1,1和第四种情况0,1。然而，最优的战略选择组合应该是第一种情况，即政府给予政策扶持，投资商愿意出资进入停车市场，这时双方达到了双赢。33空城计三国演义想必大家都看过了，其中有一回就是诸葛亮摆空城吓走司马懿，司马懿面对诸葛亮的一座空城，在城前不知如何是好是攻是退。思索之后最终决定退兵。我们可以建立模型简化成下图，分析下当时仲达面对注图中数字为模型假设出来的，正负代表双方的收益。模型分析首先这是一个动态博弈，且是个
23、不完全信息的博弈。在结果中可以看出，无论是不是空城，退兵对自己来说是最好的，双方的收益都是零。而在不了解对方部署的情况下进攻的话多少是有风险的。正所谓兵法云知己知彼，百战百胜。34诺曼底登陆历史背景不用多说了，我们把问题简单化，设我方两个师，敌方三个师，且都只能整师调动有两条进攻路线。我方兵力超过敌方时则我方胜，当我方兵力等于或小于敌方兵力时则我方败。那么双方该如何部署呢从上可以明显地看出敌我的方案敌方方案A三个师驻守甲方向；B三个师驻守乙方向；C一个师驻守甲方向，两个师驻守乙方向；D两个师驻守甲方向，一个师驻守乙方向。我方方案A两个师从甲方向进攻；B两个师从乙方向进攻；C兵分两路，每路各一个
24、师进攻。假如我方胜用“1”表示，用“0”表示败，那么得益矩阵如下得益矩阵敌方ABCD11我方A0,11,00,11,0B1,00,11,00,1C1,01,00,10,1我们先分析敌方的策略，很明显，A方案不如C方案，B方案不如D方案。所以敌方是不会选择这两个方案的，于是我们剔除A、B这两个方案，得到以下对策矩阵。得益矩阵敌方CD我方A0,11,0B1,00,1C0,10,1接着再分析我方的策略，同理可以看出，C方案比A、B方案都要差，所以把C方案剔除，那么就得出新的对策矩阵。得益矩阵敌方CD我方A0,11,0B1,00,1最后我们得出此次博弈的均衡敌方不会把所有兵力都驻守在一个方向，我方也不
25、可能同时兵分两路进攻，在两个进攻方向上，如果碰到敌方薄弱之处则我取胜，否则我方失败。用此可见，在博弈的过程中，信息是非常重要的。4小结本文就博弈论涉及的基础知识做了简单的介绍，采取的例子也是些平常所见到或者是为大家所了解的，通俗易懂，这样就容易加深对博弈的理解，同时可以引起更多人的兴趣来研究它。因为博弈论是源于数学的，所以在学习博弈的过程中提高了自己对数学的兴趣，同时可以从另一方面比较理性的来看待一些问题，包括经济上，军事上等。这样的话，对自身的思维方式还是有个很好的锻炼的。总之，在社会日益发展的今天，学习博弈论对个人来说还是有用的。参考文献1张问探讨博弈论及其在企业管理及商战中的应用J绿色质
26、量与管理，2010，0141432孙广毅博弈论原理在社会有关领域中的应用J经济师,2007,113738123汪贤裕，肖玉明博弈论及其应用M北京科学出版社，20084吴广谋，吕周洋博弈论基础及其应用M南京东南大学出版社，20105范如国，韩明春博弈论M武汉武汉大学出版社，20066ROGERAMCCAINGAMETHEORYANONTECHNICALINTRODUCETOTHEANALYSISOFSTRATEGYMADIVISIONOFTHOMSONLEARNING20047姚国庆博弈论M北京高等教育出版社，20078孙康，曲晓飞，孙肃合作博弈与竞争博弈性质及应用J大连理工大学学报，2005，45（6）9179199胡运权运筹学基础及其应用M北京高等教育出版社，200932134710李光久博弈论基础要点注释与题解精编M镇江江苏大学出版社，200811李凌，王翔论博弈论中的策略思维上海经济研究J2010,01354112MARTINJOSBORNEANINTRODUCTIONTOGAMETHEORYMOXFORDUNIVERSITYPRESS2004
