Summary of The Theory of Learning in Games by Fudenberg

First, the scope and assumptions of the question of learning in games.

Second, several learning models.

  1. Pure Strategy Best Response Equilibrium and Best Response Dynamics
  2. \[S^{i} = BR^{i}\left(S^{-i}\right)\]
    and
    \[S^{i}\left(t+1\right) = BR^{i}\left(S^{-i}\left(t\right)\right)\]
    Where \(S^{i}\) is the pure strategy of player \(i\) and \(S^{-i}\) is the pure strategy state of players other than the player \(i\)

  3. Mixed Strategy Best Response Equilibrium (Nash Equilibrium) and Best Response Dynamics
  4. \[\rho^{i} = BR^{i}\left(\rho^{-i}\right)\]
    and
    \[\rho^{i}\left(t+1\right) = BR^{i}\left(\rho^{-i}\left(t\right)\right)\]
    Where \(\rho^{i}\) is the mixed strategy of player \(i\) and \(\rho^{-i}\) is the pure strategy state of players other than the player \(i\)

  5. Pure Strategy Fictitious Player
  6. \[S^{i}\left(t+1\right) = BR^{i}\left(\rho^{-i, E}\left(t\right)\right)\]
    Where \(\rho^{-i,E}\) is the empirical distribution of strategies of players other than the player \(i\) from the whole history, or certain length of the previous actions

  7. Replicator Dynamics, mimicking the best or the better
  8. \[Prob\left(S^{i}\left(t+1\right)=S^{j}\left(t\right)\right) = \delta_{E^j\left(t\right), Max\left(E^{1}\left(t\right), \cdots, E^{i}\left(t\right), \cdots, E^{N}\left(t\right)\right)}\]
    or
    \[Prob\left(S^{i}\left(t+1\right)=S^{j}\left(t\right)\right) \propto e^{\beta\left(E^{j}\left(t\right)-E^{i}\left(t\right)\right)}\]

  9. Pure Strategy Smoothed Best Response Equilibrium and Best Response Dynamics
  10. \[S^{i} = \bar{BR}^{i}\left(S^{-i}\right)\]
    and
    \[S^{i}\left(t+1\right) = \bar{BR}^{i}\left(S^{-i}\left(t\right)\right)\]
    where
    \[\bar{BR}^{i}\left(\rho^{-i}\right)\propto e^{\beta E\left(s^{i},\rho^{-i}\right)}\]
    is a probability distribution of player \(i\)’s strategies and \(S^{i}\) takes one sample from this probability distribution at a time.

  11. Smoothed Fictitious Play
  12. \[S^{i}\left(t+1\right) = \bar{BR}^{i}\left(\rho^{-i, E}\left(t\right)\right)\]
    Again \(S^{i}\) takes one sample from this probability distribution at a time.

  13. Here comes something that is natural but not in the book: Quantal Response Equilibrium (QRE) and Dynamical QRE, or mixed strategy smoothed best response and its dynamical version
  14. \[\rho^{i} = \bar{BR}^{i}\left(\rho^{-i}\right)\]
    and
    \[\rho^{i}\left(t+1\right) = \bar{BR}^{i}\left(\rho^{-i}\left(t\right)\right)\]
    What it does is to simply replace the static/dynamical mixed best response by static/dynamical mixed smoothed best response. This is what we have done in this field: Dynamical QRE and its stability.

  15. In principle, one can also have mixed fictitious play with smoothed best response
  16. \[\rho^{i}\left(t+1\right) = \bar{BR}^{i}\left(\rho^{-i,E}\left(t\right)\right)\]
    where \(\rho^{-i,E}\left(t\right)\) is some kind of empirical distribution of strategies of players other than player \(i\). For example, one approach can be taking average of all historical \(\rho^{j}\left(\tau<t+1\right)\)s,
    \[\rho^{j,E}\left(t\right) = \sum_{\tau<t+1}\frac{\rho^{j}\left(\tau\right)}{t}.\]
    Not sure this has been discussed by others or not.

All the above models can be simultaneously updated or alternatively updated.

科学家中的社会学习

考虑科学家采用其他人提出的科学方法或者科学概念这样一件事情。我们注意到:第一、非常原创性的工作在短期内比较难以得到大家的采用;第二、原创性不高的跟踪性的工作往往更容易发表和得到采用;第三、原创性高的工作最后还是会扩散开来。

问:如何描述这件事情,扩散和得到采用的时间等取决于什么因素。

