读书笔记: 博弈论导论

摘要:
博弈论博弈论是对智能理性决策者合作与冲突的数学模型的研究。博弈论的目的可以说是研究寻找博弈均衡的方法。博弈论的直接目标不是找到一个玩家的最佳策略,而是找到所有玩家最合理的策略组合。博弈论的另一个作用是机制设计,根据预期结果设计博弈系统。这是博弈论的中心。声誉在博弈论中,为了证明自己的信誉,玩家会选择一种行为,这种行为只会让自己的类型受益,但会给其他类型造成损失。用于多阶段游戏。
读书笔记: 博弈论导论 - 总结

总结

本文是Game Theory An Introduction (by Steven Tadelis) 的学习笔记的总结。

博弈论

博弈论是关于智能理性决策者的协作和冲突的数学模型的研究。

博弈论的目的可以说是研究寻找博弈均衡的方法。
博弈论的直接目标不是找到一个玩家的最佳策略,而是找到所有玩家的最理性策略组合。
我们称最理性策略组合均衡

博弈论(也叫逆向博弈论)的另外一个作用是机制设计,根据期望的结果,设计一个博弈体系。

博弈论的分类

这本书中将博弈论的只是分为四类:

  • 完整信息的静态博弈
  • 完整信息的动态博弈
  • 不完整信息的静态博弈
  • 不完整信息的动态博弈

博弈论的数学模型

  • 普通形式博弈(normal-form game)的数学表达

    1. 一个有限的玩家集合, (N = {1, 2, cdots, n})
    2. 每个玩家的纯策略集合的组合, ({S_1, S_2, cdots, S_n})
    3. 一套收益函数, ({v_1, v_2, cdots, v_n}),对于每个玩家,每一种所有玩家选择的策略组合,都有一个收益值。
      $v_i: S_1 imes S_2 imes cdots imes S_n ext{ for each } i in N $
  • 贝叶斯博弈(Bayesian Game)
    用于描述不完整信息博弈。

