CMSC 5728 Decision Analysis & Game Theory - Lecture 02
- Minimax Theorem
- Nash’s Theorem
- Pareto Optimal
- Cournot Model of Duopoly
Games With no Saddle Points
当没有 saddle points，如下图所示
此时就P1和P2就需要做出一些策略，称之为 Mixed Strategies。每个玩家都会分配一定的概率选择某个策略，如下图所示
此时，
当 P1 选择 A 的时候：A = 1/3(4) + 2/3(0) = 4/3
当 P1 选择 B 的时候：B = 1/3(-5) + 2/3(3) = 1/3
显然此时选择 A 的收益会更大一些。但是这只是只考虑 P1 的情况，实际上 P2 的选择也会对 P1 有影响，我们继续看。
P2 设使用 C 策略的概率为 x，使用 D 的概率为 ( 1 - x )。此时，
当 P1 选择 A 的时候：A = x(4) + (1-x)(0) = 4x
当 P1 选择 B 的时候：B = x(-5) + (1-x)(3) = 3 - 8x
4x = 3 - 8x，x = 1/4，P1 的 payoff 为 1。
反过来，P1 也有理性，P1 也会做出一些策略的选择
当 P2 选择 C 的时候：C = x(-4) + (1-x)(5) = 5 - 9x
当 P2 选择 D 的时候：D = x(0) + (1-x)(-3) = -3 + 3x
5 - 9x = -3 + 3x，x = 2/3，P2 的 payoff 为 -1。
Two-person Non-zero Sum Games
玩家之间并非一定要对立对抗，也可以互相合作，如下图所示，矩阵中会有两个量，分别代表 P1 跟 P2 的损益。
但是这样会造成一个问题，Zero-sum game 的解决方法就是找 saddle points，但是 Non-zero sum game可能会有如下两种情况
左边这种情况，P1 跟 P2 都找到了对各自利益最大化的点，即（5，4）。但是右边这种情况会形成一个循环，P1 认为对自己利益最大的点 P2 不认可，反之 P1 也不认可。此时就需要一个新的解决方法，Nash’s Theorem
Nash’s Theorem
在博弈论中，如果每个参与者都选择了自己的策略，并且没有玩家可以透过改变策略而其他参与者保持不变而获益，那么当前的策略选择的集合及其相应的结果构成了纳什均衡。——维基百科
根据 Nash’s Theorem 得出的游戏结果是一个 NEP（Nash Equilibrium Point纳什均衡点），任何 saddle point 也是 NEP。
The Prisoner’s Dilemma 囚徒困境
Nash’s Theorem 著名的例子就是囚徒困境
S 为 Silence 保持沉默，C 为 confess 招供。由图可知，当两人都保持沉默时是对两人都是最好的情况，都只判刑2年。但是双方是不能交流的，如果自己保持沉默，对方招供了，那么对方将仅判1年，而自己将判10年。因此，两个犯人都会为了争取尽可能最小的判刑时间，而都选择招供，这个点就是 NEP。
Paroto Optimal
在没有使任何人境况变坏的前提下，使得至少一个人变得更好，这就是帕雷托改善。帕雷托最优的状态就是不可能再有更多的帕雷托改善的状态；换句话说，不可能在不使任何其他人受损的情况下再改善某些人的境况。
需要指出的是，帕雷托最优只是各种理想态标准中的“最低标准”。也就是说，一种状态如果尚未达到帕雷托最优，那么它一定是不理想的，因为还存在改进的余地，可以在不损害任何人的前提下使某一些人的福利得到提高。但是一种达到了帕雷托最优的状态并不一定真的很“理想”。——维基百科
如上图所示，（2，2）、（10，1）、（1，10）都是 Paroto Optimal。
Cournot Model of Duopoly
古诺寡头竞争的假设
- 两个寡头厂商生产的产品是同质或无差别的；
- 每个厂商都根据对手的策略采取行动，并假定对手会继续这样做，据此来做出自己的决策；
- 为方便起见，假定每个厂商的边际成本为常数，并假设每个厂商的需求函数是线形的；
- 两个厂商都通过调整产量来实现各自利润的最大化；
- 两个厂商不存在任何正式的或非正式的串谋行为。
边际成本亦作增量成本，指的是每增产一单位的产品所造成的总成本的增量。 这个概念表明每一单位的产品的成本与总产品量有关。比如，仅生产一辆汽车的成本是极其巨大的，而生产第101辆汽车的成本就低得多，而生产第10000汽车的成本就更低了。 但是，考虑到机会成本，随着生产量的增加，边际成本可能会增加。——维基百科
博弈分析
设 q1、q2 分别代表 企业1 和 企业2 生产的同质产品的产量，市场中该产品的总供给 Q = q1 + q2，令 P(Q) = a - Q 表示市场出清时的价格（假设这只是个简单的市场，固定需要 a 数量的产品）
设 企业i 生产 qi 的总成本 Ci(qi) = cqi，即企业不存在固定成本，且生产每单位产品的边际成本为常数 c （假设 c < a）。
两个企业同时进行产量决策。假定产品是连续可分割的，由于产出不可能为负，因此，每一企业的战略空间可表示为 Si = [0, 无穷]，其中一个代表性战略 si 就是企业选择的产量 qi （qi ≥ 0）。假定企业的收益是其利润额 U。
为了找到 NEP，企业1 会采取解决方案
企业2 会采取解决方案
则企业i 最优化问题的一阶条件是
也即是，若产量组合 (q1, q2) 为纳什均衡，则企业的产量选择必须满足
联立，得
总结