模型:我们把科学家分成三种:聪明的,一般的和傻的。一个工作会释放一个隐藏的私人信号给每一位科学家,p的几率这个信号就是这个工作的价值。这个p的取值对于三类科学家是不一样的,例如0.8、0.5、0.4。但是所有的科学家都相信自己的聪明的,于是主观认为自己的p=0.8。每一个科学家的类型是隐藏信息,其他人不知道,自己也不知道(可以考虑让科学家自己知道)。但是,科学家分三类以及各个类别的比例是公共知识。对于上帝(这个模型的设计者)来说,每一个科学家的类型是确定的,随机分配以后定下来的。

一个科学家如果有了对一个科学工作的判断,那么判断和实际一样的时候得到收益T,否则损失收益T。

现在再加上一个收益机制:聪明的科学家,尽管是隐藏的,喜欢在少数派里面,收益增加M;傻的科学家喜欢在多数派里面,收益增加M;一般的科学家,无所谓,收益不增加和减少。

看一看这个动力学。如果我们把一般的和傻的合并为一般的,结果会改变吗?如果只有一个群体,那么按照社会学习的已有结果,正确的或者错误的信息塌缩都是可能的。多个群体呢?没准科学的扩散与传播需要多个群体?

复杂性研究讨论班

刚刚结束的科学学讨论班很好。我很有收获。

大家看一下这个文献,

Complex Systems: A Survey by MEJ Newman

然后做一下其中最主要的推荐文献的阅读。我准备最近按照这个大纲做一个复杂性研究的讨论班。拓宽视野、学习基本概念和基本的技术、获得研究经验,对于科学家的培养来说都是必不可少的。

广义投入产出分析和细节投入产出分析

希望解决的根本问题:

  1. 产业部门之间的相互关系1。如果我们希望某个产业部门的总产出(包含中间消耗)或者是净产出(不包含中间消耗,只计算直接消费)有一个单位的增加,我们需要增加的各个其他产业部门的总投入或者净投入(不包含通过中间生产过程得到的投入)是多少。例如,在包含最终消费和劳动力的开放系统的投入产出中,这个问题就是:为了得到最终消费的某一个产品的一个单位的增加,需要劳动力部门在各个产业上增加多少投入。在封闭系统中,这个问题如何回答还不知道。
  2. 产业部门之间的相互关系2。如果我们减少某个产业部门的总投入(包含中间投入)或者是净投入(不包含中间投入,只计算直接投入)一个单位,各个其他产业部门的净产出(不包含通过投入给中间生产过程的部分)和总产出是多少。例如,在包含最终消费和劳动力的开放系统的投入产出中,这个问题就是:减少劳动力部门在某个产业上的投入一个单位,所有产品的总产量和净产量如何变化。
  3. 产业部门之间的相互关系3。如果我们希望在整个系统中去掉某个产业部门,整个系统中受影响最大的部门是哪一个?
  4. 产业部门的影响力度量。哪一个产业部门对整个系统最重要?

这些问题可以通过投入产出矩阵(总投入与总投入之间的关系或者总产出与总产出之间的关系),也可以通过概率转移矩阵(总投入与总产出之间的关系,或者总产出与总投入之间的关系)来讨论。数学手段不一样,包含的信息应该是一样的。

所有的投入产出分析从这里开始:给定一个产业部门的集合\(\left\{j=1,\cdots,N\right\}\),每一个部门之间的投入产出绝对量\(\left\{x^{i}_{j}\right\}\),表示部门\(i\)投入到部门\(j\)的产品\(i\)的数量。这里产品和部门相互认同。我们会讨论部门和产品有区别的更加细节的投入产出分析。