[left langle N, { A_i }_{i=1}^n, { Theta_i }_{i=1}^n, { v_i(cdot; heta_i), heta_i in Theta_i }_{i=1}^n, { phi_i }_{i=1}^n ight angle \ where \ N = { 1,2,cdots, n} ext{ : is the set of players} \ A_i ext{ : the action set of player i} \ Theta_i ext{ : the type space of player i} \ v_i : A imes Theta_i o mathbb{R} ext{ : type dependent pay of function of player i} \ phi ext{ : the belief of player i with respect to the uncertainty over the other players' types} \ phi( heta_{-i} | heta_i) ext{ : the posterior conditional distribution on } heta_{-i} ]

术语

  • 静态博弈(static game) vs 动态博弈(dynamic game)
    静态博弈指所有玩家同时、独立做出选择。也叫做同时博弈(Simultaneous game)
    动态博弈指所有玩家按照次序做出选择。也叫做序贯博弈(Sequential game)、序列博弈。

  • 完整信息博弈(Complete information game) and 不完整信息博弈(Incomplete information game)
    完整信息博弈是指所有知识被所有玩家都了解,就是成为了公共知识。
    不完整信息博弈是指一个玩家不知道其他玩家的部分信息(actions, outcomes, payoffs)。

  • 完美信息博弈(Information perfect game) vs 不完美信息博弈(Information imperfect game)
    完美信息博弈指一个玩家知道对手做出了选择,并且知道对手的选择是什么。比如:围棋。
    不完美信息博弈指一个玩家知道对手做出了选择,但是不知道对手的选择是什么。比如:德州扑克。

  • 普通形式博弈(Normal-Form Game) vs 扩展形式博弈(Extensive-Form Game)
    博弈的数学化定义方式。
    普通形式博弈比较简单,适用描述信息较少的情况,比如:两个玩家的纯策略的静态博弈。
    扩展形式博弈用于形式化描述博弈。无论完美信息还是不完美信息,完整信息还是不完整信息都可以。
    针对不完美信息,支持信息集的概念。
    针对不完整信息,支持Nature和类型概念。

  • Subgame-perfect equilibrium
    这里主要说perfect这个词,这个词和equilibrium用在一起时,常常有精炼(refinement)的意思,表示优化均衡的结果。

  • 序贯(sequential)
    序贯表示连续的。

  • 信念(beliefs),
    玩家i的一个信念就是他的对手们的一个可能的策略组合。

  • 最佳反应(Best Response)
    当其他玩家策略已知时,玩家i的优势策略就是其最佳反应。
    这是博弈论的中心。理性,序贯理性的意味就是最佳反应。均衡的结果也来自于最佳反应。
    最佳反应:对于玩家i,给定其对其他玩家的信念,他会选择在这个信念上对自己最好的行为。

  • 序贯理性(Sequential Rationality)
    在博弈中的每个阶段,玩家都保持理性。

  • 信任系统(a system of beliefs)
    对每个信息集上一个行动的选择概率。见后面的数学定义。

  • 信誉(Reputation)
    在博弈论中,玩家为了证明自己的信誉(自己的类型),会选择一种行为,这种行为只会对自己的类型有益,而对其它类型有损失。

经典博弈问题

  • 囚徒困境(Prisoner's Dilemma)
    两个囚徒选择沉默(mum)和告密(flink)的一个静态博弈问题。
玩家2
mf
玩家1M4, 4-1, 5
F5, -11, 1
  • 报复博弈(Revenge Game)
    报复博弈一般和囚徒困境组成一个两阶段博弈。
    两个囚徒在玩完囚徒困境后,进入报复博弈,选择单独人(loner)和加入帮派(gang)的一个静态博弈问题。
玩家2
lg
玩家1L0, 0-4, -1
G-1, -41, 1
  • 古诺双寡头(The Cournot Duopoly)
  • (p-Beauty Contest)
  • 两性之争(the Battle of the Sexes)

策略

一个策略是一个玩家在博弈中,根据当时的情况,选择其行动的逻辑。
策略有各种各样的。我们可以想象每个策略都是如果这样,我就选择行动X,等等。
博弈理论中定义了一些策略。

  • 纯策略(Pure Strategy)
    玩家总是选择一个特定的行动。

  • 混合策略(Mixed Strategy)
    玩家在选择行动上有一个可能性分布。但是最终会选择一个纯策略。

  • 行为策略(Behavioral Strategy)
    玩家在选择行动上有一个可能性分布。一般用于动态博弈的自然选择,所以总是使用这个可能性分布来计算(期望收益等)。

    正式的说法是:对每个信息集指定一个行动上的独立可能性分布。

  • 条件选择策略(Conditional Play)
    如果怎样,我会怎样的策略。

  • 奖罚策略(Reward-and-punishment Strategy)
    好行为被奖励,坏行为被惩罚的策略。用于多阶段博弈。

  • 残忍触发策略(Grim-trigger strategy)
    在第一阶段上选择一个合作(符合子博弈精炼均衡)的行动;
    在以后的阶段里,继续选择这个合作行动,当且仅当对方也一直选择合作的行动;否则选择惩罚性的行动。

  • 使用第三方作为信誉机制(Third-Party Institutions as Reputation Mechanisms)
    在多阶段博弈中,如何保证协作的一种机制。
    玩家1:如果玩家2支付保证金给玩家3(第三方),则信任玩家2,否则不信任。
    玩家2:在阶段1,支付保证金给玩家3。在以后的阶段中,如果玩家3一直遵守保证金协议,则继续支付保证金。
    如果支付保证金了,则于玩家1合作,否则叛变。
    玩家3:(保证金协议)在一个阶段中,如果玩家2合作,则返回保证金给玩家2;否则不返回保证金。

  • 不使用第三方的信誉机制(Reputation Transfers without Third Parties)
    在多阶段博弈中,如何保证协作的一种机制。
    玩家(P_1^1):如果玩家(P_2^1)创建了一个唯一的商标,则信任玩家(P_2^1),否则不信任。
    玩家(P_2^1):在阶段1,选择一个唯一的商标,和玩家1合作。然后,把商标以价格(p^* > 1)卖给下家(玩家(P_2^2))。
    玩家(P_1^t(t>1)):如果1) 玩家(P_2^t)从玩家(P_2^{t-1})手里买了这个唯一的商标,2) 而且这个商标没有被滥用(叛变)过,则信任玩家(P_2^t),否则不信任。
    玩家(P_2^t(t>1)):如果1) 玩家(P_2^{t-1})从玩家(P_2^{t-2})以价格(p^*)手里买了这个唯一的商标,2) 而且这个商标没有被滥用(叛变)过,和玩家(P_1^t(t>1))合作。然后,把商标以价格(p^*)卖给下家(玩家(P_2^{t+1}))。

