观察公司c，cmand x，XNEACH有一个单一的外向优势，他们的战略是固定的。如果一家公司xi，j，0或xi，j，1有多个支出，它总是优先考虑边缘，分别为xi，j+1,0和xi，j+1,1，或ziif j=m。在下文中，我们认为当且仅当存在一个变量分配，使得k′子句在I中完全填充时，v与资产值k′+n的响应最好。假设存在一个变量分配，使得k′子句完全填充。修复此赋值，对于每个满足的子句C，选择一个在子句中计算为true的文本LC。让v选择以下策略：首先，如果赋值中xa=false，则对边（v，xi，1,0）进行优先级排序，如果赋值中xa=true，则对边（v，xi，1,1）进行优先级排序。所有这些边将闭合一个周期（v，xi，1,0，xi，2,0，…，xi，m，0，xi，v）或（v，xi，1,1，xi，2,1，…，xi，m，1，xi，v）。之后，如果c=cj且lc=-xiinan顺序，则对于所有充满子句的文字，lc优先考虑边缘（v，xi，j，0）。如果c=CJ和lc=xi，则对边（v、xi、j、1）进行优先级排序。所有这些边通过克劳斯节点cj闭合一个循环，导致总流入量k′+x。为了显示其他方向，我们观察了所有变量xi的以下结构特性。如果边上有一些流（xi，m，0，zi），则边上不能有任何流（xi，m，1，zi），反之亦然。我们得出结论，某些边缘上的流动（xi，j，0，cj）意味着边缘上的流动（xi，j，0，xi，j+1,0）（因为它具有更高的优先级）和（xi，m，0，zi），因此所有j′都没有流动（xi，j′，1，cj′）。类似地，我们观察到，某些边上的任何流（xi，j，0，cj）意味着边上没有流（xi，j′，1，cj′）。我们观察到，如果有一个流等于k′+n的游戏者v的最佳响应，则节点v有k′+n个携带流的传入边。这些边中最多有n条可以是（zi，v）-边，因此至少有k′子句边（cj，v）携带流。

因此，所有这些k′子句顶点都接收传入流。如果某些子句CJ的流量来自节点xi，j，0，我们通过上面的观察知道，noedge xi，j′，1携带流量。因此，我们可以将变量xito设置为false，这将填充子句Cj。将此操作和类似操作应用于边上的流（xi，j，1，v）会产生一个变量赋值，其中ful fillsat least k′子句。A、 2命题证明10证明。考虑一下右侧描述的游戏。所有资产都有单位权重，所有外部资产都为0。考虑π，其中π=（e，e）和π=（e，e）。这是一个总收入为0的普雷纳什均衡，因为没有一个玩家可以单方面结束一个周期并增加发行量的价值。然而，最优解π*带π*= （e，e）和π*= （e，e）的总收入为2.123EEEEA。3定理14的证明我们首先证明了当纯纳什均衡或强均衡被保证存在时，计算它的难度。计算纳什或强平衡的难度。考虑问题3维匹配的一个实例I。I由一个| T |=3k的有限集T和一个集U给出 T×T×T。Karp[22]证明了判定是否存在子集W是强NP完全的 U使得| W |=k，并且W的任何两个元素都没有非空的intersection。这样一个集合W的存在就是T的精确覆盖。给定一个三维匹配的实例I，我们构造了一个边排序对策的实例，如下所示。为每组u创建一个中心顶点v∈ U，创建一个顶点U，并通过一条边（v，U）将v连接到U，边的容量c（（v，U））=3。对于每对t，u带t∈ T，u∈ U和t∈ 我们创建一个顶点t并添加一条边（u，t），其容量c（（u，t））=1。最后，我们连接每个元素t∈ T乘以边（T，v），c（（T，v））=1到v。其思想是，计算任何纯纳什或斯特龙g均衡都会减少到为玩家v找到最佳响应。

然而，当且仅当我有一个解决方案时，这个最佳响应给出的总资产av=3k。因此，通过计算纯纳什均衡或强均衡，我们可以得到v的最佳响应，从而证明I是否可解（反之亦然）。首先，让我们来论证一下，在这个边缘排名游戏中，e总是一个强大的均衡。首先，请注意所有顶点t∈ T有一个单独的输出边缘。我们定义了一个任意可行策略向量π′。我们将论证最佳响应动力学会产生强平衡。对于v的每个策略，最多有一个顶点ui和aui∈ {1, 2}. 对于所有其他顶点u∈ 由于命题4，每个策略都是对U的最佳响应。我们的结论是，如果π′不是一个强均衡，则存在一个由参与者S组成的联盟，该联盟具有一个改进动作，使得S中的所有参与者S严格增加其资产。如果v/∈ S、 有一个播放器ui∈ S∪ U、 UIM的移动也增加了v的资产。因此，v的资产在动力学的每一步都会增加。这表明dynamicsterminate具有强平衡。设π为边排名博弈中的任意纳什均衡。我们提出以下索赔。有一个子集W，使得| W |=k，并且W的任何两个元素在I中都没有非空交集，当且仅当av=| T | inπ。首先，假设π是一个纳什均衡，av=| T |。由于V的每个传出边缘都有容量3且| T |=3k，我们通过边缘排名游戏的定义知道|{u∈ U | au=3}|=k。我们用U，…，表示这些顶点，英国。T hus，对于i，aui=3≤ 对于所有i>k，k和aui=0。我们将显示对应于顶点u，假设有两个集合u，u有一个非空的交点。如果是这种情况，则有一个元素t∈ Twith t公司∈ u∩ u、 在边缘排名游戏中，有带流的边缘（u，t），（u，t）。