我们可以定义:

  1. 反向投入产出矩阵
    \[B^{i}_{j}=\frac{x^{i}_{j}}{X^{j}},\hspace{2cm} (1)\]
    其中\(X^{i}=\sum_{j=1}^{N}x^{i}_{j}\)。于是,我们有
    \[\sum_{j=1}^{N}B^{i}_{j}X^{j}=X^{i}\Longrightarrow B^{a}_{b}X^{b}=X^{a},\hspace{2cm} (2)\]
    从这里我们看出来,\(B\)的右本征向量是平庸的,就是\(X^{a}\)。

    如果我们在取和中去掉其中的某一个部门\(k\),则
    \[\sum_{j\neq k}B^{i}_{j}X^{j}+x^{i}_{k}=X^{i}\Longrightarrow B^{\left(-k\right)}X^{\left(-k\right)}+Y_{\left(k\right)} = X^{\left(-k\right)}. \]
    于是,
    \[X^{\left(-k\right)} = \left(1-B^{\left(-k\right)}\right)^{-1}Y_{\left(k\right)}, \hspace{2cm} (12)\]
    并且
    \[X^{k} = \sum_{j\neq k}B^{k}_{j}X^{\left(-k\right),j}+x^{k}_{k}. \]
    这里的方程(12)就是Loentief投入产出的核心公式。在那里,通常把部门\(k\)取作最终需求部门\(N\)。这个表达式可以用来回答预期\(k\)部门的产能有一个单位的增加的情况下,系统的其他部门的产能如何变化。在这个条件下,我们能够计算出来所有的\(\Delta x^{i}_{j}\)于是也就得到了所有的\(\Delta X_{j}\),所有部门的需要的投入的增量。这样,我们就相当于回答了:如果需要增加\(k\)部门的一个单位净产出,需要的各部门的总投入是多少。如果我们还能够知道初期额外投入的多少就更好了,也就是去掉中间生产过程产生的投入。有可能把\(F\)和\(B\)合起来可以解决这个问题。

  2. 正向投入产出矩阵
    \[F^{i}_{j}=\frac{x^{i}_{j}}{X_{i}},\hspace{2cm} (3)\]
    其中\(X_{i}=\sum_{j=1}^{N}x^{j}_{i}\)。相应地,我们有
    \[\sum_{j=1}^{N}X_{i}F^{i}_{j}=X_{j}\Longrightarrow X_{a}F^{a}_{b}=X_{b},\hspace{2cm} (4)\]
    从这里我们看出来,\(F\)的左本征向量是平庸的,就是\(X_{a}\)。
  3. 正向概率转移矩阵
    \[MF^{i}_{j}=\frac{x^{i}_{j}}{X_{j}}.\hspace{2cm} (5)\]
    如果我们还是照着上面的方式企图写出本征向量的形式,我们有
    \[\sum_{j=1}^{N}MF^{i}_{j}X_{j}=X^{i}.\hspace{2cm} (6)\]
    这个是矢量和对偶矢量之间的关系,而不是同类型的矢量之间的关系。把一个投入向量变成一个产出向量。同时,我们发现这个矩阵的左右本征矢量可能都不是平庸的。
  4. 反向概率转移矩阵
    \[MB^{i}_{j}=\frac{x^{i}_{j}}{X^{i}}.\hspace{2cm} (7)\]
    如果我们还是照着上面的方式企图写出本征向量的形式,我们有
    \[\sum_{i=1}^{N}X^{i}MB^{i}_{j}=X_{j}.\hspace{2cm} (8)\]
    它把一个产出向量变成一个投入向量。同时,我们发现这个矩阵的左右本征矢量可能都不是平庸的。

有了这四个定义,我们可以问\(B\)的左本征矢量、\(F\)的右本征矢量、\(MF\)和\(MB\)的左右本征矢量有什么含义,我们还可以讨论如何把平庸的关系(2)和(4)变得有用。由于概率转移矩阵的特点,在这里我们仅仅讨论最大本征值,也就是\(1\)所对应的本征向量。
\[\tilde{P}B=\tilde{P}\Longrightarrow \sum_{i}\tilde{P}_{i}\frac{x^{i}_{j}}{X^{j}} = \tilde{P}_{j} \Longrightarrow \sum_{i}X^{i}\tilde{P}_{i}\frac{x^{i}_{j}}{X^{i}} = X^{j}\tilde{P}_{j} \Longrightarrow P_{a} MB^{a}_{b} = P_{b}. (9)\]
于是\(B\)的左本征矢量与\(MB\)的左本征矢量是一样的(差一个常数)。同理可以把\(F\)的右本征矢量与\(MF\)的右本征矢量联系起来。

现在我们来看\(MB\)的右本征矢,假设为\(W\),则
\[\sum_{j}\frac{x^{i}_{j}}{X^{i}}W^{j} = W^{i} \Longrightarrow \sum_{j}x^{i}_{j}W^{j} = X^{i}W^{i} \Longrightarrow W^{j} = 1. \]
于是,我们发现\(MB\)的右本征矢是平庸的。同理,\(MF\)的左本征矢也是平庸的。

总结一下:四种归一化方法定义了矩阵\(B,F,MB,MF\),其中\(B\)的右本征矢和\(MB\)的右本征矢是平庸的、\(F\)的左本征矢和\(MF\)的左本征矢是平庸的,\(B\)的左本征矢和\(MB\)的左本征矢认同,\(F\)的右本征矢和\(MF\)的右本征矢认同。