方法

  • 严格劣势策略(strictly dominated strategy)
    一个理性玩家不会选择一个严格劣势策略。

  • 优势策略(Dominant Strategy)
    如果有的话,玩家一定会选择优势策略。

  • 帕累托优势(pareto dominate)

  • 重复剔除严格劣势均衡(Iterated elimination of strictly dominated strategies (IESDS))
    如果能够找到一个严格劣势策略,将其删除掉,简化了博弈;
    然后在简化的博弈中,重复上面的过程,直到有一个优势策略为止。

  • 纳什均衡(Nash equilibrium)
    纳什均衡的定义是:在一个策略组合中,如果一个玩家i,当其他所有玩家的策略都不变时(是这个策略组合中的玩家策略),玩家i的策略是个最佳反应。
    如果这个条件对每个玩家都成立,则这个策略组合是一个纳什均衡。
    纳什均衡的概念可以从纯策略组合,推广到混合策略(期望收益)、(动态博弈的)行为策略、(不完整信息)贝叶斯纳什均衡。

纳什证明了每个博弈都至少有一个纳什均衡。

纳什均衡相当于在博弈论中发现了一个新大陆。
一个问题是纳什均衡的解往往很多,因此,有一个精炼的概念,就是我们常常看到词perfect,其目的是近一步减少纳什均衡的解。

  • 子博弈精炼(Subgame perfection)
    子博弈精炼是对纳什博弈的一种优化。
    要求对于一个行为策略组合(sigma^*),满足在任何一个合适的子博弈中,这个行为策略组合(sigma^*)都是一个纳什均衡。

  • 逆向归纳法(Backward induction solution)
    在扩展形式博弈树中,可以形象的看出:
    从底层开始,玩家在每个父节点的子节点集合中,选择出(最佳反应的)其会获得最大收益的行为。每个父节点会对应一个或者几个最佳反应节点。
    将这些节点的收益值作为其父节点的收益值。
    重复迭代可以找到所有玩家的一个子博弈精炼均衡。

  • 贝叶斯纳什均衡(Bayesian Nash equilibrium)
    可以说是纳什均衡在不完整信息博弈中的扩展。大概的意思是计算了其他玩家类型的分布概率上的收益期望。
    注意:子博弈精炼不适用于不完整信息博弈,主要原因是不知道其他玩家的类型,导致在子博弈上难以确定收益。

  • 精炼贝叶斯均衡(perfect Bayesian equilibrium)
    在不完整信息博弈中,精炼贝叶斯均衡是一个贝叶斯纳什均衡和一个信任系统的组合,并需要满足下面四个需求:
    精炼贝叶斯均衡(perfect Bayesian equilibrium)的四个需求:

    • 需求 15.1
      每个玩家在每个信息集上,都将有一个意义明确的信念(关于他的位置)。也就是说博弈将有一个信念体系。
    • 需求 15.2
      (sigma^* = (sigma_1^*, cdots, sigma_n^*))是一个不完整信息博弈的贝叶斯纳什均衡,我们要求在所有信息集上,在均衡路径上的信念符合贝叶斯规则。
    • 需求 15.3
      对于不在均衡路径上的信息集,其信念值可以是任何值。
    • 需求 15.4
      给定玩家的信念,玩家的策略必须是序贯理性。也就是说在每一个信息集上,玩家将选择信念对应的最佳反应。