这与av=| T |的事实相矛盾。现在，假设有一个解u，ukto I.我们将证明，对于顶点v，边排名博弈中的每个pur e Nashequirementπ都会产生av=3k的资产。v的所有传入边的总容量正好是3k，所以av≤ 3k显然适用于所有战略文件。我们现在要论证的是，独立于所有其他玩家的策略选择，玩家v总是可以得到AV=3k。设πv=（（v，u），（v，英国），…）。由于u，UK完全覆盖所有元素t∈ T，这将在上述TopCycleIncrease算法中产生3k个循环。这与所有其他顶点的策略选择无关，因为它们总是具有这样的特性：要么所有伸出的边都完全饱和，要么根本没有流动。这表明，即使在一类具有保证存在性的博弈中，计算纯纳什均衡或强均衡也是stron-gly NP困难的。计算社会最优解的难度。考虑之前的构造。网络中的每个简单周期都涉及v和另外两个公司。因为没有外部资产。因此，系统中的总收入正好是3av。因此，通过计算v的最佳响应，我们也可以获得总收入最大的战略文件。这证明了在计算最优策略时具有很强的NP硬度。请注意，这一结果与硬币排名游戏相反，在硬币排名游戏中，可以在强多项式时间内计算出最佳策略。决定Nash和强平衡存在性的困难。对于决策版本的硬度，我们调整了该证明第一部分的结构，并将其与图2中的无布尔纳什均衡博弈相结合。观察到，对于固定vin，外部资产为1。图2将导致主导策略πv=（（v，v），（v，v））。

考虑到该策略，可以向前推导出vand v.πvπv（（v，v），（v，v））（（v，v），（v，v））4 5（（v，v），（v，v））9 34 4（（v，v），（v，v））9 3Thus所有策略选择的资产，前提是vhas外部资产为1，VP主要策略πv=（（v，v），（v，v）），策略πv=（（v，v），（v，v））和πv=（（v，v），（v，v））表示一个强平衡点m。我们利用这一点设计了一类基于三维匹配实例的边排名对策，并具有以下性质。如果我有一个解，游戏有一个强均衡（因此是一个纯纳什均衡）；如果我没有解，博弈就没有纯纳什均衡（因此也没有强均衡）。我们调整了本证明第一部分的结构，并将其与图2示例的| T |副本相结合：在上述证明第一部分的结构中，删除所有T的所有边（T，v）∈ T并添加一个av=3k的外部资产。我们都知道∈ 当且仅当存在三维匹配实例I的解时，T接收到1的流入。图2所示的实例被复制了| T |次。我们表示顶点v，v，…，的| T |个副本，v | T |。从每个ti添加容量为1的边∈ T到v的对应副本，即i=1，…，的边（ti，vi）|T |。如果e是I的解，则所有顶点ti∈ T收到1的流量。该流通过转发到顶点，可以视为其外部资产。因此，所有副本和整个游戏都有一个强大的平衡。另一方面，如果对I没有解决方案，那么总会有一些ti∈ |T | ati=0，例如，w.l.o.g.at=0。相应的顶点V不接收任何流。

