首页 > 编程语言 > 详细

算法博弈论_2_策略式表述博弈

时间:2021-09-21 00:27:46      阅读:1      评论:0      收藏:0      [点我收藏+]

博弈的策略式表述方法

博弈的策略式表述

  1. 博弈参与人(Players)

    • \(N\)-参与人的集合
    • \(i\)-参与人
  2. 博弈参与人的策略集(Strategy sets)

    • \(S_i\)-参与人的策略集
    • \(s_i\)-参与人的策略集的一个元素
    • 所有参与人的策略放在一起,称之为博弈的策略组合,表示为\(s = (s_1, s_2, … s_n)\)
  3. 博弈参与人的支付函数

    • \(u_i\)-参与人\(i\)的支付函数\(i\isin N\)
      \(u_i(s_1, s_2, s_3,..., s_i,..., s_n)\)

囚徒困境和公地悲剧——个人与集体

囚徒困境

坦白 抵赖
坦白 -8,-8 0,-10
抵赖 -10,0 -1,-1

对于选择坦白,对面无论是坦白或者抵赖,选择坦白的结果均好于抵赖,可知,坦白属于占优策略

指在博弈中参与人的某一个策略,不管对方使用什么策略,只要参与人使用这一策略,都可以给自己带来最大的支付,此时称为占优策略

(-8,-8)称为占优策略均衡

囚徒困境揭示了这样一个个人利益和集体利益的关系:个人正确理性的选择往往会造成最坏的结局,降低集体的福利,而集体的最优则必然侵害个人利益的最大化。

公地悲剧

在没有监管的情况下,人们倾向于无节制地侵占共用资源以获得最大利益

占优策略和劣策略

占优策略:是指不论对手选择什么,自己的某个策略都不比其他策略差的策略。

如果自己的某个策略严格强于(收益大于)任何其他策略,那么该策略还被称为严格占优策略

占优均衡:如果每个参与人都存在占优策略,那么这些占优策略放在一起,构成了博弈的占优均衡。

劣策略:是指不论对手选择什么,自己都不会选择的策略。

对于劣策略。可以直接剔除以简化博弈,如果剔除到最后只留下唯一一个策略组合,那么这个策略组合就是我们说的重复剔除严格劣策略均衡。如果存在重复剔除严格劣策略均衡,那么我们说这个博弈是重复剔除劣策略可解的

理性共识

零阶理性共识:每个人都是理性的,但不知道其他人是否理性;

一阶理性共识:除了要求每个人都是理性的,还要求每个人都知道其他人是理性的

二阶理性共识:每个人是理性的,同时每个人知道其他人是理性的,并且每个人知道其他人知道自己是理性的;

最优反应

对于博弈的策略式表述\(G =(N, Si, ui)\),$ i \isin N$

对于参与人\(i\),给定其他参与人策略组合\(s_{-i}\),i关于的最优反应集是满足如下条件参与人\(i\)的策略集\(B_i(s_-i)=\{s_i \isin S_i |u_i(s_i,s_-i>=u_i(s_i‘,s_{-i}),for all s_i\}\)

最优反应是关于其他人策略的函数,只与其他人策略有关。

纳什均衡

对于博弈的策略式表述\(G=(N,S_i,u_i),i \isin N\)

对于任意的参与人\(i \isin N\),如存在一个策略组合\(s^*=(s_i^{*},s_{-i}^{*})\)满足

\[s_{i}^{*} \isin B_i(s_{-i}^{*}) \]

对于一个纳什均衡,所有人的策略都是其他人策略的最优反应

技术分享图片

待思考

纳什均衡强调的是个体最优,但对于整体、社会来说,则未必是好的。比如被大家责骂的过分应试教育;缺乏监管下的黑心食品生产商;缺乏监管的网购欺诈;囚徒困境和公地悲剧;过分竞争市场的恶性竞争等

囚徒困境的一般形式

合作 背叛
合作 R,R S,T
背叛 T,S P,P
  • 条件一:T>R>P>S
  • 条件2:R+R>T+S

对于1972年,Alchian & Demsets在《美国经济评论》上发表了《生产、信息成本和经济组织》一文,提出了解决方案:使其中人一成为所有者,另一人变成雇员,让前者监督后者。

对于所有者,偷懒是严格劣策略,所以所有者一定会选择工作。雇员选择工作为最优反应。

技术分享图片

连续策略中的二人合作

参与人1与参与人2合作一个项目,如果每个人都付出,双方都会获得合作收益。

二人的策略为选择努力水平a1和a2,努力水平的取值范围为闭区间[0, 4]。

对于参与人来说,如果双方的努力水平为a1和a2,他们的收益如下:

参与人1:\(u_1 = a_1(2+a_2-a_1)\)

参与人2: \(u_2=a_2(2+a_1-a_2)\)

假设第一个人努力为4,此时第二个人最优选择为3,当第二个人选择为3时,第一个人的最优反应为2.5.....,以此类推,最终当两个人的努力程度都为2时,达到一个纳什均衡,为(4,4)。

技术分享图片

然而,当两人都选择付出最大努力时两人的收益是(8,8),大于纳什均衡的最优值,这也体现了囚徒困境

算法博弈论_2_策略式表述博弈

原文:https://www.cnblogs.com/xiaoyunbowen/p/15312389.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!