原理

单阶段偏差原理(The One-Stage Deviation Principle)

在理解单阶段偏差原理之前,我们先回顾一些背景知识:

  • 每个博弈都存在至少一个纳什均衡。
  • 在有限多阶段博弈中,如果每个阶段博弈都有唯一的纳什均衡,则多阶段博弈的最优结果就是这些纳什均衡的组合(的路径)。
  • 在有限多阶段博弈中,如果至少有一个阶段博弈有多个的纳什均衡,则多阶段博弈的最优策略组合可能会偏离阶段博弈的纳什均衡。

那么在多阶段博弈中,在多阶段博弈的扩展形式博弈树(extensive-form game tree)上,一条路径的收益是容易得到的,只要求出每个阶段博弈的收益总和就可以了。
这样,我们也可以比较容易计算两条路径中,哪个更优(一般和折扣率有关)。

问题是:对于玩家i来说,当其他玩家的策略组合(sigma_i)给定的时,如何找到玩家i的最佳反应(best response)?
注:这里的策略可以是任何策略,比如纯策略,混合策略,条件策略等。
这里边,一个比较麻烦的问题是路径太多。比如:考虑一下一个有五个阶段的博弈。
幸运的是,上面这个骇人的问题可以被简化- 这就是单阶段偏差原理。

单阶段偏差原理的含义是,当其他玩家的策略组合(sigma_i)给定的时,判断玩家i的一条路径是否最优,只要看这个路径(策略)是不是单点不可改善(one-shot unimprovable)。
因此只要检测和它有一个信息集不同的那些路径就可以了。
比如:如果一个阶段博弈有A和B两个行动,在一个三阶段的重复博弈中,判断一条玩家的路径(策略)AAA是否是不可改善,只需要对比BAA,ABA和AAB就可以了。
很明显,这个原则只适合于有限多阶段博弈。

其实原书中,对于Prisoner-Revenge Game,计算折扣率,可以看成对单阶段偏差原理的过程描述,只不过只是比较两个路径。

下面加上书中的定义和定理,以供参考。
单阶段偏差原理表述如下:

一个阶段的不可改善策略必定是最优的。
这意味着,如果在一个阶段博弈中,存在一个单阶段不可改善策略,则不会发生偏离,也就是不存在非纳什均衡的最优策略。
反之,则一定会发生偏离的情况。

单阶段不可改善策略的定义如下:

一个策略(sigma_i)是单阶段不可改善的,则:
不存在信息集(h_i)和行动(a in A_i(h_i))和对应的策略(sigma_i^{a, h_i})(其为除了信息集(h_i)以外,和(sigma_i)都一致的策略),有(sigma_i^{a, h_i} > v_i(sigma_i, h_i))

参照见One-shot deviation principle

基本数学符合

(Gamma): 博弈(game)
(N): 玩家(player)集合
(i): 玩家i, (i in N)
(X): 结果(outcome)集合。
(X_i): 玩家i的结果(outcome)集合。
(x_i): 玩家i的一个结果(outcome)。

