Aiur

zellux 的博客

Game Theory - Stanford

Permalink

课程链接:https://class.coursera.org/gametheory-2012-002/lecture/index

Week 1: Introduction and Overview

  • Nash Equilibrium: 已知其他参与者的行为后,每一位参与者的行为能最大化他/她的收益。

  • Best Response:$a_i^{*} \in BR(a_{-i}) \iff \forall a_i \in A_i, u_i(a_i^{*}, a_{-i}) \geq u_i(a_i, a_{-i})$

  • $a = <a_1, …, a_n>$ 是一个 pure strategy Nash equilibrium 当且仅当 $\forall i, a_i \in BR(a_{-i})$,注意这里用了 $\in$,因为 best response 可能有多个。

  • $s_i$ strictly dominates $s’_i$ $\iff \forall s_{-i} \in S_{-i}, u_i(s_i, s_{-i}) > u_i(s’_i, s_{-i})$

  • $s_i$ very weakly dominates $s’_i \iff \forall s_{-i} \in S_{-i}, u_i(s_i, s_{-i}) \geq u_i(s’_i, s_{-i})$

  • Best response 是针对已知其他参与者的行为而言的,而 dominating 则是无论其他人怎么做都最优的方案。

  • Best response 的条件是已知对手的行为后,该行为的收益不低于其他的行为,也就是说是可以和其他行为有相同收益的。这也意味着 Nash equilibrium 同样可以包含一些行为,这些行为和其他行为的收益一样。

Week 2: Mixed-Strategy Nash Equilibrium

  • Mixed strategy 的期望收益: $$u_i(s) = \sum_{a \in A}{u_i(a)Pr(a|s)}$$ $$Pr(a|s) = \prod_{j \in N}{s_j(a_j)}$$

  • 对于 mixed strategy,best response 和 Nash equilibrium 的定义和 pure strategy 的类似,只是把行为(a)改成了策略(s):

Best Response: $s_i^{*} \in BR(s_{-i}) \iff \forall s_i \in S_i, u_i(s_i^{*}, s_{-i}) \geq u_i(s_i, s_{-i})$

Nash equilibrium: $s = <s_1, …, s_n>$ 是一个 Nash equilibrium 当且仅当 $\forall i, s_i \in BR(s_{-i})$

注意这里的 $S_i$ 是个无限集合。

  • 每一个有限游戏都有一个 Nash equilibrium。

  • 关于 2.3 中 indifferent 问题我的理解:首先这里 indifferent 是指玩家 2 的决策必须让玩家 1 关于 B 和 F 的收益相同,如果不是这样,假设玩家 1 选择 B 的收益高一点,那么玩家 1 肯定就会选择 100% 选择 B 了,与假设(best response 且 mixed strategy)矛盾。

  • 寻找 Nash equilibrium 问题被证明是 PPAD-complete 的,PPAD 位于 P 和 NP 之间,即 P -> PPAD -> NP -> NPC。

    • 点球时如果守门员左右防守能力均衡,射手不擅长右脚(右脚有一定几率射出范围),为了获得最大期望他应该以更大的概率往右踢。一个反直觉的结论。而实际上,有人统计过 FIFA 1400 多场比赛中守门员和射手的表现,实际数据和 Nash equilibrium 得出的结论相当接近。

Week 3: Alternate Solution Concepts

  • 移除的策略必须是 strictly dominated,也就是说等号不能成立。但是策略可以被另外一个混合策略 strictly dominated。

  • Maxmin strategy:在最差条件的下获得最大收益的策略。与之相反,minmax 是在双人博弈中,让对手在最佳条件下获得最小收益的策略。在一个有限的双人零和博弈中,任何 nash equilibiurm 同时也是每个玩家的 minmax 和 maxmin 策略。

  • Correlated Equilibrium: 通过外界指定行为的建议,使得双方都愿意遵从这一约定(例如红绿灯)。

Week 4: Extensive-Form Games

  • pure strategy 的定义是所有可能会发生的情形下用户行为的描述。

  • subgame perfect equilibrium 是指博弈树中的每一个子树都是 Nash equilibrium。

  • 非 subgame perfect 的 Nash equilibrium 的问题在于,只有当玩家相信对方的确会这么做时,他才会采用相应的策略。

  • 把 extensive form 转成 normal form 后就没法恢复回来了,但是两者的策略和均衡都是一样。

  • behavioural strategy 和 mixed strategy 的不同点在于,前者是某种情形下选择不同行为的概率分布,而后者是对于整个博弈的概率分布,两者在 perfect recall 的前提下可以互相转换。

Week 5: Repeated Games

  • Discounted reward: 未来的收益的实际效果会逐渐减小 $\sum_{j=1}^{\infty}{\beta^{j}r_{j}}, (0 < \beta < 1)$

  • 如果 fictitious play 中每个玩家的策略概率分布都收敛于某一定值,那么这个收敛后的概率分布一定是一个 Nash equilibrium。

  • 以下任一条件都可以使得 fictitious play 的结果收敛:

    • zero sum game
    • 迭代去掉 strictly dominated strategies 后这个博弈有解
    • potential game
    • 2 x n game & generic payoffs
  • Regret: $R^t(s) = \alpha^t(s) - \alpha^t$ (slides 有误)

  • No-regret learning: $Pr(\lim_{t \rightarrow \infty}R^t(s) \le 0) = 1$

  • enforceable: 任何人的收益都不比最差情况下的收益差

  • feasible

  • Nash equilibrium => enforceable

  • enforceable + feasible => Nash equilibrium

Week 6: Coalitional Games

  • superadditive: $G = (N, v)$ is superadditive if $\forall S, T \subset N, S \cap T = \varnothing \Rightarrow v(S \cup T ) \geq v(S) + v(T)$

  • interchangeable: 对于所有不包括 i 或 j 的子集 S,$v(S \cup \{i\}) = v(S \cup \{j\})$,则 i 和 j 是 interchangeable 的。

  • dummy player: 对于所有不包括 i 的子集 S,$v(S \cup \{i\}) = v(S)$,则 i 是 dummy player。

  • Shapley value: 每个成员的收益都和他们的边际贡献成正比。它是唯一满足 interchangeable(相等)、dummy player(分配为零)和 superadditive(累加)的分法。

  • Shapley value 的问题在于忽略了稳定性,对于某些参与者而言组成更小的团队或许更有诱惑。

  • Core: payoff $x$ 在 core 中当且仅当 $\forall S \subset N, \sum_{i \in S}{x_i \geq v(S)}$。即对于任一子集,组成这个子集的玩家所能分配到的收益的总和,都不应该低于这个子集的收益。否则组成这个更小的集体就会变得更有吸引力。

  • Core 和 Nash equilibrium 很类似,只是 core 背叛的方式是通过组成小集体。

  • Simple game: 任一子集的收益要么是 0,要么是 1。

  • Veto player: 如果没有他,那么剩下的人组成的任一集体收益都是 0。

  • 对于 simple game,如果没有 veto player,那也就不会有 core;如果有 veto player,那么 core 里的分配方式必然是其他玩家都获得 0 的方式。

  • Convex game: $\forall S,T \subset N, v(S \cup T) \geq v(S) + v(T) - v(S \cap T)$。Convex 的条件比 superadditive 更严格。

  • 对于所有的 convex game,Shapley value 是属于 core 的。

Week 7: Bayesian Games

评论