专栏首页绿巨人专栏读书笔记: 博弈论导论 - 07 - 完整信息的动态博弈 预备知识

读书笔记: 博弈论导论 - 07 - 完整信息的动态博弈 预备知识

读书笔记: 博弈论导论 - 07 - 完整信息的动态博弈 预备知识

完整信息的动态博弈 预备知识

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

动态博弈(Dynamic Games)

静态博弈是每个玩家同时(并且在不知道其他玩家选择的情况下)做出选择。 动态博弈引进了玩家做出选择的先后次序。 注意:玩家i做出了选择后,玩家j知道玩家i做出了选择,但是不一定知道玩家i做出了什么选择。

扩展形式博弈(The Extensive-Form Game)

扩展形式博弈的表达结构:

  1. Set of player, N.
  2. Players payoff as a function of outcomes, \{ v( \cdot ) \}_{i \in N}
  3. Order of moves.
  4. Actions of players when they can move.
  5. The knowledge that players have when they can move.
  6. Probability distributions over exogenous events. "exogenous"是指预先确定的分布概率自然选择(不依赖于玩家的选择)
  7. The structure of the extension-form game represented by 1-6 is common knowledge among all the players.

博弈树(game tree)

  • 博弈树 博弈树用来表示扩展形式博弈。 一个博弈树是一个带先后关系x > x'的节点集合x \in X x > x'表示x在x'之前。 每个节点只有一个父。 先后关系(precedence relation)具有: 传递性(transitive): x > x', x' > x'' \implies x > x'' 不对称性(asymmetric): x > x' \implies \ not \ x' > x 不完整性(incomplete): 不是每一对x, y有先后次序。 有一个根节点,标记为x_0,是其它所有节点的祖先。 没有子的节点称为末端节点(terminal nodes),表示为Z \subset X 末端节点表示为结果,并关联收益函数。 非末端节点被赋予1)一个玩家\i(x),和行动集合A_i(x),或者2)自然(Nature)。
  • 信息集合列表(the collection of information set of player i) 玩家i的信息集合(information set)列表,每个信息集合h_i \in H_i博弈树中的玩家i运行的部分节点,具有以下属性:
  1. 如果h_i = \{ x \}是一个单例集合,则运行x的玩家i知道他位于x节点上。
  2. 如果h_i = \{ x, x', \cdots \},则运行x的玩家i不知道他位于x节点上还是位于x'节点上。
  3. 如果h_i = \{ x, x', \cdots \},则A_i(x') = A_i(x)\

更多的解释,这是为完美信息的定义打铺垫。 如果玩家i的信息集列表都是h_i = \{ x \},则表明玩家i知道:1) 行动次序, 2)对方的行动是什么。 如果玩家i的信息集列表存在是h_i = \{ x, x', \cdots \},则表明玩家i知道:1) 行动次序。但是不知道: 1)对方的行动是什么。 这是导致玩家i: 1)性质2:不决定位于博弈树上的那个节点,因此,性质3:A_i(x') = A_i(x)也必然成立。

  • 完美信息博弈 一个完整信息博弈中,每个玩家i的每个信息集都是单例集合,并且没有自然(Nature)选择,则这个博弈是完美信息博弈。
  • 不完美信息博弈 一个完整信息博弈中,存在一些信息集不是单例集合,或者有自然(Nature)选择,则这个博弈是完美信息博弈。

可以将自然选择理解为掷骰子、抽签、盲牌。

  • 扩展形式博弈的纯策略 玩家i的一个纯策略是一个完整计划,描述了在每一个信息集合上,玩家i会选择哪个纯行动。
  • 扩展形式博弈的纯策略 玩家i的一个纯策略是影射: s_i: H_i \to A_I,对于每个信息集h_i \in H_i,有s_i(h_i) \in A_i(h_i)
  • (A_i(h_i)表示玩家i的一个信息集对应的行动集合。
  • 扩展形式博弈的策略数 |S_i| = m_1 \times m_2 \times \cdots \times m_k \\ where \\ |S_i| \text{ : the number of elements in } S_i \\ m_j \text{ : the number of actions in the j-nd information set} \\ k \text{ : the number of information sets}
  • 混合策略(mixed strategy) 一个混合策略是一个在各个纯策略上的概率分布。
  • 行为策略(behavioral strategy) 一个行为策略:对每一个信息集h_i \in H_i,有一个在各个行动a_i(h_i) \in A_i(h_i)上的概率分布,表示为 \sigma_i : H_i \to \Delta A_i(h_i) \sigma_i(a_i(h_i)): 玩家i,在信息集h_i上,选择行动a_i(h_i) \in A_i(h_i)的概率。
  • 纯策略 vs 混合策略 vs 行为策略 纯策略使用一个行动作为策略结果。 混合策略在玩游戏前是一个行为的概率分布,最终还是使用了一个纯策略。 行为策略在玩游戏前和玩的时候,都是一个行为的概率分布。
  • 完美回忆博弈(a game of perface recall) 在完美回忆博弈中,每个玩家都不会忘记之前知道的信息集。
  • 均衡路径(the equilibrium path) 在一个扩展形式博弈中,行为策略的纳什均衡\sigma^* = (\sigma_1^*, \cdots, \sigma_n^*) 如果一个信息集有可能到达这个纳什均衡\sigma^*,则称这个信息集在均衡路径上。 如果一个信息集不可能到达这个纳什均衡\sigma^*,则称这个信息集不在均衡路径上。

参照

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 教程 | 从零开始:TensorFlow机器学习模型快速部署指南

    机器之心
  • 资源 | NIPS 2017 Spotlight论文Bayesian GAN的TensorFlow实现

    机器之心
  • 一次搞定多种语言:Facebook展示全新多语言嵌入系统

    机器之心
  • 业界 | 滴滴成立AI Labs:由副总裁叶杰平教授领导

    机器之心
  • ICLR 2018 | CMU提出新型智能体定位方法:「主动神经定位器」

    机器之心
  • PyTorch一周年战绩总结:是否比TensorFlow来势凶猛?

    机器之心
  • 业界 | 从服务内部到实现商业化,美团云所经历的这两年

    机器之心
  • 机器之心最干的文章:机器学习中的矩阵、向量求导

    机器之心
  • AAAI 2018 | 腾讯AI Lab参与提出EAD:基于弹性网络正则化的深度神经网络对抗样本攻击

    机器之心
  • 业界 | 追一科技完成B轮2060万美元融资,创新工场领投

    机器之心

扫码关注云+社区

领取腾讯云代金券