(S): 策略集合(strategy set), (S equiv S_1 imes S_2 imes cdots imes S_n).
(S_i): 玩家i的策略集合(strategy set)
(S_{-i}): 除去玩家i的策略集合(strategy set), (S_{-i} equiv S_1 imes S_2 imes cdots imes S_{i-1} imes S_{i+1} imes cdots imes S_n).
(s = (s_1, s_2, cdots, s_n)): 表示所有玩家的一个策略组合。
(s_i): 玩家i的一个策略(strategy),(s_i in S_i)
(s_{-i} = (s_1, s_2, cdots, s_{i-1}, s_{i+1}, cdots, s_n)): 表示除了玩家i,以外的所有玩家的一个策略组合。
(A_i): 玩家i的行动集合。
(a_i): 玩家i的一个行动,(a_i in A_i)
(mathbb{R})AAAAA: 实数。
(u_i: X o mathbb{R}): 玩家i的收益函数,基于一个结果组合。
(v_i: s o mathbb{R}): 玩家i的收益函数,基于一个策略组合。
(H_i): 玩家i的信息集的集合
(h_i): 玩家i的一个信息集,(h_i in H_i)
(A_i(h_i)): 玩家i的一个信息集(h_i)对应的行动集合。
(s_i(h_i)): 玩家i的一个纯策略。(s_i(h_i) in A_i(h_i))
(T): 多阶段博弈的所有时期。
(t): 多阶段博弈的一个时期。

(p(x_k | a)): 采取行动a时,产生结果(x_k)的概率。
(E(u(x) | a)): 采取行动a的期望收益。
(0 < delta < 1): (多阶段博弈中的)折扣率。

动态博弈(Dynamic Game)

策略组合(sigma = (sigma_1, cdots, sigma_n)): 一个动态博弈的混合策略组合(mixed strategies profile)。

不完整信息博弈

(Theta) : 所有玩家的类型空间(type space)集合。
(Theta_i = { heta_{i1}, cdots, heta_{ik}}) : 玩家i的类型空间(type space)。
( heta_i) : 玩家i的类型(type)。
( heta_{-i}) : 除了玩家i以外其他玩家的类型(type)。
(phi_i) : 玩家 i 对其他玩家 type 的信任分布概率。
(v_i(a; heta_i)) : 当在type ( heta_i)下,依赖于一个行动组合的玩家收益函数,

机制设计

(m_i in mathbb{R}) : 玩家i的资金。
(Y) : 所有玩家(机制设计的)结果组合集合。
(y = (x, m_1, cdots, m_n)) : 所有玩家(机制设计的)一个结果组合。
(Gamma = langle A_1, cdots, A_n, g(cdot) angle) : 一个机制。

不完整信息的动态博弈

(mu): 信任系统(a system of beliefs),对每个信息集上一个行动的选择概率。

[mu(x) in [0, 1] \ sum_{x in h} mu(x) = 1, forall h in H ]

参照

免责声明:文章转载自《读书笔记: 博弈论导论》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Django之POST GET与前后端交互装饰模式【大话设计模式Demo】下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

博弈论知识汇总

目录 巴什博弈 威佐夫博弈 尼姆博弈 尼姆博弈变形一 尼姆博弈变形二 反尼姆博弈 阶梯尼姆游戏 ( ext{ACM}) 中涉及的博弈一般为双人零和博弈。 巴什博弈 巴什博弈(Bash Game) 一堆 (n) 个物品,两人轮流从这堆物品中取物,规定每次至少取一个,最多取 (m) 个。最后取光者胜。 取胜法则 如果 (n=(m+1)r+s) ,(r)...

【笔记】博弈论DP基础——简单记忆化的二人博弈类型和sg函数的组合博弈类型

例题 A , B进行游戏。A先开始,轮流将n减去{2,3,4,5,6}中的一个数,谁最后无法进行减法了,就输了。给定n。A,B都采用最优策略,问A是否会赢。 状态 设f[i]表示当前的数是i的时候,对于当前的先手来说是否会赢f[i]=true,则赢f[i]=false,则输 转移 当先手A操作一次后,问题转移为了对于当前先手B,对(n-i)进行操作 必胜转...