因此，各副本中不存在纳什均衡，博弈中也不存在纳什均衡。B边缘排名游戏的清算状态计算对于边缘和硬币排名游戏，我们提供了策略文件π中清算状态结构的更详细分析。在这些游戏中，每个清除状态∈ A对应图中一对一的toa循环，其中循环流量遵循偏序。我们利用这一结构性洞察来说明，唯一的收益最大化清算状态^a可以在多项式时间内计算出来。必要的周期。对于给定的str-ategy-proπ，考虑具有辅助源s和相应辅助边的环流网络G′=（V′，E′）。为了完整性，我们将s视为在其输出辅助边上具有固定策略π的公司。由于命题2，在每个清除状态下，都会精确地填充出边缘。如前所述，π的策略对清洁态集没有影响。我们还扩展了πvand，将辅助边（v，s）定义为顶点v选择的最后一条边∈ V和V已经支付的一定数量的k硬币。然后，下一个硬币到达V时，会有一个未定义的输出边缘。我们将此边缘称为V的活动边缘。每个V公司总是在排名最高的边缘πV（1）开始偿还债务。如果某个边（v，w）=πv（k）饱和，则该形状将其活动边从πv（k）切换到πv（k+1）。现在，考虑≡ 0.每一个固定v 6=s h，正好是一个伸出的活动边πv（1）。必须将活动边集划分为具有附加树的不相交循环。每个连接到一个循环的树都植根于该循环的一个节点，并指向循环C。我们定义了C byo（C）={v的轨道∈ V | 活动边的v-u路径，对于某些u∈ C} ，即，从which我们可以到达C的最上排边的节点集v。

现在，考虑一下辅助源s≡ 0是G′中的可行清除状态，但as=l（s） 是确保a在原始图形G中表示清除状态的必要条件。但是，只要<l（s） 存在s的活动传出边，所有节点（包括s）都属于某个轨道。因此，有一个循环C和s∈ o（C）。清算状态下的流量守恒和s策略的单调性意味着s的某些资产最终必须达到C。由于C中的流量守恒，至少δC=min{C（e）| e的流量∈ C} 因此必须出现在C的任何y边缘。这是每个清除状态a的必要条件∈ A、 归纳地应用这个论点很简单，从而获得一系列必要的循环C，这些循环C必须用流动δC=min{C（e）填充- fe | e∈ C} 。特别是，当为每个边e指定了一个flow offe=δChas时∈ C、 至少有一条垂直线的排名靠前的边在C中发生变化。这意味着轨道会发生变化，即轨道o（C）会划分为新的子轨道，或与其他轨道相连的部分。注：一旦顶点v填充了所有规则的延伸边，排名靠前的边就变成（v，s）。请注意，同时存在的轨道总是相互不相交的。因此，对于两个现有的轨道o（C）和o（C），沿着Ccan的冲流不会改变o（C）的最顶端边缘。因此，当s最终出现在轨道上时，有必要为所有循环C分配一个流量增加δCin，以达到as=l（s） 。一旦我们达到a状态，其中as=l（s） ，一个“轨道”o（s）由根植于s的tree组成。此时，我们确实构建了一个可行的清除状态，通过归纳，它是G′中唯一的最小清除状态，适用于G.可选循环。

在下文中，我们描述了所有其他可行清算状态的结构∈ A通过应用类似的观察结果。修复一些可行的清除状态a（as=l（s） ）并考虑所有活动边的集合。假设有一个循环C具有一些轨道o（C），即一组节点v未连接到以s为根的树上。在这种情况下，可以沿C推动非零流量，即每v增加一个严格正的AV∈ C、 这显然会产生一种新的可行的清除状态。当一条边变得饱和时，活动边集将发生变化，轨道o（C）将消失，即如上所述获得倾斜（新的子轨道、附加到其他轨道的部分、附加到以s为根的树的部分）。请注意，可能同时存在多个轨道，因此，通过增加一个周期的流量，有多种可能性延伸a。然而，如上所述，在同一时刻存在的轨道总是相互不相交的，沿旋回CCA的急流不会改变当时存在的轨道o（C）的顶部坡度。现在考虑一些顶点v∈ o（C）。为了创建一些清除状态，需要a′和a′v>avit沿C推动水流，直到达到avis（如果v∈ o（C）∩ C） 或o（C）消失并溢出（如果v∈ o（C）\\C）。由于流量调整会显著增加所有资产，因此流量增加的周期集与清算状态之间存在一对一的对应关系。请注意，为流量增加选择的周期形成了一个偏序：周期C′可能不存在于开始阶段——可能存在必须填充至δCto的前一个周期C，以打破现有的轨道o（C），改变一些排名靠前的边，并出现d m ake C′。

在上述论证中，可以看出，某些旋回C′的前一旋回pred（C′）集合是由π中的边排序唯一确定的。上述论点暗示了一种计算^a的自然算法，这在精神上类似于房屋分配的经典TopTr ad ingCycles算法[28]。TopCycleIncrease算法通过循环网络G′中排名靠前的边缘的循环来增加资金流动。因此，它从晶格计算出唯一的最大清除状态^a。该算法在多项式时间内运行–在每一轮中，它将沿循环C的流量增加δC。在这一点上，至少斯通边缘（从G或辅助）变得饱和。对于原始网络G=（V，E），算法最多需要O（| V |+| E |）轮。每一轮都可以在斯特龙多项式时间内轻松实现。提案18。在每一个边缘或硬币排名游戏中，TopCycleIncrease算法在强多项式时间内计算唯一的最大清除状态^a。