也就是说,对于通常的投入产出分析矩阵,如果我们计算本征矢量而不是线性方程(参考投入产出矩阵分析的主要思想小结),那么这个本征矢量和稳定概率分布是一个东西(差一个常数),而后者是PageRank算法的基础。

这个时候,我们再来考虑去掉一行一列的本征向量的含义就比较清楚了。以这个为基础,我们可以讨论两个产业部门的关系,以及每一个产业部门的重要性衡量。

细节的投入产出分析,也就是考虑到产品之间的配比的投入产出分析(举例来说,一斤面粉和半斤水生产一斤面包和半斤脏水,如果需要增加面包产量一斤,实际上就意味着增加脏水半斤。这个面包和脏水之间不是简单的投入产出关系,而是共同生产关系。这个关系没有被通常的投入产出考虑进来),需要考虑两个矩阵\({L_{\alpha}}^{j}\)和\(R_{\alpha,j}\),分别表示发生一次工艺\(\alpha\)的生产需要和产生\(j\)产品的数量。如果我们知道这个时间内每一个生产部门的生产的次数\(V^{\alpha}\),那么我们就可以计算总需求和总产出分别为,
\[X^{j}=\sum_{\alpha}L_{\alpha}^{j}V^{\alpha}, \hspace{2cm} (10)\]
为产品\(j\)投入到所有产业的总和。
\[X_{j}=\sum_{\alpha}R_{\alpha,j}V^{\alpha}, \hspace{2cm} (11)\]
为所有产业生产出来的产品\(j\)总和。

当假设一个产业部门只生产一样产品的时候,\(R_{\alpha,j}=\delta_{\alpha,j}\),于是\(X_{j}=V^{\alpha}\),于是,公式(10)成为
\[X^{j}=\sum_{i}L_{i}^{j}X_{i}. \hspace{2cm} (13)\]
这个时候,可以看出来,\(L\)与\(MF\)相当。对于这个生产过程,可以存在多种理解。例如,给定投入向量\(X^{a}\),我们希望得到最优的产出向量。例如,我们要求投入向量实际上来自于产出向量。例如,给定总价格和投入资金,我们希望得到最优的产出值。所有的这些问题都可以用这个\(L\)和\(R\)的数学模型来描述。

对于一个封闭系统(总投入等于总产出),则
\[\sum_{\alpha}L_{\alpha}^{j}V^{\alpha} = \sum_{\alpha}R_{\alpha,j}V^{\alpha} \Longrightarrow \sum_{\alpha}\left(L_{\alpha}^{j}-R_{\alpha,j}\right)V^{\alpha}=0 , \hspace{2cm} (14)\]
对于一个开放系统系统(总投入不等于总产出,但是外界输出已知),则
\[\sum_{\alpha}\left(L_{\alpha}^{j} – R_{\alpha,j}\right)V^{\alpha} = b^{j}. \hspace{2cm} (15)\]
这两个方程意味着,为了满足外界的需求,各个部门的生产频率是受约束的(如果能够完全确定下来就更好了。通常做不到,因为方程不是方的)。

回到化学反应网络的层次,\(L\)和\(R\)被合起来称为化学反应系数矩阵\(S\),相当于把\(L\)当作负的\(R\)当作正的,一起叫做\(S\)。这个时候系统的行为完全由如下微分方程描述,
\[\frac{d}{dt} X_{i} = \sum_{r=1}^{M} \kappa^{r}\Pi_{j=1}^{N} \left(X_{j}\right)^{\frac{\left|S_{r}^{j}\right| – S_{r}^{j}}{2}}S_{r}^{i}, \hspace{2cm} (16)\]
其中\(\kappa^{r}\)是化学反应速率常数(外生变量)。联系两个公式,我们发现,实际上,相当于
\[ \kappa^{r}\Pi_{j=1}^{N} \left(X_{j}\right)^{\frac{\left|S_{r}^{j}\right| – S_{r}^{j}}{2}} = V^{r}.\hspace{2cm} (17)\]

这也就是说,尽管整个化学反应是由外生变量系数矩阵\(S\)和外生变量反应速率矢量\(\kappa\)所决定的一个系统,但是,一定程度上说,例如优化进化的结果使得系统出于平衡的封闭系统状态或者外界输出一定的开放系统的状态(还可以有其他的约束和优化目标,例如经济学的最大利润目标),速率矢量\(\kappa\)也是,一个由\(S\)(加上\(b\)在开放系统中)决定的,适合这个\(S\)的满足一些额外约束和最大化某些额外目标的,参数。

