一些有关Game Theory(博弈论)的学习记录

前言：

以下是笔者学习【耶鲁大学】博弈论 课程中整理的内容，因为笔者实在是懒的自己找书啃。有些内容可能结合自己的研究方向（Multiple-Agent-System）简单拓展；至于数模感觉能用到的几率比较小。

一、Prisoner’s Dilemma 囚徒困境

1.1 四个重要结论

定义 1.1：Strictly Dominant Strategy 严格优势策略

假如策略$\alpha$在无论对手选择何种应对的情况下的收益都高于策略$\beta$，则称策略$\alpha$为相对$\beta$的严格优势策略；

结论 1.1：不要使用严格劣势策略

我们假设参与博弈的行为人都是理性的（和经济学中定义的理想经济人类似），都希望追求更高的收益（当前，每个人衡量收益大小的标准有不同，对收益的看法显然也会影响决策）；

结论 1.2：理性的选择可能导致更糟的结果

显然，如果双方均追求对于个人收益的最大化，可能导致双输；

如何破解囚徒困境？

沟通并不能解决这个困境，在缺乏强制力介入的情况下，沟通缺乏意义，可能有效的方式是有强制力的合同（比如书面合同）、重复博弈、教育。

结论 1.3：如欲得之，必先知之 If you want to get it, you must know it first

如果我们不知道一个人或一场博弈中的收益情况，那么我们就不可能获得收益；

结论 1.4：换位思考 Put yourself in others’ shoes and try to figure out what they’ll do

假如我们知道另一方的收益情况，那么如果我们确认对方会根据 结论 1.1 选择某种策略，那么我们可以根据对方的选择选择对于自己收益更高的那种，即使站在自己的角度，并没有严格优势策略；

1.2 Grade Game 积分游戏

关于耶鲁大学《博弈论》课程上的积分游戏的具体推导见下，懒地打了。。。

1.3 Ingredients of a game 博弈的要素

• Players 参与者；
• Strategies 策略；
  • $s_i$: $Player_i$的某个特定策略；
  • $S_i$: $Player_i$的策略集合；
  • $S$: 一次博弈，即所有参与者的策略组合；
• Payoff 收益；
• Assumption 假设：每个参与者都知道其他人的可能策略和收益，即博弈者之间信息透明；
• $S_{-i}$: 一次博弈中除了$Player_i$之外的其他所有参与者的策略；

定义符号后，我们给出更严格的严格优势策略的定义：

定义 1.1 Plus：Strictly Dominant Strategy 严格优势策略

$Player_i$'s strategy $S’i$ is strictly dominated by $Player_i$'s strategy $S_i$ if $U_i(S_i, S{-i}) > U_i(S’i, S{-i})$ for all $S_{-i}$；

1.4 Hannibal 汉尼拔

Ben教授通过汉尼拔进军罗马的例子，引入了弱优势策略，弱优势策略允许了一部分策略组下收益相等而不是严格大于；

定义 1.1 Extension：Weakly Dominant Strategy 弱优势策略

$Player_i$'s strategy $S’i$ is weakly dominated by $Player_i$'s strategy $S_i$ if $U_i(S_i, S{-i}) \ge U_i(S’i, S{-i})$ for all $S_{-i}$, and $U_i(S_i, S_{-i}) > U_i(S’i, S{-i})$ for some $S_{-i}$;

关于汉尼拔的具体推导见下：

1.5 Iterative Deletion 迭代剔除劣势策略

该策略要求参与者首先找到所有劣势策略，剔除它们，然后再重新审视整个博弈，如此往复。一个具体的例子如下：

每人选择一个1到100之间的数字，谁选的数字最接近平均数的三分之二，则获得胜利。

第一层：

假设大家选取的数字是在 0 ～ 100 间随机分布的，那么 average 约等于50，50的2/3应该是33左右；但是问题也很明显，大家不会都进行随机选择；

第二层：

我认为别人都按照第一层的思路进行思考，即大部分人都会选择33，那么我应该选择 33 * 2/3 = 22；

第三层：

从这一层开始，使用了博弈论的框架，即假设参与者都是理性的。那么，选择大于67的数字属于弱劣势策略（除非大家均选择100）；那么大于67的数字就被剔除了；按照这个思路，我选择45；

第四层：

如果大家都考虑到了上面一层，那么基于第三层，现在选择大于45的也变成了弱劣势策略；按照这个思路，我应该选择30；

按照这个逻辑一直持续下去，30 ～ 20、20 ～ 13，不断持续剔除下去，那么最终所有人都会选择1；

但1就是正确答案吗？

得到1需要反复迭代、剔除，即需要我不断知道别人都想到了上一层，即我知道你知道我知道你知道（无限套娃）我是理性的，即 Common Knowledge 共同知识 。

定义 1.5：共同知识

共同知识是指某个信息或事件不仅被所有参与者知晓，而且所有参与者都知道其他参与者也知道该信息，并且知道其他参与者也知道其他人知道该信息，如此无限递归。
即：所有人都是理性的；所有人都知道所有人是理性的；所有人都知道所有人都知道所有人是理性的……

1.6 The Median-Voter Theorem 中位选民定理

该定理事实上只是迭代剔除劣势策略在政治学上的一个应用。并且该模型还是简化了现实问题，存在不少问题；

首先，对于2个候选人A和B，他们的立场用 1 ～ 10 数字表示，假定每个数字对应10%的选民，选民仅按立场的接近程度进行投票；如果立场的接近程度相同，则一半一半；候选人的目标就是最大化选票，即收益；

容易发现，1和10为劣势策略，具体推导如下：如果A选择2，那么

1. 当B选1时，$U_A(2,1) = 90% > U_A(1,1) = 50%$；
2. 当B选2时，$U_A(2,2) = 50% > U_A(1,2) = 10%$；
3. 当B选3时，$U_A(2,3) = 20% > U_A(1,3) = 15%$；
4. 当B选4时，$U_A(2,4) = 25% > U_A(1,4) = 20%$；

以此类推，后面都是2优于1并且均相差$5%$；

选2严格优于选1，根据对称性，选9也严格优于选10。

越接近中间就优于两侧吗？并不，可以算一个例子：如果A选择3，那么

当B选择1时，$U_A(3,1) = 85% < U_A(2, 1) = 90%$，即A选3并不严格优于选2；

但是如果按照迭代剔除的思想，剔除劣势策略1和10之后，那么接下来策略2和9就变成了劣势策略，以此类推，最优的策略是选5和选6；这就是中位选民定理；

这个模型存在以下问题：

1. 选民并非平均分布；
2. 选民并非完全根据立场来投票，即考量因素往往是多维度的；
3. 选民往往会根据候选人过去的行为判断立场而并非按候选人所声称的；
4. 选民存在弃票；
5. 候选人往往大于2个；
6. 大选之前还有初选；
7. …

1.7 Best Response 最优对策

如果站在双方的角度，都不存在严格最优对策，那么站在我的角度，假设另一方采取某策略的概率是$p$，据此计算我选择每个策略的期望收益；

持续更新中…