优先附着作为唯一平衡的社交网络游戏

there have been many empirical observations [3, 21] that justify theuse of Preferential Attachment in the social networks framework(including the “rich get richer” aphorism), there are little knownformal analytical justifications for that usage, to our knowledge.In this paper, we make a significant step towards filling the gapbetween empirical explanations and formal justifications. We showthat Preferential Attachment is the only rational choice for playersinvolved in a simple natural network formation game.5590优先附着作为唯一平衡0扩展摘要0Chen Avin Ben GurionUniversity, Beer Shevaavin@cse.bgu.ac.il0Avi Cohen WeizmannInstitute, Rehovotavi.cohen@weizmann.ac.il0Pierre Fraigniaud CNRS andUniversity Paris Diderotpierre.fraigniaud@irif.fr0Zvi Lotker Ben Gurion University,Beer Sheva zvilo@bgu.ac.il0David Peleg WeizmannInstitute, Rehovotdavid.peleg@weizmann.ac.il0摘要0本文证明了优先附着规则在进化网络形成的背景下自然地出现，作为一个简单社交网络游戏的唯一纳什平衡。在这个游戏中，每个节点的目标是在未来最大化其度数，代表其在节点及其连接所形成的“社会”中的社会资本。这个结果为常用的优先附着模型提供了额外的形式支持，该模型最初旨在捕捉“富者愈富”的格言。在建立我们的结果的过程中，我们揭示了优先附着、随机游走和Young格子之间的新联系。0CCS概念0• 计算理论 → 社交网络；网络形成；0关键词0优先附着；网络形成游戏；社交网络；Young格子；随机游走0ACM参考格式：Chen Avin, Avi Cohen, Pierre Fraigniaud, Zvi Lotker, andDavid Peleg. 2018. Preferential Attachment as a Unique Equilibrium:Extended Abstract. In Proceedings of The Web Conference 2018 (WWW2018). ACM, New York, NY, USA, 10 pages.https://doi.org/10.1145/3178876.318612201 引言0优先附着[1]模型无疑是一种常用于现实生活网络，特别是社交网络的模型之一。该模型基于优先附着规则，该规则规定网络中具有度数k的现有节点将以k/Z的概率接收到一个新链接，其中Z是一个归一化常数。该模型生成具有与许多现有网络相似特征的合成图形。这些特征包括小直径[4]、幂律度数序列[5,24]和邻居度数之间的相关性[14]。然而，优先附着为什么与观察结果如此契合仍然是一个广泛开放的问题。实际上，虽然有许多经验观察[3,21]证明了在社交网络框架中使用优先附着的合理性（包括“富者愈富”的格言），但据我们所知，对于这种用法，几乎没有已知的正式分析解释。在本文中，我们在填补经验解释与正式解释之间的差距方面迈出了重要的一步。我们展示了优先附着是一个简单自然的网络形成游戏中参与者的唯一理性选择。0本文在Creative Commons Attribution 4.0 International (CC BY4.0)许可下发表。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW 2018，2018年4月23日至27日，法国里昂，©2018IW3C2（国际万维网会议委员会），根据Creative Commons CC BY 4.0许可发布。ACMISBN 978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861220基于财富的推荐游戏。我们将网络演化建模为一种网络形成游戏，称为基于财富的推荐（wbr）游戏，其中每个节点的目标是最大化其期望度数。每个节点在加入网络时只能做出一个选择，即选择向谁请求推荐。具体而言，我们考虑一个节点一个接一个地到达的演化过程。最初，网络只包含一个节点v1。在离散时间t>1时到达的节点vt会自荐连接到某个现有节点，选择是基于网络中每个节点的实际社会资本（表示为当前度数）的情况下进行的，节点vt根据某个概率分布πt选择一个在当前度数序列D=(d1,...,dt-1)上的索引i，其中d1>=d2>=...>=dt-1，对应于实际网络中的节点。然后，vt联系度数为d的某个节点u，并请求与u建立连接。被选择的节点u，称为主机，可以接受连接，也可以将其委派给其邻居之一。游戏中这一特性的动机是，根据当前网络形成的当前社会的某种形式的财富，主机可能愿意或不愿意接受新的连接（即新的合同、新的社交、情感或经济依赖等），因为这些连接会带来风险。时间t时社会的财富由参数αt∈[0,1]来捕捉，αt越高，财富越高。被联系的主机u以概率αt接受vt提出的连接，或者以概率1-αt将其委派给其邻居之一。这个邻居w是在u的邻居中均匀随机选择的，w接受连接。这个模型的另一个视角是，每个新节点vt在进入网络时根据πt随机遇到它的主机u，然后开始执行一个具有停止概率αt>0的简单随机游走[18]。新节点连接到游走停止的节点。为了简化演示，我们不强制递归，只考虑一步推荐或一步随机游走。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France5600请注意，时间3时的网络状态始终是一个由3个节点组成的链，因为节点 v 2 只有一个策略，而 v 3的策略不会改变结果。不确定性只从时间 t ≥ 4开始。图1和图2分别描述了在4步和5步之后网络形成的可能情景。0G 1 = S 4 G 2 = P 40玩家 40图1：前四个玩家玩过后的两种可能状态，以及第四个节点的可能位置。0请注意，在图2中，图 G 11 和 G 22是同构的。我们在图中区分了这两种情况，因为这两个图来自于两个不同的历史：在 G 11 中，第五个节点连接到了图1中所示的图 G 1的一个叶子，而在 G 22 中，第五个节点连接到了图 G 2的一个叶子。请注意，每个节点的连接可以是直接连接到被联系的节点（即主机），也可以是委托连接到被联系节点的邻居。0玩家 40玩家 50G 110G 120G 210G 220图2：前五个玩家玩过后的四种可能状态，以及第四个和第五个节点的可能位置。0一个节点的效用定义为其预期度数，衡量其社交资本。请注意，当节点 v t 加入时，选择与谁建立连接对 v t的社交资本在短期内没有影响，因为无论选择与哪个节点建立连接，每个新节点的度数都为1。玩家的主要考虑因素是他们的选择对长期的影响，考虑到网络的当前状态（由其度数序列表示）和未来玩家的策略。因此，该游戏捕捉到了决策过程中的一些重要心理特征，个体必须在过去、现在和未来之间取得平衡，并权衡决策的短期和长期影响。特别地，不知道游戏何时结束，节点应该计划他们的策略以适应长期情景。这与社交网络中的“一生最好的朋友”（BFF）和传统婚礼仪式中使用的术语一致：人们不知道游戏何时结束，但是计划着长期的未来。换句话说，未知的停止时间是自然的假设，与事实一致，即可悲可幸的是，我们不知道生命何时结束。总之，我们的网络形成游戏由序列 ¯ α = ( α t ) t ≥ 1 表征，该序列衡量了社会的财富的演变。0社会随时间变化的财富以及度量效用的结束时间 τ 。玩家们对 ¯ α 和τ一无所知。它们代表了决策机制必须应对的未来的自然不确定性。度数序列 ( d 1 , . . . , d t − 1 ) ， d 1 ≥ d 2 ≥ ∙ ∙ ∙ ≥ d t − 1上的概率分布 π t 定义了第 t 个节点加入网络的策略。策略配置 Π被定义为玩家所有策略的集合，即 Π = ( π t ) t ≥ 1。0我们的结果。我们展示了优先连接策略配置（稍后正式定义）是游戏的唯一纳什均衡，该纳什均衡是普遍的，即对于所有序列 ¯ α = ( α t) t ≥ 1 和所有停止时间 τ都成立。独特性是一个显著的特点：对于加入网络时建立连接的选择，不确定性使得优先连接成为唯一可行的选择。任何其他策略配置 Π可能对于某些对 ( ¯ α , τ ) 而言是纳什均衡，但必定存在一对 ( ¯ α ′ ,τ ′ ) ，在该对定义的游戏中，如果存在某个时间 t ，满足 4 < t ≤ τ，某个玩家 v t 决定偏离优先连接策略，那么存在至少一个玩家 v t ′在时间 t ′ < t 通过偏离优先连接策略在时间 τ获得（预期度数）收益。值得讨论的是，不确定性程度对纳什均衡的唯一性的影响。首先，对于一个有限的游戏的不自然假设，即结束时间 τ是事先确定的并为玩家所知，显然会导致许多与优先连接不同的纳什均衡。特别地，最后一个玩家 v τ可以使用任何策略，因为这对其效用没有影响，其效用在游戏结束时必定等于1。另一方面，财富随时间变化的假设对于存在唯一普遍纳什均衡并不关键。事实上，即使社会的财富随时间保持不变，即 α t= α t ′ 对于所有 t ，t ′ ≥1，优先连接仍然基本上是唯一的普遍纳什均衡。更准确地说，根据这个假设，任何普遍纳什均衡都必须满足每个玩家在所有不同于星形（即具有 n - 1 个叶子的 n节点树）的网络上都采用优先连接策略。因此，假设 α随时间变化并不是证明优先连接的相关性的核心。关键是玩家们不知道 α 的值（即使它随时间固定）。然而，我们的证明并不要求使用 α的整个值范围 [ 0 , 1 ] ，只要 α从至少两个不同的值组成的有限集合中取值，就足以证明优先连接是唯一的普遍纳什均衡。然而，假设 α至少有两个值似乎是必要的。事实上，我们证明了如果 α是事先确定的，例如 α =1，并且玩家们知道这个值，那么存在许多普遍纳什均衡。实际上，我们对 α = 1的这种普遍纳什均衡进行了特征化，作为证明我们主要结果的中间结果。0主题：社交网络分析和Web上的图算法WWW 2018年4月23日至27日，法国里昂Wide Web using the PA rule. A few other examples of networks wellcaptured by the PA rule include collaboration networks, the internet,interbank payment networks, airline networks, and protein-proteininteraction networks [20], among others. Hence, the PA model isa powerful tool for studying real-world networks in general, andsocial networks in particular, but it does not help fully explain theexistence of the very property it aims at simulating, that is, theprevalence of social networks with a power law degree distribution.Some authors approach the problem of formally justifying PA.In particular, D’souza et al. [7] showed the emergence of prefer-ential attachment from underlying optimization mechanisms. Ourobjective is to approach the problem from a simpler, and perhapsmore natural game theoretical perspective. The same approach wassuggested for future research by Jackson [10]. Several network for-mation games have been defined. The one introduced by Fabrikantet al. [8] (see also [19]) reaches an equilibrium on either the cliqueor the star graph, both of which rarely occur in large social net-works. The PageRank game (see [2, 6, 9, 13]) better fits the socialnetwork setting. In this game, the players represent web pages, andeach player forms directed links to other players, with the goal ofmaximizing his PageRank. In particular, equilibria of the PageRankgame that are insensitive to the “jumping probability” of PageRank,and therefore are universal (in a similar sense to that defined in thecurrent paper) were presented in [9]. Nevertheless, the PageRankgame assumes that the number of players is fixed, and connectionsbetween individuals may evolve with time. Instead, we considerthe formation of a possibly infinitely growing society, in whichconnections between individuals involve a permanent commitment.We complete this section by noticing that another family ofrandom models that generates scale scale-free networks is basedon the copying mechanism [11, 12, 15, 16, 25]. In these models theprocess by which a new node selects its connections is similar toours, but these models (as well as the original PA) are not game-based.56102 结果的正式陈述0在本节中，我们完全说明了引言中提出的游戏，并正式陈述了我们的主要结果。02.1 游戏wbr(¯α, τ)0为了形式化我们的游戏，我们将网络演化定义为一种称为财富推荐（wbr）游戏的网络形成博弈。网络的演化在离散时间点上发生，每个时间步骤发生一个事件。我们从时间1开始，有一个单一节点表示为v1，并且没有边。这个图被表示为T(1)。在每个时间步骤t>1，一个新的玩家vt到达并向T(t-1)中的现有节点vj添加一条边，从而创建图T(t)。因此，在时间t，网络T(t)由具有t个节点（和t-1条边）的树组成。当玩家vt到达时，它联系一个现有玩家vi并请求一个主机。当联系到主机vi时，它必须推荐一个邻居给vt，推荐的方式如下：以概率αt，主机推荐自己，以概率1-αt，它以均匀随机的方式推荐自己的一个邻居。随后，vt连接到推荐的节点。0我们现在澄清选择主机的过程。让πt表示vt的策略，它决定vt选择主机的分布，对于图T(t-1)的每个实例。对于图G中的节点vi，我们用degG(vi)表示其度数（即邻居数量）。图G的度序列DS(G)是其节点度数的非递增序列(d1, d2, ...,dn)。令D(t)为具有t个节点的树的所有度序列的集合。对于每个t≥1，策略πt是一个函数0πt: N × D(t−1) →0也就是说，对于每个度序列D∈D(t−1)，对于树T(t−1)中度为k的节点vi，节点vi在时间t被联系的概率是πt(k,D)。注意，虽然节点在时间t被选为主机的概率取决于策略πt，但节点在时间t被推荐（即采用新邻居）的概率还额外取决于树T(t−1)的边集和参数αt。策略配置Π是所有玩家的策略集，Π = (πt)t≥1。0定义2.1. 对于一个序列¯α = (αt)t≥1，其中αt∈[0,1]对于每个t≥1，和一个时间τ>1，令wbr(¯α, τ)表示在第t = 1, . . . ,τ轮中使用αt进行的基于财富的推荐（wbr）游戏，并在时间τ结束后停止。0对于给定的游戏wbr(¯α,τ)，当使用策略配置Π时，T(t)(Π)是在时间t时获得的随机树。注意，T(t)(Π)实际上是一个节点标记的树，其中每个节点由其在网络中的到达时间标记。在接下来的内容中，n个节点标记的树是一个树，其节点由{1, . . . , n}中的不同整数标记。对于每个t节点标记的树T，令0φ(T) = Pr[T(t)(Π) = T]。0定义2.2. 在wbr游戏中，时间t时vi的效用定义为u(t)i(Π) =E[degT(t)(Π)(vi)] = ∑T∈T(t)degT(vi) ∙ φ(T)，0其中T(t)是所有t节点标记的树的集合。0策略配置Π是游戏wbr(¯α,τ)的纳什均衡，如果没有玩家vt可以通过单方面改变自己的策略πt来增加其效用，而策略配置Π是一个通用纳什均衡，如果对于每个有限时间τ和每个序列¯α，它是游戏wbr(¯α,t)的纳什均衡。更正式地说，对于游戏wbr(¯α, τ)和t∈{1, . . . ,τ}，令Π−t是除t之外的所有玩家所采取的（τ−1）维策略向量，令(π′t,Π−t)表示策略配置，其中vt采取策略πt，其他玩家根据向量Π−t采取策略。0定义2.3. 策略配置Π =(πt)t≥1是wbr游戏的通用纳什均衡，如果对于每个游戏wbr(¯α,τ)和每个策略配置Π′ = (π′t)t≥1，我们有u(τ)t(πt, Π−t) ≥0对于每个玩家t = 1, . . . , τ，u(τ)t(π′t,Π−t)。02.2形式陈述0我们用pa表示优先附加策略，即pa是一个个体节点策略，给定度序列D = (d1, . . . , dn)，度为k的节点以概率联系到其他节点。0pa(k, D) = k ∙∑nj=1dj。0主题：社交网络分析和Web上的图算法WWW 2018，2018年4月23日至27日，法国里昂.d(s)t=;Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France5620注意，在wbr游戏中，插入第t个节点后，时间t时的图是一棵具有t个节点的树T(t)。因此，无论游戏的历史如何，对于任何t>1，0pa(k, D) = pa(k) = 02(t −0定义2.4. 优先附加策略配置（preferential attachmentprofile），表示为Πpa，是一个策略配置，其中玩家vt在t≤4时任意玩，而在t≥5时按照pa策略玩。0注意，对于每个策略配置，第二个玩家没有选择，第三个玩家的选择是无关紧要的（因为任何选择都会产生相同的网络）。第四个玩家在Πpa中任意玩的假设是由于证明中出现的技术原因而产生的次要问题。以下结果表明pa是一种自然的策略。0定理 2.5. 偏爱连接配置文件 Πpa 是 wbr 游戏的通用纳什均衡。0以下定理是本文的主要结果。它表明，实际上，对于理性玩家来说，没有其他选择可以玩 pa。0定理 2.6. 对于任何策略配置 Π ≠ Πpa，Π 不是 wbr游戏的通用纳什均衡。0时间不变的 wbr 游戏是 wbr 游戏的一个变体，其中财富参数 α不随时间变化。以下结果表明，除了病态情况外，偏爱连接基本上是理性玩家唯一可以玩的策略。0定理 2.7. 如果策略配置 Π 是时间不变 wbr游戏的通用纳什均衡，则每个玩家在不是星形图的所有图上都玩pa，如果玩家 t 在星形图 St-1 上玩 pa，则所有后续玩家 t' > t在所有图上都玩 pa。此外，02，然后，以概率1，玩家轮流进行选择：玩家 t - 1选择星形图中的一个叶子节点，玩家 t - 2 选择中心节点，玩家 t - 3选择一个叶子节点，依此类推；• 如果 πt (t - 2, DS(St-1)) < 102，然后，以概率1，玩家轮流进行选择，其中玩家 t - 1从选择星形图中心开始。0静态 wbr 游戏是时间不变的 wbr游戏的变体，其中财富参数等于1。为了描述静态 wbr游戏的通用纳什均衡，我们定义以下概念。如果对于每个度为 k的节点，选择该节点的概率与度序列无关，则策略 πt是度-k一致的。如果对于每个 k ∈ N，策略 πt 是度一致的，则策略πt 是度一致的。注意，pa 是一种度一致的策略。如果对于每个 t ≥1，πt 是度一致的，则策略配置 Π = (πt) t ≥ 1是度一致的。以下结果表明，静态 wbr游戏的通用纳什均衡基本上是度一致的。0定理 2.8. 设 Π 是静态 wbr 游戏的通用纳什均衡。如果对于每个 t'∈ {1, 2, ..., t - 1}，策略 πt' 对于每个 k ∈ {1, . . . , t - 1}都是度一致的，并且 πt' (k) > 0，则 πt是度一致的策略。特别地，如果每个玩家 t' ∈ {1, 2, ..., t - 1} 都玩pa，则 πt 是度一致的策略。0重要的是要注意，pa 不是唯一的度一致策略。实际上，引理 4.15描述了一个有趣的度一致策略族，其中包括 pa以及均匀分布（即，将每个主机连接的概率设为 1 / (t -1)），以及其他分布。本文的其余部分致力于证明这些定理。由于篇幅有限，一些证明被推迟到完整版本中。03 偏爱连接是通用纳什均衡0我们现在证明偏爱连接（PA）配置文件是通用的。我们通过展示wbr(¯α,τ)游戏与图上的简单随机游走之间的紧密联系来实现这一点。首先回顾一下关于带有自环的简单随机游走的稳定分布的一个众所周知的结果（例如，参见 Levin et al. [17]§1.5）。对于任何具有 n 个节点和 m条边的无向图 G = (V, E)，带有自环的简单随机游走的稳定分布02 m . 这里有一个有趣的观察结果是，实际树 T 在时间 t的稳定分布与 T 的 pa 策略相同，即对于树 T 中的每个节点 v，π(v)= pa(deg T(v),DS(T))。我们现在可以利用这个观察结果来证明对于任何财富，新到达的节点连接到任何给定的现有节点的概率等于选择该节点作为主机的概率，如果节点按照 pa 策略进行游戏。0引理 3.1. 假设在 wbr ( ¯ α , τ )中使用优先连接配置文件，并考虑一个节点 u 在时间 t ≥ 4 加入网络T 。对于每个序列 ¯ α =  ( α t ) t ≥ 1 ，我们有0Pr [ u 连接到 v | T ]  =  pa ( deg T  ( v ) ,  DS ( T ))  =deg T  ( v )0证明。证明的结论来自于在我们的 wbr ( ¯ α , τ ) 游戏中，u决定连接到哪个节点的过程与从分布 π t开始的一步简单随机游走相同。根据定义，如果 π t 是 T的平稳分布，则选择 v 作为主机的概率等于连接到 v的概率（经过一步随机游走）。证明通过回忆 pa 是 T的平稳分布来结束。□0我们现在可以证明定理 2.5。0定理 2.5 的证明。假设使用优先连接配置文件 Π pa，并假设存在一个序列 ¯ α 和某个玩家 v t ，通过从策略 pa偏离到策略 π ′ t � pa ，他可以增加自己的效用。令 d ( s ) t表示指示随机变量0玩家 v t 在时间 s 的度数。然后 d ( t ) t =  1 ，根据引理3.1，对于每个 s > t ，以下递归成立：0d ( s − 1 ) t +  1 的概率为 d ( s − 1 ) t0d ( s − 1 ) t 否则。0这个递归与玩家 v t 的策略 π ′ t 和序列 ¯ α无关，与假设相矛盾。因此，Π pa 是一个普遍的纳什均衡。□di = (n − )Proof. To prove the lemma we show that if π5 � pa, then forevery π4, there exists a wealth parameter α5 such that π4 is not theoptimal strategy for v4. After v4 has played, the resulting tree canbe of two forms only, denoted earlier by G1 and G2, correspondingto the 4-node star S4 and the 4-node path P4 (depicted in Fig. 1), withrespective degree sequences DS(G1) = 3111 and DS(G2) = 2211.By the way S4 and P4 emerge from S3 we have� φ(S4)=2p(1 − α4) + (1 − 2p)α4 ;φ P4=2pα4 + 12p 1α4 .=1 +56304 优先连接是唯一的0我们现在转向证明本文的主要技术结果，即优先连接是唯一的纳什均衡。我们首先解释并证明五个玩家的情况，然后使用我们称之为游戏事件操作符并依靠与Young's Lattice[23]的有趣联系将结果扩展到一般情况。04.1 预备知识0我们使用以下三个简单引理。0引理 4.1. 大小为 n 的每棵树 T 在经过 n 步优先连接配置文件的 wbr游戏后都有一定的正概率出现。0 n 的树，其度序列为 ( d 1 , . . . , d n )0存在当且仅当 n �0引理 4.3. 设 T 是一棵度序列为 ( d 1 , ..., d n ) 的树，设 v i 是 T中的一个节点，使得 d i  >  1 。那么可以构造一棵与 T具有相同度序列的树 T ′ ，其中 v i 有一个度为 1 的邻居。04.2 第一步0设 Π  =  ( π i ) i  ≥ 1  是一个策略配置文件，其中 π i 是第 i个玩家的个体策略，由 v i 表示。策略 π 1 ，π 2 和 π 3是平凡的，因为 π 1的定义是创建一个节点，而第二个和第三个玩家不可避免地面临度分布 ( 0 ) 和 ( 1 ,  1 ) ，分别。也就是说，π 2 是联系唯一的度为 0的节点的唯一策略，π 3 是联系度为 1 的节点的策略（两者概率均为1）。第三个玩家玩完后，图由 3 节点路径 P 3 组成，因此玩家 v 4只能面对一种度序列，即211（为了清晰起见，我们省略括号和逗号）。然而，玩家 v 4有无限多的策略。更具体地说，v 4 的策略可以用一个参数 p ∈ [ 0 , 1 ] 来描述，即它与度为 1 的节点联系的概率。玩家 v 4玩完后，得到的树只能有两种形式，分别用 G 1 和 G 2 表示，其中G 1 是 4 节点星形图 S 4 ，G 2 是 4 节点路径 P 4，它们的度序列分别为 DS ( G 1 ) = 3111 和 DS ( G 2 ) =2211。这些图在图 1 中显示。因此，策略 π 5可以用两个参数来描述：连接到 S 4 和 P 4中叶子节点的概率。玩家 5 玩完后，得到的树只能有三种形式，即 5节点星形图 S 5 ，5 节点路径 P 5 和唯一的度序列为 32111 的树 T5 （见图 2）。为了分析起见，我们区分了对应于 T 5的两个不同状态，分别在图 2 中表示为 G 11 和 G 22 。实际上，图2 中的 G 11 和 G 12 是由图 1 中的 v 5 在 G 1 上玩的结果，而 G21 和 G 22 是由玩家 v 5 在 G 2 上玩的结果。策略 π 6在三个图上玩：S 5 （= G 12 ），P 5 （= G 21 ）和 T 5 （= G 11= G 22 ），因此可以用四个参数来描述：分别为图 S 5 和 P 5的一个参数，以及树 T 5的两个参数（因为它包含三个不同的度）。玩家 v 6玩完后，得到的树可以采取多种形式，我们在论文的完整版本中进行了考虑。在第 4.5节中，我们进一步简化了游戏的演化，只考虑度分布。这种新的结构丢弃了0对于五个玩家的定理2.6的证明04）。根据我们对偏好附加配置文件的定义，玩家v4可以自由选择任何可用的策略。定理2.6声称，特别是v5必须玩pa策略以确保普遍纳什均衡。这由下一个引理证明。0策略π1，π2和π3是唯一的，如前所述。v4的策略可以用一个参数p∈[0，1]来描述，其中π4（1）=p，π4（2）=1-2p（请注意，pa对应于p=10证明。为了证明引理，我们证明如果π5�pa，则对于每个π4，存在一个财富参数α5，使得π4不是v4的最优策略。在v4玩过之后，得到的树只能有两种形式，前面用G1和G2表示，分别对应于4节点星形图S4和4节点路径P4（在图1中表示），其相应的度序列为DS（G1）=3111和DS（G2）=2211。通过S3生成S4和P4的方式，我们有φ（S4）=2p（1-α4）+（1-2p）α4；φ（P4）=2pα4+（1-2p）（1-α4）。0引理4.4。假设Π=（πi）i≥1是一个策略配置文件。如果π5�pa，则Π不是一个普遍纳什均衡。此外，如果π5�pa，则Π甚至不是所有wbr（¯α，5）游戏的纳什均衡（即使游戏在第5次停止）。0v5的策略可以用两个参数r，s∈[0，1]来描述，其中π5（1，S4）=r，π5（1，P4）=s。请注意，pa对应于r=106。在v5玩过之后，得到的树只能有三种形式，即5节点星形图S5，5节点路径P5和唯一的度序列为DS（T5）=32111的树T5（见图2）。请注意，根据我们的一般符号约定和为了分析的目的，我们区分了与T5相对应的两种不同状态，分别表示为G11和G22（见图2）。我们有������0�0φ（G11）=φ（S4）∙[3rα5+（1-3r）（1-α5）]；φ（G12）=φ（S4）∙[3r（1-α5）+02（1-2s）（1-α5）]；φ（G22）=φ（P4）∙[2s（1-α5）+102（1-2s）（1+α50根据定义2.2，玩家v4在策略Π下在时间5的效用u（5）4（Π）满足：0u（5）4（Π）=�0i，j∈{1,2}φ（Gij）E [degGij（v4）]0= 43φ（G11）+φ（G12）+302φ（G21）+φ（G22）03φ（G11+102φ（G210这个效用是p的线性函数，我们将其写为u（5）4（Π）=A +Bp，其0A = 1 +103α4�3rα5+（1-3r）（1-α5）�+102（1-α4）�2s+102（1-2s）（1-α5）�0和0B = 03（1-2α4）�3rα5+（1-3r）（1-α5）�+（2α42sα5+102（1-2s）（1-α5）�。0Track：社交网络分析和Web的图算法WWW 2018年4月23日至27日，法国里昂011211221131112221122221122222113211132211133111142111132221113321111422111143111114111152111115111116111111115640图3：由⊕事件连接的度序列的格子。06]。令α = α4 = α5 = 102 + ϵ，其中|ϵ| > 0是任意小的。然后我们有B = δϵ + O(ϵ^2)。因此，如果δ ≠0，选择α > 1会使得玩家v4的最佳反应为p = 0或p = 102取决于B的符号，这主要受到δϵ的符号的影响。因此，为了成为一个普遍的纳什均衡，策略配置Π必须满足s = 106。在假设s = 1的情况下06]得到B = -2δ(1-2α4)(1-2α5)。因此，如果δ ≠0，通过选择α4和α5都大于1，可以使得B < 0或B > 002和另一个小于102，可以改变B的符号，使得玩家v4的最佳反应为p = 0或p = 102，具体取决于B < 0或B > 0，因此，为了成为一个普遍的纳什均衡，策略Π必须满足s= 106。也就是说，玩家v5必须玩pa。□0备注。基于引理4.4来对到达时间t进行归纳以证明定理2.6是很诱人的。然而，这并不像乍一看那么简单。事实上，玩家vt不玩pa可能对vt-1没有好处，而是对某个更早的玩家vt'（其中t' 1是D中出现的一个值，i是满足di = k的最大索引。D �k表示通过将di减小为di-1，并从D中删除dn =1而得到的大小为n-1的度序列。即，0D � k = (