于是,整个问题的研究可以走两条路:第一,在外生变量\(\kappa\)完全已知的情况下,用公式(16)讨论时间演化的过程和演化的结果;第二,通过\(S\)(按照公式(14)加上其他约束)来确定\(V\)从而也确定\(\kappa\),接着得到\(X\)。前者就是化学反应网络和微分方程的方式。后者被称为化学反应网络和流平衡分析(Flux Balanced Analysis)。

在第一个数学模型中(暂时忽略\(b\)的问题,当作封闭系统),研究某个物种多了少了对其他的影响非常简单,只要放到微分方程中去演化一下得到一个定态末状态就行了。但是,这样就需要\(\kappa\)这一外生变量。

在第二个数学模型中,对于某个化学反应(产业部门)的重要性就比较容易讨论,例如\(S\)中去掉某一个列(反应角标\(r\)),然后就可以讨论这个时候的\(V\),并且进而得到这个时候的\(X\)。但是,如何讨论某一个\(X_j\)对一个\(X_k\)的影响呢?

可以考虑这样:在满足约束(例如\(X_j\)最大值约束)的情况下,在同样的\(S\)的情况下,使得某个类似的目标最大的这样的\(V\),然后从\(V\)得到\(X\),来得到\(X_j\)对\(X_k\)的影响。

可以尝试。由于这个流平衡分析与化学反应、基因网络联系更紧密,可以考虑,先用这样的体系做例子,来发展方法,然后,回到经济学和科学计量学。

2014年复杂系统暑期学校报告

Learned something new about Bayesian formula last night and learned the hard way

Bayesian formula,
[P(A|B)=\frac{P(B|A)P(A)}{P(B|A)P(A)+P(B|\bar{A})P(\bar{A})}]
is conceptually straightforward, but amazingly useful in statistics. It turns calculation of (P(A|B)) into finding out (P(B|A)) by simply making use of the rule of total probability,
[P(A\cap B) = P(A|B)P(B) = P(B|A)P(A)]
and
[P(A) = P(A\cap B) + P(A\cap \bar{B}). ]

This seems rather trivial to me. Here comes the surprising part. Let us now add another set (C) in the following way,
[P\left(A|B\right) = P\left(\left(A|C\right)|B\right)P\left(C|B\right) + P\left(\left(A|\bar{C}\right)|B\right)P\left(\bar{C}|B\right), \hspace{2cm} (1)]
or in this way,
[P\left(A|B\right) = P\left(\left(A|B\right)|C\right)P\left(C\right) + P\left(\left(A|B\right)|\bar{C}\right)P\left(\bar{C}\right). \hspace{2cm} (2)]

Now let us ask which one of the above two formulae is the proper one, or both, or none?

It is easy to verify the first one: Assuming
[P\left(\left(A|C\right)|B\right) = P\left(A|\left(C,B\right)\right) = \frac{A\cap B \cap C}{B \cap C}, \hspace{2cm} (3)]
then right-hand side of Equ(1) becomes
[\frac{A\cap B \cap C}{B \cap C}\frac{B\cap C}{B} + \frac{A\cap B \cap \bar{C}}{B \cap \bar{C}}\frac{B\cap \bar{C}}{B} = \frac{A\cap B \cap C}{B} + \frac{A\cap B \cap \bar{C}}{B} = \frac{A\cap B}{B}, \hspace{1cm} (4)]
which is exactly the left-hand side of Equ(1).

Verifying Equ(2) is however not easy. If the assumption in Equ(3) is right, then Equ(2) becomes
[\frac{A\cap B \cap C}{B \cap C}\frac{C}{\Omega} + \frac{A\cap B \cap \bar{C}}{B \cap \bar{C}}\frac{\bar{C}}{\Omega}. \hspace{1cm} (4)]
I can see no clue that this expression should be (\frac{A\cap B}{B}).

However, if (P\left(A|B\right)) is the probability of a set of events, then the second one should be correct too. So what is the problem? It seems to me that when discussing (P\left(A|B\right)), we have implicitly limited the whole set, which originally is (\Omega), to be (B), therefore, all the expressions derived from there should have carried the condition (B) forever. So lesson one: Keeping the condition (B) as the condition for all other events. Therefore, Equ(1), not Equ(2), should be used in our case.

Another lesson learned is that conditional probability is a tricky concept and one has to deal it with extra attention.