支持学习的社交网络

例2.2中的名人图可能会导致一个猜想，即平等主义社会不能聚合信息，因为一个人需要在先验网络中指定少数代理人（如名人）来学习传播。本节的主要结果表明，这种直觉是错误的，对称网络可以支持学习。在第5节中，我们将通过展示学习的稳健性来加强这一结果。定理4.1。对于任意p>和任意δ>0，存在一个对称网络G=(V,E）使得每个agent的学习质量Lσ(v)≥1-δ，任何校正信号的概率p>p和任何状态对称平衡σ。为了证明定理4.1，我们使用扩张器理论的经典结果来构造网络，其中每个agent的局部学习要求都满足。我们需要下面的引理，它简化了对局部学习要求的检查。回想一下网络g的周长g是最短周期的长度；树的围长为g=+∞引理4.1。考虑一个周长为G且最大次为d的网络G，在这样的网络中，任何一个agent v用参数d,jg-3k,d满足局部学习要求，其中d是一个数，使得v至少有d个d次或更多的友元。在数学文献中，这类图通常称为传递图，因为自同构群在它们上是行动的；即任意一对顶点之间存在自同构映射。该定理推广到非状态对称平衡点，其代价是假定信号是足够信息量的，即P>。这个和其他扩展在6.2节中讨论。证明。让你，你，。...udbe v的朋友，其度数为deg(ui)≥D。回想一下，Br,G\\v(u)表示网络中u的R邻域，在这里agent v被消除了。对于I6=J,我们的目标是选择Br,G\\v(ui)和Br,G\\v(uj)不相交的Rsuce。如果Br,G\\v(ui)和Br,G\\v(uj)相交，这就产生了一个长度为2R+2（或更短）的循环：从v开始，然后到ui，然后通过最短的路径到达交点，然后再通过最短的路径到达uj，然后回到v，因此只有当2R+2≥G时，交点才可能存在。因此选择r使得2r+2<g，从而保证r邻域是不相交的；r=jg-3ki是这样的最大r。通过引理4.1和定理3.1，证明定理4.1归结为具有任意高次和高周长的对称D-正则网络的存在性问题。扩张器理论证明了这种网络的存在性；见附录A。以下是Lubotzky等人的定理的推论。[1988]（附录A中的定理A.1）描述了一族所谓的Ramanujan展开式。推论4.1(Lubotzky等人[1988]的定理A.1）。存在一个序列DK→∞,即对于任意gand k,存在一个对称的DK-正则网络G=(V,E）,使得围长G≥gand且λ≤2√DK-1,其中λ是邻接矩阵的第二大特征值。经过这些初步的证明，定理4.1变得容易了。定理4.1的证明。对于周长为g的D-正则网络，定理3.1与引理4.1结合，给出了任意Agent v和任意状态对称平衡σ的学习质量Lσ(v)≥1-δp，D，jg-3k，D的一个下界。推论4.1允许我们选择具有任意高脱脂率和任意高周长/度比D的对称D-正则网络g，而推论3.1则表明，如果周长g和度都趋于正常，且周长更快地达到正常，则δp，D，jg-3k，D趋于零:GD→∞。因此，对于任意给定的δ和p，我们可以选择G是具有D和G的对称D-正则网络，使得δp,D,jg-3k,D≤δ。由于δ在p中是递减的，我们得到了对于任意p≥p的δp,D,jg-3k,D≤δp,D,jg-3k,D≤δ。

因此，网络G满足定理4.1.5含义的陈述：鲁棒学习我们讨论了当一些智能体不感兴趣或不可用，因此不参与学习过程时网络的学习质量。名人图（示例2.2）表明，高学习质量可能非常脆弱：如果名人（群体中的一小部分）没有出现，这将使网络完全断开，信息聚合崩溃。我们证明了存在支持鲁棒学习的网络，即不存在这样的缺陷。在第四节中，我们看到具有高次而不是短周期的对称稀疏网络支持学习。在这样的网络中，所有的Agent扮演着相同的角色，这使得人们自然地期望在这些网络中没有一小群Agent是关键的；特别是，一个小群体的对抗式淘汰不能显著破坏学习结果。在这里，我们得到了一个令人惊讶的更强的结果，证明了存在一个对称网络，它的收益对任何群的对抗消去都是鲁棒的，甚至是一个大群。我们在第四节中没有使用λ上的界；特别地，对于定理4.1的证明，任何具有大D和大Girths的D-正则网络都将得到证明。λ上的界对于第5节中关于鲁棒学习的讨论至关重要。定理5.1。对于任一p>和任一δ>0，存在一个对称网络G=(V,E）,使得对于任一α∈(0,1]和任一具有α·V代理的子集V=V,对于任一状态对称平衡和任一错误信号概率，P>p,诱导子网络的学习质量至少为1-δα,学习的鲁棒性与网络的谱性质有关。下面的引理5.1抓住了这一点，定理5.1很容易从这个引理和展开图上的已知结果结合起来。考虑一个D-正则网络，用λ≥λ≥...≥λv其邻接矩阵的特征值按绝对值排序。λ相对于λ较小的扩展网络；参见附录A。下一个引理给出了学习质量下降的范围，如果我们考虑的是它的任意子网络，而不是原来的D-正则网络。引理5.1。设G=(V,E）是周长G的D-正则网络，特征值λ次大。然后，对于任意α∈(0,1]和任意大小为V=α·V的子集V1v，对于任意状态对称平衡σ，σGV≥1-√α+(1-α)λα·D·δp,D,jg-3k,D(5.1)的学习性质为导出的子网络GVsatieslσGV≥1-√α+(1-α)λα·D·δp,D,jg-3k,D(5.1)。这里δ(p，d，r，d)由公式（3.3）给出，引理5.1在附录d中得到证明；这里我们给出了定理5.1的主要思想，然后证明了定理5.1。引理5.1的证明简略。关键的工具是扩张器理论中的混合引理（引理A.1)。该引理适用于任何D-正则网络，并以λ的形式给出了任意两个不相交的顶点子集V,V之间的边数E(V，V)与Erdos-Renyi模型中的期望边数E(V，V)-dv·V·V≤λPVV的偏差。（5.2）这个引理允许我们对GV中的低次因子的分数进行约束。事实上，对于γ<α，设Vbe是GVA中度数小于γ·D的Agent集合，而Vbe是消除Agent的集合V\\V。由于每个agent在原网络G中都有度D，所以V-V之间至少存在(1-γ)DV边。Erdos-Renyi模型规定了(1-α)DV边。这种差异仅适用于相对较小的子集。通过附录中的引理D1，高次智能体分数的下界暗示了具有大量高次友元的智能体数目的界：具有至少γD个友元且具有γD个以上的智能体的分数大于1-2θ,其中θ=θ(α，D，γ，λ)。我们得到了GV中具有γ·D个以上的智能体的分数至少大于1-θ,其中θ=θ(α，D，γ，λ)是最小的。在GV中，高次智能体分数的下界意味着具有大量高次友元的智能体数目的下界。

根据引理4.1，每一个这样的智能体都用参数γd，jg-3k，γd来满足局部学习要求。定理3.1在这组主体上的应用完成了定理5.1的证明。正如在定理4.1的证明中，我们可以选择Ramanujan展开式，使得δp，D，jg-3k，D至多为δ。Ramanujan展开式的第二特征值λ≤2‰d-1≤2‰D（推论4.1）,因此，由引理5.1,任何具有V=α·V的子网络GV，其学习质量至少为1-α+4(1-α)α‰D≤α+α≤α和δp，D，jg-3k,D。类似于第3和第4节，该结果推广到要求p>下的非状态对称平衡点。由于α+4(1-α)α‰D≤α+α≤α和δp，D，jg-3k,D≤δp，D，jg-3k,D，学习质量从下到下为1-δα界。注5.1（随机化鲁棒性）。我们可以考虑一个较弱的概念来代替对抗消除的鲁棒性：一个智能体子集被随机删除，并且该网络必须支持对该子集的选择具有高概率的学习。在附录E中，我们出人意料地表明，任何支持学习的网络都具有随机鲁棒性。例如，在名人图中，如果随机删除大量的agents，例如50%,那么大约50%的名人将留在网络中，从而保证信息的聚集（学习质量略低）。更正式地，对于一个网络G=(V,E）考虑一个诱导子网络GV，其中vs是Dα·ve agents的一致随机集合。在一个附加的技术假设下，我们证明了对于V的选择，L(GV)≥1-q1-L(G)α，概率至少为1-q1-L(G)α（定理E.1)；这里L(G)=maxσLσ(G)表示最佳平衡点的学习质量。随机鲁棒性之所以成立，是因为在某种意义上，它与随机到达顺序的学习质量有关。事实上，如果一个网络能很好地为其他竞争对手的订单聚合信息，那么，对于大多数这样的网络，这些Dα·V·e到达的子网络也必须能很好地聚合信息。定理E.1的证明是基于子集的回声与原网络中的学习过程之间的这种耦合。6讨论在6.1节中，我们提出了两种不同的方法来理解对称网络中的学习结果（第4节）和鲁棒学习结果（第5节）。首先，我们介绍了networkdesigner的视角，然后解释了这一观点与经典社会学理论的联系。6.2节讨论了我们的技术假设和如何放松。6.1结果的替代解释网络设计者视角考虑一个想要进行社会学习的社会网络设计者。Sgroi[2002]构建了一个支持特定arrivalorder学习的网络，Bahar等人。[2020]提出名人图作为支持学习和对智能体到达顺序鲁棒的网络。然而，名人图只支持学习，如果所有代理都真正参与并做出决定。换句话说，如果少数智能体不关心手头的决策，因此不活跃，那么学习可能会失败。与此相反，我们从定理5.1得到的基于扩展器的网络给出了一个支持学习的社会结构，并且对到达顺序和实际的主动代理人子集都是鲁棒的。在实践中，社会网络不是从头开始设计的，社会联系可以被认为是给定的。然而，互联网上的社交网络通常与推荐系统相结合，该系统决定向特定用户展示哪些新闻。在这样做的时候，它可以通过隐藏一些朋友的消息和可能显示一些非朋友的消息来干预社会关系的结构。

我们的局部学习要求（定理3.1）结合引理4.1提出了一个提高整体学习质量的可能方法：消除短的周期，同时保持一个agent所服从的信息源的高数量。然而，这一建议需要额外的经验评估。两步信息链范式Katz和Lazarsfeld[1955]的经典社会学理论“两步信息链”传达了这样一个观点，即学习总是由一小群意见领袖促进的，即在由网络结构预先确定的代理中。理论的原始版本，制定于电视网的黄金时代，认为尽管这些网络负责引发新想法和介绍新产品，但这些内容被大多数人以间接的方式消费。换句话说，人们的行为，无论是采用新产品还是投票给一个政治候选人，与其说是他们从电视网络上听到的，不如说是他们从直接消费这些内容的代理人那里听到的。让我们在网络中召集一组代理人，如果这个群体出现时网络支持学习，而不是在不存在时未能聚合信息。例子2.2名人图中的名人群体就是一个例子。两步信息网络理论表明，支持学习的网络包含了一个少数群体，它在网络上的信息传播中起着中介作用。第4节和第5节的结果对本文（在我们的程式化理论模型中）提出了挑战：在先验对称网络中可以获得高的学习质量，因此，没有一组Agent是由网络结构预先确定的；6.2摆脱技术假设，我们的一些建模假设是为了简化描述，并且易于放松。到达时间的一般分布我们假设Agent的到达时间是I.I.D，特别是在单位区间上均匀分布。然而，任何非原子分布都导致一个等效模型（等效性是通过单调重参数化得到的），只要I.I.D.假设得到维持。一个重要的鲁棒性结果是将我们的结论推广到某种近似的I.I.D.概念。对于非二进制信号，我们的结果对于任何非二进制信号设备都是成立的，只要信号是信息的，并且保持对称性。所谓信息性，是指对于一个信号的正概率集合s，后子P(θ=1s)属于区间[0,1-P][P,1]的并集（这组信号的概率将进入学习质量的界）。所谓对称性，是指后子P(θ=1s)的分布在附近是对称的。注意，也允许无界精度的信号。异构agents agents可以是异构的，即信号设备可以是不同的，因此每个AgentV都有自己的信号精度PV。在这种情况下，所有的结果都符合p=minv∈vpv。非对称平衡点，平衡点和信号的对称性假设可以放松。然而，对于非对称平衡，定理3.1，4.1和5.1要求正确信号的概率大于（而不是）。其原因是不等式(c.1)，对于非对称平衡，我们在括号中得到2(1-p)。一般状态推广到非等概然状态是很简单的。然而，请注意，这打破了平衡的状态对称性，因此，我们在不等式(c.1)中得到2(1-p)（见上面的注释）。

扩展到非二进制状态并不会导致任何额外的技术缺陷。如果除了观察他的朋友的行为之外，每个代理v还获得了关于他实现的子网GV,T的一些信息，例如，关于代理集合的可能噪声信号、它们的到达时间、行为以及它们的私人信号，则第3、4和5节的结果成立。较少信息的代理所有我们的结果都可以很容易地适应这样的情况，即观察朋友的行为是噪声的。也就是说，每个agent v不是观察他的friendu∈Fv，T的动作Au，而是观察概率为1-ε的Au，或者观察概率为ε的proped动作1-Au。我们可以考虑这个模型的两个变体：u的作用在同一时间对他的所有邻居起作用，但在u∈V上独立地起作用，或者该作用在eachpair（V,u）上独立地起作用。这两个变体在第3、4和5节中都需要相同的直截了当的修改。它们源于定理3.1证明中的一个小调整：当应用公式(C.3)中的Hoe-ding不等式时，我们将需要v观察到的作用与状态不匹配的概率的上界，而不是P(Au6=θ)的上界。latterprobability等于(1-ε)P(Au6=θ)+ε(1-P(Au6=θ))，且不超过(1-ε)P(Au6=θ)+ε，其中P(Au6=θ)可以由引理C.3限定。参考文献Daron Acemoglu,Munther A.Dahleh,Ilan Lobel和Asuman Ozdaglar。社会网络中的贝叶斯学习。《经济研究述评》，2010:78:1-34.Noga Alon,Fan R.K.Chung.显式构造线性大小的容错网络。离散数学，72（1-3）：15-19,1988.Itai Arieli和Manuel Mueller-Frank。多维社会学习。《经济研究综述》，86(3):913-940，2019。Gal Bahar,Itai Arieli,Rann Smorodinsky,Moshe Tennenholtz。多议题社会学习。《数学社会科学》，2020年104:29-39.Abhijit诉Banerjee。一个简单的羊群行为模型。《经济学季刊》，1992，107(3):797-817.苏希尔·比赫钱达尼，大卫·赫什莱弗，伊沃·韦尔奇。关于时尚、时尚、风俗和文化变化的理论。《政治经济学杂志》，100:992-1026，1992年。模型错误的信息羊群。《经济理论学报》，2016年163:222-247。泽维尔·达汉。大周长任意次的正则图。组合卡，34(4):407-426，2014。Michal Feldman，Nicole Immorlica，Brendan Lucier和S.Matthew Weinberg。通过非贝叶斯异步学习在社会网络中达成共识。在莱布尼茨国际信息学论文集。Klaus Jansen，Jos\'e Rolim，Nikhil Devanur和Cristopher Moore（编辑），第192-208页。Dagstuhl出版社，2014年。Mira Frick，Ryota Iijima和Yuhta Ishii。误解他人和社会学习的脆弱性。《经济计量学》（即将出版），2020年。本杰明·戈卢布和马修·杰克逊。社会网络中的幼稚学习和人群的智慧。《美国经济杂志：微观经济学》，2(1):112-49，2010。有界随机变量和的概率不等式。在瓦西里·霍丁的著作汇编中，第409-426页。斯普林格，1994年。Shlomo Hoory，Nathan Linial和Avi Wigderson。展开图及其应用。美国数学会公报，43(4):439-561,2006。个人意识：人们在大众传播中所扮演的角色。《自由新闻》，1955年，亚历山大·卢博茨基。纯数学和应用数学中的展开图。美国数学会公报，49(1):113-162，2012.亚历山大·卢博茨基，拉尔夫·菲利普斯，彼得·萨纳克。Ramanujan图。组合科学，8(3):261-277，1988.摩根斯坦。对于每一素数幂q,q+1正则Ramanujan图的存在性和显式构造。组合理论学报，B辑，62(1):44-62，1994。Elchanan Mossel,Joe Neeman,Omer Tamuz。

社会网络中的多数动力与信息聚合。自治代理与多代理系统，28(3):408-429，201 4。Elchanan Mossel,Allan Sly,Omer Tamuz。策略学习与社会网络拓扑。《经济计量学》，83(5):1755-1794，2015.曼努埃尔·穆勒-弗兰克。在社交网络中操纵观点。可在SSRN 3080219,2018.Daniel Sgroi.在群体中优化信息：豚鼠，职业和福利。游戏与经济行为，39:137-166，2002。关于平衡和学习的动态模型的论文。芝加哥大学经济学系博士论文，1991年。扩张者有几种等价的扩张者定义；参见Hoory等人。[2006]。“光谱”识别对我们的需要是最方便的。考虑一个D-正则(deg(v)=D对所有顶点）图G=(v，E)，其邻接矩阵的特征值(λk)k=1,...,v特征值按绝对值λ≥λ≥λ...≥λV。特征值λ=D对应于代表均匀分布的特征向量：第二特征值λ越小，从某个顶点开始的随机游动的分布越快收敛于均匀分布；见命题1.6。在Lubotzky（2012）。图G是展开式，如果λ相对于λ小；即G上的随机游动忘记了起点fast，定理a.1（Lubotzky et al.[1988])。对于D-1是素数且D-2可被4整除的任意N和D,存在至少有N个顶点的D-正则对称图G=(V,E）,λ≤2‰D-1,周长G≥logD-1V。λ≤2‰D-1的图称为Ramanujan图；根据Alon-Boppana定理（参见Hoory et al.[2006]中的定理5.3)，这个λ值本质上是可能的最佳值。最好的展开器不能有短圈，这是很直观的，短圈会导致随机游动中的递归，从而减缓随机游动在图上的展开。定理A.1的证明是相当技术性的，依赖于群论。卢博茨基等人。[1988]及其后继者（如Morgenstern[1994]将整除性条件放宽4和Dahan[2014]将结果推广到任意D≥11)将G构造为某群的Cayley图，虽然这些论文中没有明确地提到所构造图的对称性，但由于任何Cayley图都是对称的，所以它是免费的；参见[Hoory et al.，2006]中的声明11.4。除了大周长之外，我们还需要扩张子的另一个性质来证明它们与Erdos-Renyi模型中的随机图的相似性，其中给定顶点之间的边的概率p等于toDV。对于一对不相交子集V,V covv用E（V,V）表示一个端点在V、另一个端点在V的边集。在Erdos-Renyi模型中，这类边的期望个数等于P·VV。下面的结果称为Mixing引理，它表明扩张器的E(V，V)接近于这个数。引理A.1（混合引理，Alon和Chung[1988])。对于任意一个D-正则图G=(V,E）和任意两个不相交子集V,V→V,V→V成立以下不等式:E(V,V）-dV·V·V≤λPVV.B判定的局部性质我们证明了引理3.1,它保证了所实现的子网络Gv,Tof V在V的邻域半径大于最大次数时可能出现在V的邻域内。事实上，我们证明了一个稍微更一般的陈述，条件是V的到达时间；这是我们在定理3.1的证明中需要的一个技术上的细微差别。引理B.1。v的实现子网包含在v的(R-1)邻域内的概率，以v的到达时间tv为条件，具有以下的下界：p gv,t tun br-1(v)tv≥1-2·e·dr r,(b.1),其中D=maxu∈br(v)deg(u)。引理B.1的证明。

在不失一般性的情况下，我们可以假定r>e·D，因为另有界(B.1)琐碎。v的已实现子网络包含在(R-1）邻域内当且仅当没有路径连接v且在其化网络GT中存在先验网络G中的球面Sr(v)=Br(v)\\Br-1(v)。考虑一个agent u∈Sr(v)，设(v=u,u,u,...,uk=u)是G中连接v和u的路径。该路径在已实现网络GTIS中出现的机会以uk，uk-1的概率为界。.，uarrime完全按照这个顺序（我们排除了代理人u=v，因为我们以他的到达时间为条件）；这个概率是相等的！。v与球体Sr(v)之间的每条路径的长度为k≥r。从v开始的长度为di-herent路径的总数至多为dk，因为对于k个步骤中的每一个步骤，至多有D个选择。因此，根据并界，在其化网络GTis中v与Sr(v)之间最多存在路的几率为∞xk=rdkk！。给定一个群G有一个群运算，且有一个子集S=G，它的Cayley图如下：当u=v=S时，顶点集v与G和vu∈E重合。事实上，对于任意x∈G，映射f(v):v→xàv是Cayley图的自同构。对于任意一对顶点v,v∈v,我们通过选择x=v→V-1,得到了f(v)=v.在cedkk！≤drr！·drk-R中，我们可以用等比数列∞xk=rdkk！≤drr！∞xl=0dr l=drr！·1-dr≤1-e·drr！≤2·drr！来约束该和，其中后两个不等式是由假设r≥e·d和假设1-e≤2得到的。使用不等式n！≥ne→n，我们可以去掉分母中的阶乘:2·d→rr！≤2·e→dr。因此，在概率至少为1-2·e→dr的情况下，在GTor中v和Sr(v)之间没有路径，等价地，Gv,t→br→1(v)。定理3.1的证明由Fdv=(iu)i=1,...,dV的朋友来自局部学习需求的集合和由Fdv，t={u∈Fdv:tu≤tv}其中那些比v早到达的朋友表示。考虑以下v偏离他的平衡作用AV的情况。agent决定依赖于他的朋友Fdv,t：如果他们中的大多数人都参与了动作a∈{0,1}，则agent v重复该动作；在tie或v被隔离的情况下，AV=sv，即v跟随他的信号。在平衡状态下，没有偏差，因此，P(AV=θ)≥P(AV=θ)。可以用Hoe-ding不等式（见脚注5）来估计发生不对称的概率。为了应用Hoe-ding不等式，我们需要动作无关性(au)u∈FDV，t，以及Au6=θ的概率上界。为了使行动独立，我们需要对适当的事件家族进行条件限制。下面的引理描述了期望的事件族并建立了边界。回想一下，Br,G\\V(u)表示由Gr消去V得到的网络中u的R-邻域，用Wv=u∈Fdv，T{Gu,TtuNBR-1,G\\V(u)}表示每个u∈Fdv的实现子网络包含在Br-1,G\\V(u)}中的事件，即Wv=u∈Fdv,T{Gu,TtuNBR-1,G\\V(u)}。注意，在给定Wv的情况下，u∈Fdv的有化子网，有脱节。引理C.1。Fixθ∈{0,1},t∈[0,1],和agent的一个朋友子集F_F__F___________________________________________________________________________________________________________________________________________________它是决策性质的局部性的推论（引理B.1)。引理C.2。根据v及其所有友方的到达时间，Wvconditioned概率的下界为：p Wv tv,(tz)z∈FDV≥1-φ,其中，φ=2d·e·dr r。第三个引理给出了错误行为概率的上界。引理C.3。对于Fdv的任意子集F,一个agent u∈F和任意状态对称平衡，错误行为的条件概率满足以下不等式:p(Au6=θθ=θ,tv=t,Fdv,t=F,Wv)≤1-ρ1-p+t·pdeg(u)-1！，(c.1)其中，φ来自引理c2。在它们的帮助下，我们完成了定理3.1的证明。

根据Hoe-ding不等式和引理C.1和C.3,高态(θ=1)的错误动作概率为:paV6=θθ=1,tv,Fv,T,wv≤pxu∈fdv,tau≤fdv,Tθ=1,tv,Fv,T,wv≤(c2)≤exp-2-1-ρ1-p+tv·√d-1·fdv,T！=(c3)=exp-2p-1-ρ-tv·对于u∈FDV，deg(u)≥d。只有当tvi不太小时，该界限(C.4)才成立：若要应用Hoe-ding不等式，圆括号中的表达式2p-1Ω-t·√d-1，必须是非负的（请参见脚注5中的要求x≥0)。我们将仅对TVV使用界限(C.4)，这样该表达式至少为2p-1Ω，或者等效为TV≥√d-1(2p-1Ω)。对于smalltv,我们粗略地将概率界为1,得到以下对所有tv有效的不等式：p av 6=θθ=1,tv,Fv,T,wv≤1ntv<√d-1(2p-1-'A)o+exp-(2p-1-'A)(1-'A)·fdv,T！，(c.5)其中1是事件的指示符。让我们省去对θ=1,tv,Fv,T和wv的条件。对于θ=0，一个类似地导出相同的界(C.5)，因此，它对θ无条件成立。由于P(·)≤P(·Wv)+(1-P(Wv))，所以我们不必在Wvat上附加增加上界的代价。它仍然是在Fdv，TAN和TV上的平均界限。大小Fdv,T在0,1,上均匀分布。因为它是fdvé{v}的随机排列中v的前项的长度。因此，对(C.5)中的第二个求和进行平均，得到长度d的几何级数。考虑到tvis均匀分布在[0,1]上，并将长度为d的等比数列与innite的等比数列包围，我们得到p(AV6=θ)≤ρ+√d-1(2p-1-ρ)+d+1·1-exp-(2p-1-ρ)(1-ρ)。(c.6)如果我们注意到1-exp(-x)≥x·1-exp(-a)afor x∈[0,a]，这个上界就可以简化。由于2p-1-ψ1-ψ≤1，我们得到了1-exp-(2p-1-ρ)(1-ρ)≤8(1-ρ)1-exp-σ)(2p-1-ρ)≤(2p-1-ρ)，其中在第二个不等式中，我们以1为界(1-ρ)，并使用了1-exp-≥，分别用b和c表示(c.6)中的第二和第三和，我们看到c≤b。对于小于1的b，我们有b≤b，而对于b≥1的界(C.6)无论如何都变得平凡，因此P(AV6=θ)≤ρ+√d-1(2p-1-ψ）。考虑到P(AV=θ)≥P(AV=θ)=1-P(AV6=θ)并代入引理C.2中的表达式，我们完成了定理3.1的证明。引理C.1的证明：为了保证条件独立性，我们利用了agent u∈V的已实现子网络Gu,T=(Vu,T,Eu,T）的以下性质。条件于Gu，T，hisaction auis独立于（sz,az)z∈V\\vu,Tand(tz)z∈V。换句话说，U的行为完全由他所实现的子网络和来自该子网络的智能体信号决定。这一特性有一个重要的后果。考虑一个Agent群Ucovv和一个事件，该事件是由T=(tz)z∈V∈T的集合所决定的，对于某些tcou[0,1]V。当所有已实现的子网络(Gu，T)u∈U)都是条件为{T∈T}的独立不相交随机网络时，我们将证明在给定θ=θ,TV=T,Fdv,T=F和WV的情况下，作用(au)u∈U是条件独立的。通过对Wv的认识，每个ui∈F的实现子网属于Br,G\\V(ui),从而实现子网(Gu，T)u∈Fare不相交。我们还需要检查它们之间的独立性。回想一下，事件wv，其形式是：u∈FDV,T{Gu,ttumbr-1,g\\v(u)}。我们现在检查每个事件{Gu,t=br-1,g\\v(u)}由agents z∈Br,g\\v(u)é{v}的到达时间tzo决定。确实，Gu,t属于br-1,g\\v(u)当且仅当u早于v到达且对于任何路径(u=z,z,z,..）。

,zk）不通过v而连接u和球面Sr,G\\v(u)=Br,G\\v(u)\\Br-1,G\\v(u),存在一个指数i，使得tzi<tzi+1。因此，我们可以将事件{Gu,t=br-1,g\\v(u)}改写为{(tz)z∈br,g\\v(u)-btu(tv)}，其中Tu(tv)是[0,1]br,g\\v(u)-btu(tv)}的一个子集，依赖于v的到达时间。对Fdv,t=F,tv=t的条件化等价于对以下由到达时间决定的事件族的条件化：对于每个u∈F,Tu>t,对于u∈Fdv\\F,tv=t。到达时间(tz)z∈va是无条件独立的，并且该条件限制了不相交子集的值（这里我们使用Br,g\\v(u)对u∈Fdv是不相交的事实）。因此，在Fdv,t=F,tv=t,Wv条件下，ofrandom变量族(tz)z∈br,G\\v(u)是独立于u∈F的。所实现的子网络Gu，Tof u由(tz)z∈br,g\\v(u)决定，因此，网络(Gu，T)u∈fare也是条件独立的，这意味着所期望的作用(au)u∈f的条件独立。引理C.2的证明：回想wv=⑤u∈fdv,T{Gu，Tbr-1,g\\v(u)}并考虑其中一个事件。我们选取了一个具有(c.7)注意，事件{Gu,t=br-1,g\\v(u)}仅由到达时间tzof z∈Br,g\\v(u){v}决定（参见引理C.1证明中的论点）。因此，通过与到达时间无关，我们可以简化条件P gu,T tambr-1,G\\v(u)tv,(tz)z∈fdv=P gu,T tambr-1,G\\v(u)tv,tu,因为fdv{u}óBr,G\\v(u)=é。由于我们以tu为条件，通过知道tvi而添加的唯一信息是，在u到达时，v不存在（回想一下，我们假设tu<tv)。Thusp gu,Ttambr-1,G\\v(u)tv,tu=Pg\\v gu,Ttambr-1,G\\v(u)tu,其中Pg\\v是网络G\\v中关于到达过程的概率。通过应用于网络G\\v中u的引理b1,我们得到Pg\\v gu,Ttambr-1,G\\v(u)tu≥1-2·e·dr r，并推导出(c.7)。引理C.3的证明：在引理C.1的证明中，我们观察到，一旦给定了agent u的实现子网络Gu，to，他的行为就由该子网络中agent的信号决定。我们还看到，在Fdv,t=F,tv=t和Wv的条件下，u∈F的实现子网络是由到达时间(tz)z∈br,G\\v(u)决定的，并且该条件等价于{(tz)z∈br,G\\v(u)btu(t)}（我们使用在证明中引入的符号）。因此，在θ=θ，Fdv，T=F，tv=T和wv，条件下的Gu，T（以及au）的分布与F中的其他代理是相同的。这个观察使我们可以简化条件:P(Au6=θθ=θ,TV=t,Fdv,t=F,Wv)=P(Au6=θθ=θ,Tu<t,v/∈Fu,t,Wv)。该概率可由全概率公式限定为:P(Au6=θtu<t,v/∈Fu,t,Wv)≤P(Au6=θtu<t,v/∈Fu,t)1-ψ(c.8)，下界P(Wv tu,tv)≥1-ψ。我们使用以下观察：对于任何属于agent u信息分区的事件A，错误行为P(Au6=θA)的条件概率至多为1-P。否则，当A出现时，智能体可能会主动偏离其均衡策略，跟随他的信号。事件A={tu<t,v/∈Fu,t}是u不知道的，因为u没有观察到他的到达时间。然而，我们可以近似事件Aby事件A={tu<t,v/∈Fu,t}，其中tu=Fu,Tdeg(u)-1是u到达时间的代理（对于大度代理tu≈tu按大数定律）。Agent u知道A何时发生，因此，P(Au6=θA)≤1-P。

关于Acan的条件概率有界为:P(Au6=θA)≤P(Au6=θ,A)+P(A\\A)P(A)==P(Au6=θA)·P(A)P(A)+P(A\\A)P(A)≤(1-P)·P(A)P(A)+P(A\\A)P(A).概率P(A)=P(tu<t,TV>tu)=ZTDTUZTUDTV=ZT(1-tu)DTU=T-T。为了估计P(A)，我们注意到在tuand>tu的条件下，u观察到的朋友数具有参数deg(u)-1和tu的二项式分布（有deg(u)-1个朋友，并且每个朋友都以概率tu独立地到达时间tu)。通过thehoe jinding不等式，我们getp fu,Tdeg(u)-1≤t tu,对于t≤tup Fu,Tdeg(u)-1≥t tu,t≤exp-2(tu-t)(deg(u)-1),对于t≥tu，v/∈Fu,t≤exp-2(tu-t)(deg(u)-1).现在我们准备估计P(A):P(A)=pFu,Tdeg(u)-1≤t,tv>tu=ZDTVZTVP Fu,Tdeg(u)-1≤t tu,tv>tu dtu≤≤ztdtvztv 1 dtu+ztdtvzt1 dtu+ztdtvztvtexp-2（tu-t）(deg(u)-1）？dtu≤≤t+t(1-t)+z-∞exp-2 s（deg(u)-1）？ds=t-t+rπ8（deg(u)-1）。类似地，P(A\\A)=P tu<t，tv>tu,Fu,Tdeg(u)-1>t==ztdtu ztudtv·p Fu,Tdeg(u)-1>t tu,v/∈Fu,t≤≤z-∞exp-2s(deg(u)-1)^ds=rπ8(deg(u)-1)。把所有的部分加在一起，我们得到p(au6=θA)≤(1-p)1+t-trπ8(deg(u)-1)！+t-trπ8(deg(u)-1)≤≤1-p+t·pdeg(u)-1。在最后一个不等式中，我们考虑了t-t≥t，p≥0,和√2π≤3。将此表达式代入(C.8)引出了期望的界(C.1)。D遗漏了引理5.1的第5节证明的证明。考虑一类V=α·V的诱导子网GVof G,用deg(V)表示一个agent V∈Vin GV的度。固定正γ≤α。我们的目标是将deg(v)<γ·D=γ·deg(v)的试剂的分数束缚在一起。用所有这类主体的集合v∈Vand用v，消去剂的集合V\\V apply不等式（5.2）（见混合引理A.1)到这些Vand V。因为E(V),V)>(1-γ)D·VAND(1-α)V-1<V≤(1-α)V,我们得到(1-γ)D·v-dv·V·(1-α)V≤λpv·(1-α)V。将两边旁路分开并重新排列项，我们得到(α-γ)DpV≤λp(1-α)V和(α-γ)DpV≤λp(1-α)V,因此，V≤(1-α)λ(α-γ)DV≤(1-α)λα(α-γ)DV。因此，至少有一个因子V∈V的分数1-(1-α)λα(α-γ)d具有deg(V)≥γ·D.由下面的引理D.1所包含的，至少有1-2(1-α)λα(α-γ)D v agent至少有γ·D的度大于或等于γ·D的友元。将定理3.1和引理4.1结合应用于该集合中的每个agent并估计出该集合外正确行动的机会为零，对于GV中的任何状态对称平衡σ，我们得到了以下关于收入质量的界:LσGV≥1-2(1-α)λα(α-γ)d1-δp,γD,r,D,其中r=JG-3k。考虑到δ(p,D,r,D)>√D，我们看到括号中的表达式大于1-(1-α)λ9α(α-γ)D·δ(p,D,r,D）。对于任意β，δ(p，βD，r，D)≤qβ-Dδ(p，D，r，D)，很容易检验，因此，第二个括号中的表达式至少是1-qγ-D·δ(p，D，r，D)。打开括号，去掉正项，我们得到σgv≥1-(1-α)λ9α(α-γ)D+qγ-D·δ(p，D，r，D)。取γ=2α，假设α-D≥α，我们得到所需的界（5.1）。在小α<D的互补情形下，上界（5.1）由于≤αδ(p,D,r,D)≥≤D≤·≤D>1而变得平凡。引理D.1。如果在网络G=(V，E)中，至少(1-β)V个代理具有D度或更高，则至少(1-2β)V个代理至少具有D度证明的友方。用v<D表示朋友小于D的Agent集合，用v<D表示朋友小于D的Agent集合，用v<D表示朋友小于D的Agent集合，用D<D表示朋友小于D的Agent集合。我们知道V<D<βV，并试图证明V<D，≥D<2βV。以矛盾的方式假定V<d，≥d≥2βV。因此，V=V<d，≥dü(V\\V<d)至少包含βV个主体。每个v∈v至少有D个友方且至少d-d=dof的度小于thand；用Fv表示suchlow-dend友的集合，<d。集合v<d包含Fv的并，<Doverv∈v。