博弈论与数学模型.pptx

主要内容 上篇：数学理论n 博弈论概说n 矩阵博弈n Nash均衡和Nash定理 下篇：数学模型n Hotelling模型n Cournot和Bertrand模型n 稳定婚姻问题博弈与博弈论 博弈论（game theory）：研究利益存在冲突的决策主体在相互依赖的条件下，如何选择适当的策略实施以获得最大利益。n 研究对象不是客观规律，而是带有主动性的人的活动。n 最优不是绝对的，而是现有主客观条件下的理想结果。博弈论的发展简史 古代文献中的朴素博弈论思想n 田忌赛马（中国，春秋时代）n Talmud中的债务分摊原则（以色列，公元6世n纪前）自二十世纪二十年代起，von Neumann，Zermelo，Borel等数学家相继给出了若干博弈论结论。n 1944年，von Neumann和Morgenstern著作Theory of Games and EconomicBehavior出版，这是博弈论正式形成的标志。nPrinceton Press，1944博弈论的发展简史n1950-1953年，Nash先后发表四篇论文，提出了Nash均衡，讨价还价等一系列重要概念。n二十世纪六七十年代起，经济学、社会学和生物学领域开始大量应用博弈论，并逐渐在经济学界取得重要地位。n 1994年，三位博弈论研究者Nash，Harsanyi，Selten获诺贝尔经济学奖，博弈论开始走入大众视野。博弈的要素n参与者（player）：参与博弈的决策主体。n行动（actions）：参与者可以采取的行动（策略）方案的全体；所有参与者采取各自的行动后形成的状态称为局势（outcome）。n收益（payoff）：各个参与者在不同局势下获得的利益。n规则（rule）：对参与者行动的先后顺序、参与者获知信息的多少等内容的具体规定。美苏冷战n参与者：美国，苏联n行动集 美国：强硬、妥协 苏联：强硬、妥协n局势 美国强硬、苏联强硬 两败俱伤、同归于尽 美国强硬、苏联妥协 美国得益、苏联受损 美国妥协、苏联强硬 苏联得益、美国受损 美国妥协、苏联妥协 互不侵犯、和平共处美苏冷战n收益：由于实际情况的复杂性，参与者的收益很n难精确量化，因此收益多表现为偏好或序关系。n美方偏好排序 苏方偏好排序n 负无穷 美国强硬苏联强硬 负无穷n 1 美国强硬苏联妥协 -1n -1 美国妥协苏联强硬 1n 0 美国妥协苏联妥协 0美苏冷战n研究博弈的重要内容之一是分析每个局势是否会出现、是否会稳定。n当参与者只有两个时，博弈可以用简洁的形式表示。美苏冷战n美国强硬、苏联妥协是稳定点n美国妥协、苏联强硬是稳定点美苏冷战n美国强硬、苏联强硬不会出现，美国妥协、苏联妥协不会出现n冷战时期，美苏在世界各地争夺霸权，曾多次出现紧张局势，但最后都以一方的妥协而告终，上述模型较好地解释了这一现象。非合作博弈的分类n根据参与者是否同时行动：静态博弈，动态博弈n根据参与者掌握信息的多少：完全信息博弈，不完全信息博弈对策论v.s.博弈论数学v.s.经济学n博弈论和数学建模矩阵博弈n 参与者为两人：甲、乙n 每人的可行策略集为有限集：n 两人收益之和为零，博弈可用一矩阵、即甲的收益矩阵A来表示，乙的收益矩阵为-A。n 极大极小原则鞍点矩阵博弈纯策略和混合策略n若参与者每次行动都选择某个确定的策略，我们称之为纯策略（pure strategy）。n若参与者行动时可以以一定的概率分布选择若干个不同的策略，这样的策略称为混合策略（mixed strategy）。n 在混合策略意义下，参与者的收益实质上表现为期望。矩阵博弈的混合策略n甲、乙的混合策略集分别为n设甲、乙采用的混合策略分别为，n甲的期望收益为Von Neumann定理线性规划历史回眸双矩阵博弈n零和的要求限制了矩阵博弈在经济学中的应用，也阻碍了非合作博弈向多人推广。n对两人非零和有限博弈，双方收益需用两个矩阵表示，称为双矩阵博弈（bimatrix game）。n1960年，Lemke和Howson给出了求解双矩阵博弈解的算法，但该算法是指数时间的。John Forbes NashNash 均衡n完全信息静态博弈的某个局势称为Nash 均衡（Nash equilibrium），若每一个理性的参与者都不会单独偏离它。即在其他参与者的策略不变情况下，单独采取其他策略，收益不会增加。n矩阵博弈的解即为Nash 均衡，因此Nash 均衡可视作矩阵博弈解的概念向非零和、无限策略集、多人博弈的推广。囚徒困境（Prisoners Dilemma)双人博弈Stag or Harenn个猎人相约去打猎，猎场中有鹿和兔两种动物，鹿的价值远大于兔的价值。每个猎人在打猎时只能专注于一种猎物，猎到某猎物后他即中止打猎。n一头鹿需要所有人协力才能捕获，一只兔只要单人努力即可捕获，所有人协力获得的猎物收益由所有人平分。n所有人捕鹿或所有人捕兔是两个Nash均衡。Nash 均衡的性质nNash 均衡是理性参与者在动态决策过程中可以预见的终极局势。nNash 均衡具有稳定性，一经形成后不用外力即可维持。nNash 均衡从整体而言未必是最优局势，也未必是每个参与者的最优选择。Braess悖论Braess悖论Shapley 网络设计问题n现有一由若干节点和线路组成的通讯网络，每个使用者可借此网络建立两点之间的通讯联系，为此需向网络所有商购买线路使用权。n每条线路价格不同。若多个使用者共同使用某线路，费用由这些使用者分摊。Shapley 网络设计问题Shapley 网络设计问题Nash均衡的数学定义最优反应函数不动点定理Nash 定理n（Nash 定理）设参与者数目有限，每位参与者策略集均有限，收益函数为实值函数，则博弈必存在混合策略意义下的Nash均衡。nNash 定理的证明只是一个存在性证明，并没有给出Nash均衡的求法。Nash均衡（或近似Nash均衡）的算法与复杂性问题是近年来理论计算机科学的关注热点。Hotelling 模型n现有两家快餐连锁店拟在一条街道上开设分店。n居民住宅在街道上均匀分布，每人都会选择距他住址较近的一家快餐店就餐（若距离相等则随机选择一家）。n两家连锁店应分别在何处选址才能吸引较多的顾客。nHarold Hotelling（1895-1973）美国数学家、经济学家、统计学家Hotelling 模型Hotelling 模型Hotelling 模型Hotelling 模型最优反应函数Nash均衡n(1/2,1/2)是Nash均衡，两家快餐店开在同一地点，平分所有的客源。n该模型可推广为居民住址服从任意连续分布的情形。若分布的中位数m为，则Nash均衡为（m,m）。三方竞争选举n候选人政纲和选民主张均可抽象为一实数。选举时选民投票给政纲距本人主张最接近的候选人。获得最多选民支持的候选人当选。n实行两党制的国家在竞选时两党的政纲区别不大，旨在争取中间选民。实行多党制的国家政党分分合合，政府更迭频繁。竞争上岗n每位选民都可以自荐为候选人，其政纲即为本人主张。n参选需要支付成本b，当选可获得收益c。若未当选或未参选另有损失d，d表示其主张与当选人政纲的距离。n Nash均衡为何？是否应该自荐为候选人？n（和b，c大小以及本人观点与m 距离有关）Cournot 双头垄断n两家垄断企业生产同一产品，生产单位产品的成本为常数C。n若市场上该产品供应量为Q，则产品销售价格为a-Q，其中a为一常数。n两家企业应如何选择各自的产量可使自身获益最大。nAntoine Augustin Cournot（18011877）法国数学家、经济学家、哲学家Cournot 双头垄断最优反应函数Nash均衡联合欺骗Bertrand双寡头垄断Bertrand双寡头垄断最优反应函数Nash均衡稳定婚姻问题稳定婚姻问题算法n“男士选择，女士决定”n每位男士都选择他最钟爱的女士。n如果有女士被两位或者以上的男士选择，则这几位男士中除了她最喜欢的之外，对其他男士都表示拒绝。n被拒绝的那些男士转而考虑他（们）的除被拒绝之外的最满意女士。如果存在冲突（包括和之前选择某女士的男士发生冲突），则再由相应的女士决定拒绝哪些男士。n以上过程持续进行，直至不再出现冲突为止。算法最优性n称一组稳定婚姻是男方最优的，如果在该组婚姻中，每位男士都认为其配偶不比任何一组稳定婚姻中他的配偶来的差。n男方最优的稳定婚姻是唯一的，同时必是女方最劣的。n“男士选择，女士决定”算法给出的总是一组“男方最优”的稳定婚姻。稳定婚姻问题的应用n稳定婚姻（stable marriage）及衍生问题在理论上具有重要的意义，在实践中发挥了巨大的作用。n申请式学校录取n用人单位与求职者双向选择n选择不同类型的算法可满足保护不同群体利益的要求。欺骗机制设计n是否存在一种机制（算法），能鼓励参与者真实表达意愿，即参与者不会因为虚假表达意愿而获益。n给定任何一稳定婚姻问题的算法，参与者都可以通过提供虚假偏好顺序而获得更好的一组稳定婚姻。n对给出男（女）方最优稳定婚姻的算法，男（女）方不可能通过提供虚假偏好顺序获得更好的一组稳定婚姻。谢谢