Game Theory - Stanford
课程链接：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 的。