微博校园发的一个阴(博)谋(弈)论题目

阅读本文需要
1,1-1,-1 3,0-3,0
0,30,-3 2,2-2,-2

limnk=1nak\lim_{n\to\infty}{\sum_{k=1}^{n}{a_k}}

题图:阅读本文需要(数学吧梗

微博校园发了一个转得都“变质”的考试附加题照片——还有可能是 PS 的!那些字真的跟纹身刚刚纹上去的时候一样,底下还泛红。我把这个题做了一做,又苦于最近没什么新的博文主题,就暂且写一篇这个罢了。

为什么这篇的标签有“计算机科学”呢?大概是因为博弈论是一门姚班专业课,且该课不属于物理,且姚班是“计算机科学实验班”。

回正题,微博校园发的考试附加题 是:

(Conspiracy)本题你需要回答 A 或 B,本题你的得分如此决定:

  • 若有超过一半的人回答 A 且你回答的是 A,则得 2 分;
  • 若有超过一半的人回答 A 且你回答的是 B,则得 10 分;
  • 若有超过一半的人回答 B,则得 0 分。

这是一个比较常规的博弈问题,我随便加了一些假设来计算这个问题的一些性质(见 本文后面的解答,注意 微博 上的解答有笔误),然后获得了微博校园的 转发,带来了一些观众。我觉得我的解答对于一个学过一点点博弈论的人比较中规中矩吧。

有趣的并不是我的解答,而是不同的人对这个问题的不同效用函数的设置。比如原微博下很多人提到标准分、和其他人的分差(也就是调分、看排名),如 泉大头LastExile_彻叶栗子球 的评论。如果考虑的是排名,这两位用户都想要表达选 B 是占优策略(支配策略,dominant strategy),但是实际上并非如此——如果考虑的是排名,我们就需要考虑其他每个同学不带这道题目的分数的分布,然后选择“最能提升排名”的策略。如果一开始分差过大,这道题不会产生任何影响;如果一开始分差的分布比较微妙,则加上对其他人的型(type)的假设才能正确计算应该如何参与此题。聪明的读者一经发现这种情况下需要用 Bayesian 博弈来建模了。

我的解答

为了让题目的分类不漏,假设参与考试的有 2n+12n+1 个人(nZ+n\in\mathbb{Z}_{+})。假设各人的效用都是此题自己获得的分数。此时该博弈是对称正规博弈,现在只考虑其对称 Nash 均衡。每个对称策略可以用一个数 pp 表示——这里记 pp 是每一个人选 A 的概率。显然 p=0p=0 对应一个 Nash 均衡,而 p=1p=1 不对应一个 Nash 均衡。

下面考虑 0<p<10<p<1 的情况,这时策略的支撑集是 {A,B}\left\{{\mathrm{A},\mathrm{B}}\right\},该策略是 Nash 均衡当且仅当2k=n2n(2nk)pk(1p)2nk=10k=n+12n(2nk)pk(1p)2nk,\NashEqEquation,r=p1p>0r=\frac{p}{1-p}>0,又令fn(r)=1+4k=1nrkt=1knt+1n+t,f_n\left(r\right)=\NashEqFunc,则充要条件改写为 fn(r)=0f_n\left(r\right)=0

因为 fnf_n 是连续、(在正数范围内)严格递增的函数,而 fn(0)=1f_n\left(0\right)=-1fn(1)>0f_n\left(1\right)>0,所以还存在另一个惟一的对称 Nash 均衡。

记对应于 2n+12n+1 个人的零点为 r0(n)\rZero,实际上 r0(n)15 (n)\rZero\to\frac15\ \left({n\to\infty}\right),可以用夹逼证明。

ε>0,u>0,n>u\forall\varepsilon>0,u>0,n>us=15+εs=\frac15+\varepsilon,则fn(s)1+4k=1uskt=1knt+1n+t,\EqRLeqOneFifthEpsFirst,nn\to\infty 则右边1+4k=1uskt=1knt+1n+t1+4k=1usk,\EqRLeqOneFifthEpsSecond,又令 uu\to\infty 则上式右边1+4k=1usk1+4s1s>0,\EqRLeqOneFifthEpsThird,由保号性对足够大的 nnfn(s)>0f_n\left(s\right)>0,对这些 nn 就有 r0(n)<s=15+ε\rZero<s=\frac15+\varepsilon。(给微积分生手的提示:这里保号性跳步了,并不是教科书版本的“保号性”,但你可以自己验证这命题是正确的。)

此外fn(15)1+4k=15k=0,\EqRGeqOneFifth,所以 r0(n)15\rZero\geq\frac15。这就得到所要证明的。又 p=r1+r16 (n)p=\frac{r}{1+r}\to\frac16\ \left({n\to\infty}\right),即对于参考人数足够大的情况,该对称 Nash 均衡近似于每个人各自以 16\frac16 的概率选 A。这个均衡下大家的期望得分是同一个(很小的)正数,而全写 B 的期望得分是 00

读者习题 怎么想到 r0(n)15 (n)\rZero\to\frac15\ \left({n\to\infty}\right) 的呢?

答案 先把方程瞎胡搞取个极限解出来再说。我想这个单调函数列零点极限和函数列极限零点的关系应该可以用更强的收敛性的语言形式化出来,但是我懒。

请启用 JavaScript 来查看由 Disqus 驱动的评论。