> 博弈论简介 在上一篇文章中提到了计算广告内容众多，在这里将从机制设计开始谈起。所谓机制就是广告主与媒体方直接约定的一种规则，一种游戏的规则。广告产品在互联网公司里面往往属于商业部门，一般是公司的收益来源。商业涉及到经济，经济学相关原理是在计算广告，特别是机制设计的理论基础。 目前大部分在线广告是以拍卖的形式进行的，拍卖属于博弈论的范畴，博弈就是游戏，博弈论研究游戏的规则以及在规则下各方的反应和各个反应下产生的效果。博弈论为众多学科提供了分析的概念和方法：经济学和商学,政治科学,生物学, 心理学和哲学。博弈论与传统微观经济学相比较，两者在利益最大化和均衡原则上是一致的，微观经济学研究的市场更偏向于极端市场，即完全竞争市场或者垄断市场，这个市场的重要特点是市场的参与者决策不会影响到其他参与者的决策，这种情况下市场的运行主要通过『看不见的手』即供求关系调整并达到均衡。博弈论更加偏向研究在某种博弈规则下，博弈参与者之间的关系，研究博弈参与者之间的相互依存性和相互作用，就是研究博弈参与者根据策略地分析其他参与者可能的行为而做出理性的行为。 > 博弈分类与表示方法 博弈论研究参与者之间的相互关系，如果参与者之间是合作关系，那么称之为合作博弈，达成有约束力的协议（binding agreement），强调团体理性，强调效率、公正、公平。如果参与者之间不是合作关系，那么称之为非合作博弈，强调个人理性，其结果可能有效率，也可能无效率。 博弈的过程有动态和静态之分，静态博弈是参与者同时进行博弈或者可以看做同时选择策略的博弈，动态博弈是指参与者的选择和行动有先后顺序。按照参与者是否知道其他全部参与者的信息，又分为完全信息博弈和不完全信息博弈。 - 完全信息静态博弈：囚徒博弈，智猪博弈、夫妻博弈、懦夫博弈 - 完全信息动态博弈：海盗分金 - 不完全信息静态博弈：求爱 - 不完全信息动态博弈：黔之驴，李牧守关 对博弈论的建模方法（或者说表示方式）主要有两种：一种是策略型，一般用于分析静态博弈，常用表格的形式表示，包括博弈参与者的名单、博弈者参与者的策略集、博弈参与者的策略与其他参与者的策略组合时相对应的收益；另一种是展开型，一般用于分析动态博弈，常用博弈树的形式表示。当然，每一个展开型博弈可以表示成策略型，每一个策略型博弈至少有一种展开型表示。 > 完全信息静态博弈策略与结局 在博弈中，参与者的行动称之为策略，策略有好有坏，有优有劣。先引入两个概念： - 严格占优策略（强占优策略） 对于一个参与者来说，无论其他参与者采取什么策略，这个策略的回报都严格大于执行其他策略所得到的回报。 - 弱占优策 对于一个参与者来说，无论其他参与者采取什么策略，这个策略的回报不小于执行其他策略所得到的回报。 对于博弈模型来说，占优策略是博弈的结局，也就是博弈的一个解。当所有参与者都有占优策略时，博弈存在占优策略解。在许多博弈中并不存在占优策略解，特别地，只要一个参与者没有占优策略，博弈没有占优策略解。 - 累次剔除劣策略解 在许多博弈中，参与者不一定会有占优策略，除了搜寻占优策略，退而求其次，理性的人可能会去剔除不好的策略（劣策略），即无论别的参与者采取什么策略，剔除自己的策略集合中的劣策略（存在其他策略比该策略的回报大），获取策略子集，在子集上反复执行直到剩下最后一个解。在任何博弈中，如果能够求得这样唯一的累次剔除劣策略解，称之为IEDS解，称博弈是占优可解的。IEDS的解可能不唯一，强IEDS解是唯一的。这种解法的缺点是：存在占优可解的博弈，可能没有强IEDS解。 如果博弈中（N-1）个参与者有占优策略，那么该博弈必定有一个IEDS解。 - 纳什均衡解（策略） 纳什均衡是博弈的一种解（博弈可能还有占优解，IEDS解）。在给定其他参与者采取的策略时，该参与者回报最大的策略就是纳什均衡解，可以看出纳什均衡有两个条件，一个是对其他参与者采取的策略要猜测正确，另一个是每个参与者必须采用针对自己猜测的最优反应。纳什均衡是博弈论中最普遍的求解方法。 关于纳什均衡解有三个问题 （1）存在性：在一定的条件下的博弈，存在纳什均衡解【每个有限战略式博弈（参与人与战略数目均为有限）都有纳什均衡存在，这均衡有可能是混合战略均衡】 （2）唯一性：在一些博弈中纳什均衡解不唯一 （3）在多个纳什均衡解中，哪种均衡才是最合理的？ - 混合策略 之前讨论的都是纯策略，而混合策略是参与人在纯策略的基础上以一定概论进行的策略。一个混合策略可以优于最好的纯策略。存在没有纯策略纳什均衡的博弈，但是总存在混合策略的纳什均衡。 > 博弈三种解的关系 每一个占优策略解是一种IDES解，每一个IDES解是一种纳什均衡解，每一种纳什均衡解是一种混合策略均衡解，反之不成立。  > 对称博弈与对称均衡 对称博弈是参与人之间没有差异的博弈，每一个人都有相同的机会，相同的行动，并产生相同的收益，这就促成了对称均衡，每个参与者策略都相同的纳什均衡。 > 零和博弈 零和博弈是指两个博弈参与者，无论采用什么样的策略，他们的总盈利都是一个0（或者是一个常数） > 不同博弈类型对应的均衡 - 完全信息静态博弈：纳什均衡 - 完全信息动态博弈：子博弈完美纳什均衡 - 不完全信息静态博弈：贝叶斯纳什均衡 - 不完全信息动态博弈：完美贝叶斯纳什均衡以及序贯均衡  参考资料： 《策略与博弈——理论与实践》，杜塔