浅谈博弈论
博弈论(Game Theory)主要研究具有斗争或竞争性质现象的数学理论和方法, 考虑了游戏中的个体的预测行为和实际行为，并研究它们的优化策略. 在这类行为中，参加竞争的各方各自具有不同的利益. 为了达到各自的目标, 各方必须考虑对手的各种可能的行动方案, 并力图选取对自己最为有利的方案. 基本概念中包括局中人、行动、信息、策略、收益、均衡和结果等. 其中局中人、策略和收益是最基本要素。局中人、行动和结果被统称为博弈规则。
美女与男人的游戏
我们先举个例子, 假设有一天你在酒吧里走过来一个美女想跟你玩个游戏, 游戏规则是这样:
- 两个人把硬币出一面
- 如果两面都是正面的话, 你赢走3块钱
- 如果两面都是反面, 则你赢走1块钱
- 如果是一正一反的话则, 那你就输给她2块钱
从几率上来讲玩四把, 一次两正, 一次两反, 所以赚了四块钱, 还有两把是一正一反, 所以是输了4块钱. 尽管这游戏看起来是公正的, 但是美女可以采取一定的策略让你的收益期望为负数.
我们假设你出正面的概率是$x$, 反面的概率是$1-x$, 美女出正面的概率是$y$, 出反面的概率就是$1-y$. 你的收益期望是
$$
z(x, y) = 3xy + 1(1-x)(1-y) - 2*(x(1-y) + y(1-x)) = 8xy - 3x - 3y + 1 \quad x,y \in [0,1]
$$
你希望不要赔钱但是美女则希望你一直赔钱, 你们唯一能做的就是调整概率$x$和$y$, 有没有一种可能当美女义某一个$y$出牌的时候, 无论你的概率是多大, 她都能赚钱而你的期望都是负的. 我们来推算下$y$等于多少的时候, $E$总是小于零
$$E = (8x-3)y - 3x + 1 < 0 \Rightarrow (8x - 3)y < 3x -1$$
假如$8x - 3 > 0 \Rightarrow x > \frac{3}{8} \Rightarrow y < \frac{3x-1}{8x-3}$ 右边的函数是个减函数, 它的最小值是当$x=1$的时候$y < \frac{2}{5}$
假如$8x - 3 < 0 \Rightarrow x < \frac{3}{8} \Rightarrow y > \frac{3x-1}{8x-3}$ 这个同样是个减函数, 它的最大值是当$x=0$的时候$y > \frac{1}{3}$
也就是说当$y$属于$\frac{1}{3}$到$\frac{2}{5}$的时候, 你的数学期望总是负的, 无论你采取什么样的措施, 你总是会倾向于输钱. 这就是策略, 也就是博弈论.
三姬分金
假如有三个人ABC分一百枚金币, 按顺序提议A先提, B再提, C再提, 如果提议未获半数以上通过, 半数以上不包括半数, 那么提议人就被处死. 我们假设这三个美女都是聪明人且是理性的, 然后是邪恶的.
如果只余下B和C两个人, 在这种情况下, B不管什么提议, C都要杀掉B. 无论B如何提议只要C否定就未获半数以上人通过, 于是B就会死, C就能拿到全部金币. B清楚的知道这个结果所以她不能让A死, 她会支持A的一切建议. 这件事A也是知道的, A会直接提议拿走全部的金币.
假设再来一个人M在A之前先选, M知道如果自己死了A就会拿走全部金币, M会选择贿赂B和C, 因为假如M掉A会拿走全部金币, B和C只能拿零个, 所以M拿零个金币, B和C各拿一个金币.
在生活中我们称M具有先手优势, 而B和C没什么决策力属于低端人群, 但是M总是要拉拢B和C而且B和C没什么风险虽然收益也很低. A处于夹层, 没有先手优势, 不能让自己的利益最大化, 其次他不属于低端人群所以不是M所拉拢的对象. A如果想获得更大收益就必须把M干掉, 他就成为老大, 他就具有先手优势了.
A也可以选择贿赂B和C, 我们称之为共谋或者串谋, 但是有一个问题当M杀掉之后A会不会反悔. 假如这个游戏是重复玩的, 他们可以选择共谋, 如果A不守规矩, 下次就不再合作. 但是如果这游戏只玩一次那A就一定反悔因此B和C是不敢冒这个风险的
囚徒困境
两个小偷A和B被警察抓了并且告诉他们如果两个人都坦白则判八年, 如果两个人都不坦白则判一年, 如果其中一个人坦白则坦白的那个人不判罪另一个判十年.
对于A来说无论B坦白不坦白他的最佳选择都是坦白, 同样的道理对于B来说他的最佳决策也是坦白, 最终的结果就是A和B都会坦白, 他们两个人都会被判八年.
纳什均衡
这就是纳什均衡点, 意思就是在这样的决策情况下没有一个人有改变决策的动力, 即使我们知道那不是最优解, 纳什均衡点不一定是整体的最优解. 改变的方法就是串谋或者叫共谋, 如果这事只有一次, 那么肯定反悔, 只有在多次博弈的情况下他们才有合作的可能.
沉没成本
沉没成本是指已经付出而且不可回收的成本. 经济学上说在决策的时候不应考虑沉没成本. 我们必须学会认清沉没成本, 你已经花出去的时间和钱已经沉没了不要去考虑它, 就当是白来的不要让沉没成本来干扰你的决策.
一美元拍卖陷阱
美国耶鲁经济学教授跟学生玩的一个游戏, 他拍卖一美元, 但是拍卖规则是两条
- 出价最高的人会获得这一美元
- 多个人出价, 出价最高的和出价次高的都需要付钱
五美分起拍每次加价五美分
当第二个学生出到50分的时候, 第一个学生不得不出价到55分, 但此时教授以及开始盈利了, 在到出到100分的时候, 大家尽管知道这个游戏已经无法盈利了, 但是次高的为了不亏掉95分只能继续出价, 于是这个价格会一直往上涨.
学生在参与的时候可能只是因为好玩或者因为能小赚一笔, 当教授开始盈利的时候他们已经开始觉得不对劲了但是陷入了一种困境, 自己已经不想再继续玩了, 但是不玩的话自己就要白白损失了, 而到了后面的阶段就完全是后悔的.
解决办法也很简单: 不参与或者可信威胁, 在这个问题中如果所有人都相信B财大气粗会一直跟价那么别人就不会参与了.
红眼睛和蓝眼睛
有一个村子有100个人, 这100个人里面有95个人他们的眼睛是蓝色的, 还有五个人他们的眼睛是红色的, 但是村里的人并不知道有95个蓝眼睛和五个红眼睛. 而且村子里有个规矩就是你能看别人的眼睛是什么颜色, 但是你也不能告诉别人说你的眼睛的是什么颜色. 一旦你知道你的颜色是什么颜色你就必须在第二天中午在广场自杀. 所以所有人都不知道自己眼睛是什么颜色. 突然有一天村子来来了一个外乡人并告诉他们说这个村子里有红眼睛的人. 在这外乡人走后第五天村子里的五个红眼睛的人都自杀. 为什么？
假设村里只有一个红眼睛，那么在外乡人走后他就会自杀 因为他看到的人都是蓝眼睛的.
假设村里有两个红眼睛，他们知道村子里有红眼睛他们以为外乡人走后第一天他就会自杀，但是他没自杀，其他人都是蓝眼睛那他就知道了自己是红眼睛.
假设村里有五个人，那么在第五天的时候这五个人都会自杀.
看起来这是个悖论，因为外乡人确实并没有提供任何新的知识. 他们本来就知道村里有红眼睛
共有知识和公共知识
共有知识
大家都知道的
公共知识
大家知道大家都知道的知识
讨论
在外乡人来之前红眼睛的人不知道大家都知道，当外乡人说了之后共有知识就变成了公共知识。
例如在皇帝的新装中，但小男孩呐喊出皇帝没穿衣服，这个时候共有知识就变成了公共知识。从共有知识变成公共知识。
最优停止规则
麦穗原理
有一次苏格拉底的学生问他什么是爱情，苏格拉底把这些学生带到了一个麦田上然后跟他们说你从这条路开始往前走，一路走过去，你只能前进，不能后退，只能前进，同时你只能捡一次，我们通过某些方法捡出一个最大的麦穗来，如果捡的太早那后面遇到最好的就没法选择，如果一直迟迟不犹豫那么很大的可能会错过最好的。
秘书问题
这是个与前面类似的问题, 有一个人公司要招聘一个秘书, 你有两种选择录用他那你就不能看后面的面试者了, 或者是拒绝他, 然后他会去找其他工作, 我们应该采取什么策略才能保证我们选到最优秀的人呢.
最优停止策略
假如我们把所有的面试者写为单位1, 这个问题的最优解是一个停止规则, 我们会拒绝头$r-1$个应聘者, 令他们中的最佳人选为M, 然后在备选区间, 剩下的应聘者中选择第一个比M好的应聘者, 最佳人选被选中的概率是:
$$
\begin{split}
P(r) &= \sum_{i=1}^{n} P(applicant ; i ; is ; selected |applicant ; i ; is ; best) * P(applicant ; i ; is ; best)\\\\
&= \Big(\sum_{i=1}^{r-1}0*\frac{1}{n} \Big) + \Big(\sum_{i=r}^{n} P(the ; best ; of ; the ; first ; i - 1 ; applicantes ; is ; in ; the ; first ; r - 1 ; applicants | applicant ; i ; is ; best) * \frac{1}{n} \Big)\\\\
&= \sum_{i=r}^{n} \frac{r-1}{i-1}*\frac{1}{n}\\\\
&= \frac{r-1}{n}\sum_{i=r}^{n}\frac{1}{i-1}\\\\
P(x) &= x \int_x^1 \frac{1}{t} dt = -x log(x)\\\\
\end{split}
$$
通过求导我们可以得知当$x = \frac{1}{e}$的时候函数达到最大值, 也就说我们应该选其中前36.8%作为我们的样本区间, 此时我们找到最好的那个人的概率也是36.8%.
总结
做决策的时候我们应该选择一定的样本区间, 我们称之为观望期, 然后在备选区间遇到比样本区间都大的我们就可以pick了.