支持学习的社交网络

我们得到了dxv∈vfv,<d≤v<d,其中事实的起源是因为没有u∈Fv,<dis计数大于deg(u)<dtimes。利用这个表达式中所有集合的基数上的界，我们得出d·βv·d<βv1<1。这个矛盾完成了证明。e随机化鲁棒性在第五节中，我们证明了满足一个非常强的对抗鲁棒性的先验网络的存在性：即使以对抗的方式消除了一个代理子集，网络仍然聚集信息。在这里，我们考虑了一个较弱的对随机消除的鲁棒性的概念，并证明了任何网络都具有这种性质。也就是说，对于具有高学习质量的网络，即使有相当一部分Agent离开网络，剩余的Agent也有一种学习状态的方法，即使大部分信息的传递路径（包括被消除的Agent）消失了。我们将在一个关于Agent可用信息的附加假设下证明随机鲁棒性。回想一下，Gv，T=(Vv，T，Ev，T)表示agent V的已实现的子网络；参见第3.1节假设E.1中的规定。每个代理v除了他的信号和比他更早到达的朋友的行动之外，还观察代理Vv的集合，即他实现的子网络（没有他们的行动和到达时间）。换句话说，一个代理人知道那些可能会采取行动的人。因此v的信息集是IV=(sv，(au)u∈FV，T，Vv，T)。注E.1（假设E.1)的作用。我们认为，这一假设具有技术上的作用，如果没有它，随机化的鲁棒性一定是普遍存在的；然而，我们无法在我们的证明中摆脱它。假设E.1保证平衡点的序贯结构，如果Vv,t=,agent v跟随他的信号。如果Vv,Tis非空且Vv,T=k,则均衡策略σv sv,(au)u∈fv,T,Vv,t-是Vu,T≤k-1（因为Vu,Tis是Vv,T的严格子集）对(σu)u∈Vv,T的最优回答。这种序贯结构意味着agent不能从学习尚未到达的agent集合中获得优势，这是定理E.1证明中的关键性质，定理E.1是本节的主要结果。对于给定的网络G和正确信号的概率p，用L(G)表示，最佳平衡点的学习质量:L(G)=maxσLσ(G)。定理E.1（学习对随机消除具有鲁棒性）。在假设E.1下，考虑网络G=(V,E）具有学习质量L(G)=1-δ且某些δ>0。固定α∈(0,1）并随机一致地选取一个具有α·V代理的子集V(conv)。由此，诱导子网络的学习质量GVenjoys的下界LGV≥1-qδα，其概率至少为1-qδα。定理E.1的证明。该论点是基于原始网络G的学习过程与随机子网络GV的选择之间的耦合。将均衡σ=(σV)V∈V极大化Lσ(G),并选取一个子集Vto为α·V最早到达集。对于V∈V，原网络G中的均衡策略σVA可作为策略GV。由此得到的策略族(σv)v∈V，构成了GV中的一个均衡，它由σv表示。注意，这里我们使用假设1。构造的耦合允许我们分别将G和gvunder均衡σ和σv的学习质量联系起来。通过总概率公式，forG的学习性质可以表示为asL(G)=VXV∈VP(AV=θv∈v)·P(v∈v)+P(AV=θv/∈v)·P(v/∈v),在考虑到P(v∈v)自下而上有界的情况下，利用对正确行动概率P(AV=θv/∈v)≤1的粗略估计，我们得到了如下不等式:Lσ(G)≤α·evlσvgvé+(1-α),其中ev表示关于V的选择的期望，由于左手边等于1-δ，我们得到了1-evlσvgvé≤δα。应用马尔可夫不等式完成了证明。在V上的博弈中，所有在场的Agent都知道V\\va中的Agent是不存在的。

特别是，在没有假设E.1的情况下，v中的一个agent v会比游戏中的同一个agent在v上玩更多地了解他的前任。因此，V中的最佳答复可能不再是限制在V的博弈中的最佳答复，即使所有其他代理人都保持他们的策略。

谢谢分享