博弈论（一）
在之前的讨论中，一场游戏只有一个智能体。而在博弈论中，智能体评估它们的决策如何与其他人的决策相互作用以产生不同的结果。
看一个具体的博弈游戏：
这是博弈问题最简单的一种： 两个玩家的零和有限确定性完美信息博弈 。
在 MDP 中有个名词叫 POLICIES （策略），它是状态到动作的映射。博弈论中有类似的概念，称为 STRATEGIES （策略），它是所有可能的状态到动作的映射。
对于 A 来说 (1→L, 4→L) 就是一个策略。不难看出，在这个特定的游戏中，A 有4个策略，B 有3个策略，如下：（这种策略被称为 纯策略 ）
我们可以以表格的形式写出这些策略，并在中间填入最后的得分。（由于B得分是A的相反数，所以这里省略B）
最终可以得到一个矩阵（红框部分），这个矩阵包含了此场博弈的一切信息，即：有了它我们不再需要一开始的博弈树了。
试想这样一个游戏过程：
A 总是最大化得到的分数，而 B 总是试图最小化 A 可以得到的分数。所以得出这样一个结论： A 先手时必须要考虑会遭遇 B 最严酷的反制策略 。所以选择 (L,L) 是非常不明智的。事实上若交换 AB 角色，结论是一样的。
在这个结论的指导下，A 要选择的并不是全局最大值，而是在 B 执行反制策略（找到极小值）后得到尽可能大的值。也就是：极大化极小值。相反，B 要找到极小化极大值。（因为值越小 B 得分越高）
所以正确的博弈过程是这样的：
从这个过程可以得出一个结论：极大化极小值和极小化极大值最终的结果是一样的。
极小极大原理也就是 Von neumann 定理 （冯诺依曼定理）。
前面所述简单博弈具有确定性，现在我们取消这一约束。看一个具体的游戏：
同样的，只需要用概率乘以得分再求和，也可以写出一个博弈矩阵：
前面所述博弈是完美信息，现在我们取消这一约束成为 两个玩家的零和有限隐藏信息博弈 。
看一个具体的游戏：
因为 B 不知道 A 抽到的是什么颜色，故不知道自己处在哪一状态，也就是隐藏信息。
同样的可以得到一个矩阵：
不难看出，在这场博弈中，Von neumann 定理不再有效了，它无法在不同情况下得出一个确定的结果。
混合策略与纯策略的区别就是， 需要指定选择不同策略的概率 。如此看，纯策略是特殊的混合策略，其选择某一策略的概率是100%.
令 A 选择留牌的概率是 p，那么当 B 选择弃权时，A 的预计收益是 .
当 B 选择亮牌时，A 的预计收益是 .
不难看出这是2个关于p的函数，可以把它画出来：
由于 B 始终希望最小化 A 的奖励，所以 A 实际的奖励函数应该是取最小的部分（下图红色部分），也就是极大化极小值。
同样的，黄色部分是极小化极大值。他们最终应该选取的点相同。
前面所述博弈是零和的，现在我们再取消这一约束成为 两个玩家的非零和有限隐藏信息博弈 。
同样，先看一个具体的博弈：
类似地，可以表述为一个矩阵。但由于这里不是零和了，因此 AB 双方的得分都需要列出。
显然，相互合作不揭发对于这个犯罪团伙是最好的方案。但实际上并非那么顺利。设想下面的情况：
因此最终他们会互相检举从而均被判刑6个月，这不是想要的最佳方案。这被称为 囚徒困境 。
NASH 均衡，英文 nash equilibrium ，也被音译为 纳什均衡 。
当且仅当对于所有的 n 个玩家，各自选择的每一项策略都使此玩家效用最大 ，即为 Nash 均衡。
更好理解的解释是：当所有玩家都知道其他玩家的策略，任意选择一名玩家允许他改变策略，他都没有理由改变，因为当前策略可以最大化效用。
Nash 均衡的定义适用于纯策略和混合策略。
对于这个具体博弈，A 选择检举（第二行）总是要比合作（第一行）更有利（0>-1, -6>-9）。可以称为第二行 严格控制 第一行。
这也就意味着如果选择了第一行的任何数据，那么总是应该倾向于选择下一行，因为它更有利。
在囚徒困境中，整个团体无法达成最佳策略。那么对于一个连续的囚徒困境博弈问题，是否可以通过先驱的博弈建立信任从而达到最佳呢？可惜答案也是否定的。
假设连续进行20场博弈，对于最后一场博弈来说，可以认为由于建立了信任，对方一定选择合作，基于最大化自己利益，这正是检举对方的好时机。因为双方都有这种想法，于是再次落入了囚徒困境。
因为第20次博弈结局已知，所以第19次博弈可看做是最后一次，根据归纳法不难看出，每一次博弈都将陷入囚徒困境。
