由于前段时间一直忙着找地方上学，所以一直没有更新，先开个坑。
论文概述
研究问题
这篇paper旨在回答的是：在结构化的有限种群中，自然选择倾向于合作的条件。具体而言，paper研究的是静态复杂网络上的博弈，即种群是有限的，网络不是混合均匀的（即不是全连通的），并且网络的拓扑结构是固定的，不会受博弈动力学影响。他们提出了这种情况下合作行为产生的一个判据\(b/c>k\)。
在作者提出的模型中，种群的博弈行为在一个网络上进行，每个节点代表一个个体，每一轮博弈中有边相连的个体都会进行一次博弈。两个个体间的博弈被设定为囚徒困境博弈，即收益矩阵如下 \[\begin{matrix} &C&D\\ C&b-c&-c\\ D&b&0 \end{matrix}\] 其中\(b>c\)，且一个个体要么总是合作的，即会给每个邻居付出成本\(c\)，使得该邻居得到收益\(b\)；要么总是背叛的，即不会付出任何成本，但会从每个合作者邻居处得到收益\(b\)。
其中，每一个个体的适应度被定义为\(f=1-w+wP\)，\(P\)为该个体本轮的收益。该式子中的\(w\)含义为博弈收益对适应度的贡献，可以理解为个体对收益的偏好程度，\(w\)越大则越注重收益带来的影响。本文考虑的是弱选择，即\(w<<1\)，可以理解为博弈收益只是影响适应度的因素之一。
在每一轮博弈后，都会对个体的决策进行更新，文中共提出了如下三种更新方法。
- 死亡出生（DB）更新：每一轮会等概率的随机选中一个个体，设该个体的邻居中，所有合作者的适应度总和为\(F_C\)，所有背叛者的适应度总和为\(F_D\)，则背叛者个体会有 \[\frac{F_C}{F_C+F_D}\] 的概率在下一轮变为合作者，而合作者个体会有 \[\frac{F_D}{F_C+F_D}\] 的概率在下一轮变为背叛者，其他\(N-1\)个未选中的个体保持原有策略。
- 模仿（IM）更新：类似DB更新，只是在选中个体后，计算改变策略时会考虑自身的收益而不只是邻居的。
- 出生死亡（BD）更新：每个个体被选择的概率不再是相同的，而是正比于适应度，其中被选择的个体会等概率的选择一个邻居，使该邻居变成它的策略。
而判断自然选择倾向于合作还是背叛，则是基于固定概率。在一个网络上等概率地随机选择一个个体，使其为合作者，其余\(N-1\)个均为背叛者，则最终网络演变成所有个体都是合作者的概率\(\rho_C\)即为合作的固定概率。类似地可以定义背叛的固定概率\(\rho_D\)。当\(\rho>\frac 1N\)时，我们可以认为自然选择支持合作者入侵背叛者。
主要结论
通过在环、网格图、随机规则图、随机图和无标度网络上的数值实验验证和基于配对近似和扩散近似的推导，得到了以下结论。在弱选择和\(N>>k\)且两者都充分大的前提下，在DB更新中，自然选择支持合作者入侵背叛者且抑制背叛者入侵合作者（即\(\rho_C>1/N>\rho_D\)）当且仅当\(b/c>k\)；在IM更新中则为\(b/c>k+2\)；在BD更新中则总是支持背叛者入侵合作者且抑制合作者入侵背叛者，其中\(k\)为网络的平均度。
具体地推导将在下一节中分析，这里先给出这些结论的直观理解。首先是不同更新下结论的差异，在BD更新中，可以理解为每个个体只考虑自身的收益，而不会考虑邻居的，此时背叛者总是占据有利地位，也是导致该更新下总是支持背叛者入侵合作者且抑制合作者入侵背叛者。而另外两种更新中，被选择的个体还会考虑邻居的收益，此时背叛者的邻居很可能没有收益，如果这个邻居在一个背叛者的集群中；而如果它的邻居是一个在合作者集群边缘的合作者，则该合作者的收益是非常大的，背叛者可能就会倾向于选择合作者。IM更新会考虑自身的收益，即会更倾向于自私，因此合作的条件比DB更新更高一些。
而DB更新和IM更新的结论都和Hamilton规则具有相似性，即社会粘度越高的群体越倾向于合作。在生活中也有对应的例子，例如在景区里，商家会随机接触大量的顾客，此时他们的行为更倾向于背叛者；而在人口稳定的小镇上，商家更需要熟客，即更倾向于合作。事实上这两种社交网络的平均度也能指出这一现象和本文结论的一致性。
理论推导
本节将会分析支撑材料中的理论推导。值得一提的是，我给出了\(k=2\)时不借助近似方法的证明，以及补上了原文中一些直接给出结果但推导不平凡的式子的证明。接下来将分析DB更新的结论的推导，而另外两种更新的推导方法没有太大差异，不再赘述。
首先作者使用了配对近似（pair approximation），该方法可以直观理解成将平均场理论用在节点对的分布上，即以两端都是合作者的边所占的比例\(p_{CC}\)去作为一个合作者个体的邻居也为合作者的概率，其余的情况也是类似地。在这个近似下，原文(2-10)式都是平凡的。而原文(11-12)式则是将模型连续化，这是一个很常见的处理方法，例如用平均场证明优先连接模型的无标度性就有用到。而两个式子中，第二个等号的表达式则需要一定的推导，大致过程为先用等价无穷小等方法变换一下表达式，然后利用配对近似得到的原文(2)式中的 \[ \begin{align*} q_{A|X}+q_{B|X}&=1\\ p_{XY}&=q_{X|Y}p_Y\\ P_{AB}&=P_{BA} \end{align*} \] 几式以及二项式展开的逆过程进行证明，详细步骤见附录。
在得到了节点和边的变化的动力学方程后，推导到(15)式的过程也是平凡的。而在(15)式中，由于\(\dot{p}_A=O(w)\)而\(\dot{q}_{A|A}=F_2+O(w)\)，在弱选择时\(w\)充分小，故\(\dot{q}_{A|A}\)的收敛速度远快于\(\dot{p}_A\)，从而\(\dot{q}_{A|A}\)很快就会收敛，即\(F_2=0\)，则由原文(14)式有\(1+(k-1)(q_{A|B}-q_{A|A})=0\)，结合原文(2)式即可得到(16-17)式。
下一步是扩散近似，即把\(p_A\)和\(q_{A|A}\)这两个随着时间变化的随机过程设定为扩散过程，其中一个扩散过程\(X_t\)有 \[{\rm d} X_t=\mu(t,X_t){\rm d}+\sigma(t,X_t){\rm d} B_t\] \(\mu\)和\(\sigma\)分别为该过程的漂移和扩散，对一个扩散过程在很短的时间\(\Delta t\)内的变化计算期望和标准差，对应的即为漂移和扩散乘上\(\Delta t\)，这即原文(18-19)式的目的。再结合KBE方程，即可得到原文(20)式，通过参数分离后积分和等价无穷小去近似，根据初值条件就得到了(21)式，具体过程见附录。
在得到了\(\phi_A\)之后，\(\phi_A(1/N)\)即固定概率\(\rho_C\)。由此通过一些初等计算和\(\rho_D=\phi_A(1-1/N)\)即可得到原文(22-24)式，又由\(k\)充分大，只考虑\(k^2\)前的系数，就导出了1/3规则。Nowak等人在混合均匀的有限种群博弈中提出了弱选择下的1/3规则，Ohtsuki等人的结果说明这个规则推广到异质化的情况下仍然适用。最后，根据原文(24)式令\(\rho_C>\rho_D\)，即有 \[(k+1)(b-c)-(k-1)c-(k-1)b>0,\] 从而得到\(b/c>k\)时\(\rho_C>\rho_D\)，再代入原文不等式(22-23)，即可得到这是\(\rho_C>\frac 1N>\rho_D\)的充要条件。
\(k=2\)时的证明
从只有一个合作者开始，在一个环上进行DB更新时，所有合作者总是连通的。这是因为可能改变自己策略的个体的邻居中一定有不同策略的个体，在一开始只有一个合作者时，会改变的只有合作者和它的两个背叛者邻居，此时一个背叛者改变策略后就成了两个合作者的集群。再下一回合，只有两个合作者和他们的背叛者邻居有可能改变策略，此时背叛者改变后形成三个合作者的集群。从三个开始，有可能改变策略的个体只有合作者集群与背叛者相邻的两个个体和它们的背叛者邻居。因此。
在这个条件下，不难看出当合作者和背叛者的数量都超过三个时，合作者集群增加、减少个体或保持不变的，因为此时只有四个个体有可能改变策略，并且这几个个体的邻居的适应度都固定。不妨设此时合作者集群减少、增加一个个体的概率分别为\(p\)、\(q\)，则保持不变的概率为\(1-p-q\)。另外，设合作者从\(1\)个增加到\(3\)个的概率为\(\alpha\)，背叛者从\(2\)个减少到\(0\)个的概率为\(\beta\)。
设\(\mathcal P\)为从\(3\)个合作者开始，增加到\(N-2\)个合作者，且整个过程中合作者数量不会少于\(3\)个的概率。很显然，\(\alpha\beta \mathcal P<\rho_C\)，这是因为\(\alpha\beta\mathcal P\)是在有限制条件下合作者占领整个集群的概率。下文中\(\rho_C\)和\(\rho_D\)分别为策略\(C\)和策略\(D\)的固定概率。
接着先计算\(p\)和\(q\)。考虑一个可能改变策略的合作者，此时它的合作者邻居适应度为\(2b-2c\)，背叛者邻居适应度为\(b\)，它变为背叛者的概率为 \[ \frac{1-w+w(2b-2c)}{2(1-w)+w(3b-2c)} \] 从而有 \[ p=\frac{2}{N}\frac{1-w+wb}{2(1-w)+w(3b-2c)}\tag{1}\label{Equ:p} \] 同理可得 \[ q=\frac{2}{N}\frac{1-w+w(b-2c)}{2(1-w)+w(b-2c)}\tag{2}\label{Equ:q} \] 下一步来计算\(\mathcal P\)。事实上，\(\mathcal P\)可以看作一个有吸收壁的随机游走问题被某个吸收壁吸收的概率：在一维数轴上从\(1\)开始随机游走，有\(p\)的概率向左一个单位，\(q\)的概率向右一个单位，在\(0\)和\(N-4\)各有一个吸收壁，则被\(N-4\)吸收的概率即\(\mathcal P\)。先设从\(k\)点出发，吸收壁为\(0\)和\(n\)时，被吸收壁\(0\)吸收的概率为\(\delta(k,n)\)，特殊地，\(\delta(0,n)=1,\delta(n,n)=0\)。由该过程的Markov性， \[ \delta(k,n)=p\delta(k-1,n)+q\delta(k+1,n)+(1-p-q)\delta(k,n),k=1,2,\dots,n-1. \]
整理得 \[ \frac qp[\delta(k+1,n)-\delta(k,n)]=\delta(k,n)-\delta(k-1,n). \] 迭代得 \[ \delta(k,n)-\delta(k-1,n)=-\left(\frac qp\right)^{n-k}\delta(n-1,n). \] 累加得 \[ \begin{align*} \delta(k,n)-\delta(0,n)&=\delta(k,n)-1\\ &=-\delta(n-1,n)\sum_{i=1}^{k}\left(\frac qp\right)^{n-i}\\ &=\begin{cases} -\frac{\left(\frac qp\right)^{n-k}-\left(\frac qp\right)^{n}}{1-\frac qp}\delta(n-1,n),&p\neq q,\\ -k\delta(n-1,n),&p=q. \end{cases} \end{align*} \] 代入\(k=n-1\)，有 \[ \begin{align*} \delta(n-1,n)=\begin{cases} \frac{1-\left(\frac qp\right)}{1-\left(\frac qp\right)^n},&p\neq q\\ \frac1{n+1},&p=q. \end{cases} \end{align*} \] 从而 \[ \begin{align*} \delta(1,n)=\begin{cases} \frac{1-\left(\frac qp\right)^{n-1}}{1-\left(\frac qp\right)^n}=\frac{\left(\frac pq\right)^{n}- \frac pq}{\left(\frac pq\right)^{n}-1},&p\neq q\\ \frac n{n+1},&p=q. \end{cases} \end{align*} \] 又由\(\mathcal P=1-\delta(1,N-4)\)，有 \[ \begin{align*} \mathcal P=\begin{cases} \frac{1-\frac{p}{q}}{1-\left(\frac pq\right)^{N-4}},&p\neq q\\ \frac 1{N-3},&p=q. \end{cases} \end{align*} \]
回到\(\eqref{Equ:p}\)和\(\eqref{Equ:q}\)，有\(p<q\)当且仅当 \[ (b-2c)[(b-c)w+1-w]>0 \] 即\(w\)充分小时，当且仅当\(b/c>2\)，而\(p>q\)当且仅当\(b/c<2\)。
注意到，\(p<q\)时\(\mathcal P\to1-\frac pq>0,N\to\infty\)，则在\(N\)充分大时一定有\(\rho_C>\alpha\beta\mathcal P>\frac1N\)。由于合作者在只有\(1\)个和\(2\)个时增加的概率要小于\(q\)，故全部变为合作者的概率应该小于\(\beta(1-\delta(1,N-2))\)，\(p>q\)时\(1-\delta(1,N-2)\)收敛于零且是指数下降的，收敛速度远快于\(\frac 1N\)，因此在\(N\)充分大时\(\rho_C<\frac 1N\)。
综上所述，\(N\)充分大时\(\rho_C>\frac1N>\rho_D\)当且仅当\(b/c>2\)。
原文式(11)
引入记号 \[ \begin{align*} e_{BA}&=a(k-1)q_{A|A}+b[(k-1)q_{B|A}+1]-1\\ e_{BB}&=c(k-1)q_{A|B}+d[(k-1)q_{B|B}+1]-1\\ e_{AA}&=a[(k-1)q_{A|A}+1]+b(k-1)q_{B|A}-1\\ e_{AB}&=c[(k-1)q_{A|B}+1]+d(k-1)q_{B|B}-1\\ \end{align*} \] 对应原文式(7-10)四个公式中\(w\)前的系数，则有 \[ \begin{align*} \frac{k_Af_A}{k_Af_A+k_Bf_B}&=\frac{k_A+k_Awe_{BA}}{k+k_Awe_{BA}+k_Bwe_{BB}}\\ &=\frac{k_A}{k}\cdot(1+we_{BA})\cdot\frac{1}{1+\left(\frac{k_A}{k}e_{BA}+\frac{k_B}{k}e_{BB}\right)w}. \end{align*} \] 注意\(x\to0\)时\((1+x)^{-1}\sim1-x\)，则有\(w\to0\)时 \[ \begin{align*} &\frac{k_A}{k}\cdot(1+we_{BA})\left[1-\left(\frac{k_A}{k}e_{BA}+\frac{k_B}{k}e_{BB}\right)w+O(w^2)\right]\\ =& \frac{k_A}{k}\left[1+\left(e_{BA}-\frac{k_A}{k}e_{BA}-\frac{k_B}{k}e_{BB}\right)+O(w^2)\right]\\ =&\frac{k_A}{k}\left[1+\frac{k_B}{k}\left(e_{BA}-e_{BB}\right)w\right]+O(w^2)\\ =&\frac{k_A}{k}+\frac{k_Ak_B}{k^2}\left(e_{BA}-e_{BB}\right)w+O(w^2). \end{align*} \] 从而有 \[ \begin{align*} \sum_{k_A+k_B=k}\frac{k!}{k_A!k_B!}q_{A|B}^{k_A}q_{B|B}^{k_B}\frac{k_A}{k}&=q_{A|B}\sum_{k_A+k_B=k}\frac{(k-1)!}{(k_A-1)!k_B!}q_{A|B}^{k_A-1}q_{B|B}^{k_B}\\ &=q_{A|B}(q_{A|B}+q_{B|B})^{k-1}=q_{A|B}, \end{align*} \] 第二个等式用到了原文式(2)。类似地，有 \[ \begin{align*} &\sum_{k_A+k_B=k}\frac{k!}{k_A!k_B!}q_{A|B}^{k_A}q_{B|B}^{k_B}\frac{k_Ak_B}{k^2}(e_{BA}-e_{BB})\\ =&\frac{k-1}{k}q_{A|B}q_{B|B}(e_{BA}-e_{BB})\sum_{k_A+k_B=k}\frac{(k-2)!}{(k_A-1)!(k_B-1)!}q_{A|B}^{k_A-1}q_{B|B}^{k_B-1}\\ =&\frac{k-1}{k}q_{A|B}q_{B|B}(e_{BA}-e_{BB})(q_{A|B}+q_{B|B})^{k-2}\\ =&\frac{k-1}{k}q_{A|B}q_{B|B}(e_{BA}-e_{BB}). \end{align*} \] 在上面两个式子的推导中，第一个式子在\(k_A=0\)时，第二个式子在\(k_A,k_B=0\)时对应的项为\(0\)，默认先去除这些项。
代入原文式(5)，有 \[ {\rm Prob}\left({\Delta p_A=\frac1N}\right)=p_{AB}\left[1+\frac{k-1}{k}q_{B|B}(e_{BA}-e_{BB})w\right]+O(w^2).\tag{3}\label{Equ:1N} \] 其中 \[ e_{BA}-e_{BB}=q_{B|B}(a(k-1)q_{A|A}+b[(k-1)q_{B|A}+1]-c(k-1)q_{A|B}+d[(k-1)q_{B|B}+1]. \] 同理转换原文式(9)可得 \[ {\rm Prob}\left({\Delta p_A=-\frac1N}\right)=p_{AB}\left[1+\frac{k-1}{k}q_{A|A}(e_{AB}-e_{AA})w\right]+O(w^2),\tag{4}\label{Equ:-1N} \] 其中 \[ e_{AB}-e_{AA}=c[(k-1)q_{A|B}+1]+d(k-1)q_{B|B}-a[(k-1)q_{A|A}+1]+b(k-1)q_{B|A}. \] 由\(\eqref{Equ:1N}\)和\(\eqref{Equ:-1N}\)即可得到 \[ \begin{align*} &\frac1N{\rm Prob}\left({\Delta p_A=\frac1N}\right)-\frac1N{\rm Prob}\left({\Delta p_A=-\frac1N}\right)\\=&w\frac{k-1}{N}p_{AB}(I_aa+I_bb-I_cc-I_dd)+O(w^2), \end{align*} \] 即原文式(11)
原文式(12)
对原文式(6)，在\(w\to0\)时有 \[ \begin{align*} &\sum_{k_A+k_B=k}\frac{2k_A}{kN}{\rm Prob}\left({\Delta p_{AA}=\frac{2k_A}{kN}}\right)\\=&p_B\sum_{k_A+k_B=k}\frac{2k_A}{kN}\frac{k!}{k_A!k_B!}q_{A|B}^{k_A}q_{B|B}^{k_B}\left(1-\frac{k_Bf_B}{k_Af_A+k_Bf_B}\right)\\ =&p_B\sum_{k_A+k_B=k}\frac{2k_A}{kN}\frac{k!}{k_A!k_B!}q_{A|B}^{k_A}q_{B|B}^{k_B}\left(1-\frac{k_B}{k}\right)+O(w)\\ =&\frac{2p_{AB}}{N}\sum_{k_A+k_B=k}\binom{k-1}{k_A-1}q_{A|B}^{k_A-1}q_{B|B}^{k_B}-\frac{2(k-1)p_{AB}q_{B|B}}{kN}\sum_{k_A+k_B=k}\binom{k-2}{k_A-1}q_{A|B}^{k_A-1}q_{B|B}^{k_B-1}+O(w)\\ =&\frac{2p_{AB}}{N}(q_{A|B}+q_{B|B})^{k-1}-\frac{2(k-1)p_{AB}q_{B|B}}{kN}(q_{A|B}+q_{B|B})^{k-2}+O(w)\\ =&\frac{2p_{AB}}{N}\left(1-\frac{k-1}{k}q_{B|B}\right)+O(w)\\ =&\frac{2p_{AB}}{kN}\left(k-(k-1)(1-q_{A|B})\right)+O(w)\\ =&\frac{2p_{AB}}{kN}\left(1+(k-1)q_{A|B}\right)+O(w). \end{align*} \] 对原文式(10)，在\(w\to0\)时有 \[ \begin{align*} &\sum_{k_A+k_B=k}\frac{2k_A}{kN}{\rm Prob}\left({\Delta p_{AA}=-\frac{2k_A}{kN}}\right)\\=&p_A\sum_{k_A+k_B=k}\frac{2k_A}{kN}\frac{k!}{k_A!k_B!}q_{A|B}^{k_A}q_{B|B}^{k_B}\frac{k_Bg_B}{k_Ag_A+k_Bg_B}\\ =&\frac{2p_A}{kN}\sum_{k_A+k_B=k}\frac{k!}{k_A!k_B!}q_{A|B}^{k_A}q_{B|B}^{k_B}\frac{k_B}{k}+O(w)\\ =&\frac{2(k-1)p_{AB}q_{A|A}}{kN}\sum_{k_A+k_B=k}\frac{(k-2)!}{(k_A-1)!(k_B-1)!}q_{A|B}^{k_A-1}q_{B|B}^{k_B-1}+O(w)\\ =&\frac{2(k-1)p_{AB}q_{A|A}}{kN}(q_{A|B}+q_{B|B})^{k-2}+O(w)\\ =&\frac{2(k-1)p_{AB}q_{A|A}}{kN}+O(w). \end{align*} \] 同样地，默认先排除值为\(0\)的项。将两式做差，即可得到 \[ \begin{align*} &\sum_{k_A+k_B=k}\frac{2k_A}{kN}{\rm Prob}\left({\Delta p_{AA}=\frac{2k_A}{kN}}\right)+\sum_{k_A+k_B=k}\left(-\frac{2k_A}{kN}\right){\rm Prob}\left({\Delta p_{AA}=-\frac{2k_A}{kN}}\right)\\ =&p_{AB}[1+(k-1)(q_{A|B}-q_{A|A})]+O(w), \end{align*} \] 这即原文式(12)。
原文式(21)
令\(p=\frac{ {\rm d}\phi(y)}{ {\rm d} y}\)，原文式(20)化为参数分离方程，从而有 \[ p=\exp\set{-\frac{wN}{k}\left(\frac{\alpha}{2}y^2+\beta y\right)}. \] 当\(w\to0\)时，有
\[ p=\left[1-\frac{wN}{k}\left(\frac{\alpha}{2}y^2+\beta y\right)\right]+O(y^2). \] 两边积分得 \[ \phi(y)=y-\frac{wN}{6k}\left({\alpha}y^3+3\beta y^2\right)+O(y). \] 再考虑初值\(\phi(0)=0\)和\(\phi(1)=1\)（即没有\(A\)时无法扩散和全为\(A\)时一定能扩散），由此对\(O(y)\)项近似，即可得到原文式(21)。