160在危机时期分配刺激支票0Marios Papachristoupapachristoumarios@gmail.com 康奈尔大学 美国0Jon Kleinbergkleinber@cs.cornell.edu 康奈尔大学 美国0摘要0我们研究了在个体经历收入冲击的网络中提供金融援助（救助、刺激支付或补贴分配）的问题。这些问题在政策领域和设计新型网络金融交互形式中都很普遍。我们基于Eisenberg和Noe的金融清算框架，该框架允许基于刺激计划的离散救助来进行离线和在线设置。我们表明，在金融网络上最优地分配这种救助以最大化各种社会福利目标是一个计算难题。我们开发了近似算法来优化这些目标，并为其近似比率建立了保证。然后，我们在优化问题中引入了多个公平约束，并研究了它们的有界性。最后，我们将我们的方法应用于数据，包括在具有真实数据的大型金融机构系统的背景下，以及在具有人与企业之间的金融交互的现实社会背景下，我们使用从移动模式中得出的半人工数据。我们的结果表明，我们开发和研究的算法在实践中具有合理的结果，并且优于其他基于网络的启发式方法。我们认为，通过社会层面的视角来呈现的问题可以帮助决策者在发布补贴方面做出明智的决策。0CCS概念0• 计算理论 → 算法设计与分析。0关键词0金融传染、最优救助、公平、清算0ACM参考格式：Marios Papachristou和Jon Kleinberg. 2022.在危机时期分配刺激支票. 《ACM Web Conference 2022 (WWW’22)论文集》, 2022年4月25日至29日, 虚拟会议, 法国里昂. ACM, 美国纽约,11页. https://doi.org/10.1145/3485447.35120470M.P.受到康奈尔奖学金的支持。J.K.部分受到Simons Investigator奖、VannevarBush教职奖、MURI grant W911NF-19-0217、AFOSR grant FA9550-19-1-0183、AROgrant W911NF19-1-0057、Simons Collaborationgrant以及MacArthur基金会的资助。我们感谢S. Banerjee、S. Chang、I. Kondo和E.Pierson对本文的有益讨论。完整版本的论文可在https://arxiv.org/abs/2106.07560找到。0未经费用许可，可以将本作品的全部或部分数字或实体副本用于个人或课堂使用，但不得为了盈利或商业优势而制作或分发副本，并且副本必须带有本通知和第一页的完整引用。必须尊重ACM以外其他人拥有的本作品组成部分的版权。允许带有信用的摘要。要进行其他复制、再版、发布到服务器或在列表中重新分发，需要事先获得特定的许可和/或支付费用。请向permissions@acm.org请求权限。WWW ’22, 2022年4月25日至29日, 虚拟会议,法国里昂 © 2022 Association for Computing Machinery. ACM ISBN978-1-4503-9096-5/22/04...$15.00 https://doi.org/10.1145/3485447.351204701 引言0互联网已经实现了新型的金融互动方式——通过广泛使用的服务（如Venmo）、通过新的借贷、资助和慈善机制以及通过支持所有这些活动的数据收集。在这个过程中，Web应用程序开始遇到一系列属于更广泛领域的问题，这些问题涉及支出模式的分析和相应的金融援助。这也是世界各国政府面临的问题，因为它们面临着拯救受到金融冲击的实体的问题。在所有这些应用中，无论是在线还是离线，一个标准的政策框架是刺激支票，即现金注入以刺激消费[2, 4, 5, 12, 13, 26,34, 35,38]。在任何这样的情况下，决策者面临的一个关键问题是谁获得补贴。这些问题在COVID-19期间变得越来越突出；例如，在美国，CARES法案[1]根据收入范围给予刺激支票，并根据抚养人数相应增加支付金额。其他国家，如新西兰和希腊，为受影响的雇员提供固定金额的刺激支票。这些情况的一个共同模式是，当某人的收入低于一定门槛或满足某些标准时，该家庭有权获得固定金额的刺激支票。一个重要的局限性是这些规则忽略了金融网络中的传染效应。例如，如果一家企业违约，可能会导致员工失业，而员工可能无法支付租金等。在金融危机中救助谁是一个有争议的问题[7, 9, 11, 14, 16, 25,39]，即决策者面临以下困境：我们是否需要救助那些从违约中挽救的大企业，这将有助于保持就业岗位，但也可能使它们比其他人口更富有和更强大，还是我们需要救助个人（或其中的一些群体）和小企业，以便他们能够支付租金和杂货，而不用担心让更大的公司崩溃？影响的广度。所讨论的问题可以在许多其他领域中应用。一般而言，该问题可用于从离散集合中分配离散资源（救助），该离散集合受到预算的限制，其中网络表示受冲击的一般供需网络。例如，在拼车应用中，救助对应于车辆，节点对应于社区，冲击对应于车辆故障，责任对应于社区之间对车辆的需求。类似的表述可以扩展到其他问题，如计算中心和Web广告。贡献。我们为在广为研究的Eisenberg-Noe（EN）上最优地分配离散救助提供了一个理论框架01 https://bit.ly/guardian-new-zealand和https://bit.ly/kathimerini-greecepji ≥ 0 from j to i, which denotes how much j owes to i (in terms ofmonetary units, e.g. USD). The initial wealth, or equity, of node j isgiven by wj = cj +�i:i∼j pij −pj where pj = bj +�i:j∼i pji are thecumulative liabilities of node j. The network contains no isolatednodes, i.e. every node j has pj > 0 (either external liabilities, orinternal liabilities or both). With βj = (pj − bj)/pj we refer to thefinancial connectivity of j, i.e. the fraction of total liability that j oweswithin the network (not to be confused with graph connectivity; seealso [23]). We define βmin = minj ∈[n] βj and βmax = maxj ∈[n] βj.The assets of each node are disrupted by a random shockXj ∈ [0,cj][23]. Under the shock, each node is able to pay its creditors anamount ¯pj ∈ [0,pj]. If the node is solvent, then ¯pj = pj. Otherwise,the node defaults to its creditors, and rescales its liabilities in orderto pay its creditors to a reduced rate, according to the amount ofmoney it owes to them. The relative liabilities matrix A is defined tohave entries aji = pji/pj whenever pj > 0 and aji = 0 otherwise. Astandard bailout strategy when the recipients have high granularity(i.e. individuals, small businesses) is to bailout an individual from afixed set of resources3. Thus, to (perhaps partially) avert the shocksa policymaker can issue stimulus checks of value Lj to a subset ofnodes subject to a budget constraint Λ > 0. The clearing paymentvector ¯p is givena reasonable assumption aswe are able to model the external liabilities with a tax (e.g. incometax) or other fixed costs (e.g. rent/utilities payment) that is owedto an external entity (e.g. government, bank etc.). At equilibrium,the solvent nodes are R = {j : ¯pj = pj } and the default nodes areD = {j : ¯pj < pj } = [n] \ R.Optimization Formulation. The vector ¯p can also be found viasolving an optimization problem of the following form [19, p. 10]:170WWW '22，2022年4月25日至29日，虚拟活动，法国里昂 Papachristou和Kleinberg0(a) 节点j的模型设置。0(b) X = 0的玩具实例。0图1：Eisenberg-Noe模型。0模型[19]是一种具有收入冲击的传染模型，旨在最大化福利目标。我们证明，在离散救助方案下找到最优政策是一个NP-Hard问题，开发近似算法，并证明近似难度。然后，我们转向模型内与救助提供中的公平性和公平性考虑相关的一组问题。特别地，我们在算法公平性约束下优化与上述相同的目标，该约束通过Gini系数[22]（GC）来考虑刺激分配。我们研究了三种公平性概念：（i）经典GC，用于衡量所有对不平等性，（ii）在我们的模型中调整的GC变体，（iii）基于金融网络中每个节点的属性（例如少数派地位）的新型GC。我们证明，在离散情况下，公平代价（PoF）可能无界，在分数情况下有界。我们将我们的算法应用于来自[15]的真实银行数据集，这些数据集来自银行压力测试，以及通过匿名的Web移动性数据从SafeGraph平台，美国人口普查和美国经济普查推断出的社会粒度网络拓扑。我们将所提出的近似算法的结果与这些数据集上的其他基于网络的启发式方法进行比较。我们在半人工数据上经验性地研究了公平性约束的整体节点对之间以及在与少数群体相关的情境中的应用。我们的代码是开源的2。相关工作。EN模型[19]是一个金融网络模型，其中每个节点在内部网络方面都有资产和负债。EN模型的变体研究了冲击[23]，研究了动态版本[6，20]，救助方案[3，18，24]和信用违约掉期[37，40]。具体而言，[3]的工作考虑了与我们的论文研究的离散干预方法相反的预算约束下的分数干预方法。最后，该问题与影响最大化（IM）[10, 28]有关。02 模型0设置。EN模型考虑了一个支付网络G（[n]，E）的有向网络，具有以下结构。网络有n个节点和内部负债，这些负债在有向边E上表示。支付网络的每个节点j∈[n]都有资产的外部流入c j ≥ 0和外部负债b j ≥0，这些资产和负债对应于节点的外部交易。关于外部负债的一种直接思考方式是自然人和法人欠政府的税款。在两个节点（j，i）∈E之间，有一个从j到i的负债p ji ≥0，它表示j欠i多少钱（以货币单位计，例如美元）。节点j的初始财富或权益由w j = c j + � i : i � j p ij − p j给出，其中p j =b j + � i : j � i p ji是节点j的累积负债。网络中没有孤立节点，即每个节点j都有p j >0（无论是外部负债还是内部负债或两者兼有）。对于β j = (p j − b j)/pj，我们将其称为节点j的金融连通性，即j在网络内所欠的总负债的比例（不要与图连通性混淆；另请参阅[23]）。我们定义βmin = min j ∈[n] β j和β max = max j ∈[n] β j。每个节点的资产受到随机冲击X j ∈ [0，c j][23]的干扰。在冲击下，每个节点能够向其债权人支付金额¯ p j ∈ [0，p j]。如果节点是偿债能力强的，则¯ p j = pj。否则，节点将违约给其债权人，并根据它欠他们的金额来调整其负债，以以降低的利率向其债权人支付。相对负债矩阵A的定义是，当p j > 0时，a ji = p ji / p j，否则a ji =0。当接收方具有高粒度（即个人、小企业）时，标准的救助策略是从一组固定资源中救助个人3。因此，为了（或许部分地）避免冲击，决策者可以根据预算约束Λ > 0向节点子集发放价值为L j的刺激支票。清算支付向量¯ p由EN均衡方程给出。02 源代码：https://github.com/papachristoumarios/financial-contagion。0¯p = p ∧ �AT¯p + c − X + L⊙¯z� (1)0其中¯z ∈ {0,1}n是决策变量，⊙是Hadamard乘积。支付受到预算约束L�¯z ≤Λ的限制。违约节点的集合被定义为集合D = {j : ¯pj
0，则¯p是唯一的。0Φ(¯p) = p ∧ �AT¯p + c − X +L⊙¯z�以迭代地计算在分配¯z下的均衡向量。Φ是增加的、正的和凹的[19]。在本文中，我们依赖于一个非常现实的假设，即每个节点直接向外部部门承担义务，即0假设2. ∥AT∥1 = βmax < 1。0maxEX �D[f(¯p)]0s.t. ¯p ≤ AT¯p + c − X + L⊙¯z, 0 ≤ ¯p≤ p0L�¯z ≤ Λ, ¯z ∈ {0,0(OptBailouts)0其中f是¯p的严格增函数。我们将整体向量表示为¯ξ = (¯p, ¯z)T ∈[0, p] × {0, 1}n。前一种类型的03 当救助少数大型实体时，分数版本更合适[3]。180在危机时期分配刺激支票WWW'22，2022年4月25日至29日，虚拟活动，法国里昂0我们研究的第一个线性目标是均衡状态下支付的总和（具有正系数），而第二个目标是偿付能力节点的总数。从社会和技术的角度来看，最大化这样的目标是合理的（参见[2, 3, 30,33]）。从社会的角度来看，网络中总支付的最大化（具有正系数）会激励（假设诚实的）节点为了社会的利益清偿其债务，因此，每个节点的效用与其能够偿还的债务相对应。从技术的角度来看，已知具有正权重的线性目标会产生清算向量，而偿付能力节点的数量目标也可以稍作修改以产生清算向量。由向量v > 0参数化的线性目标为0f(¯p) = vT¯p，(L-OBJ)0以下线性目标特别重要4：0支付总和：f SoP(¯p) = 1T¯p. (SoP)0内部支付总额：f SoIP(¯p) = βT¯p. (SoIP)0税收总和：f SoT(¯p) = (1 − β)T¯p. (SoT)0分数偿付能力：f FS(¯p) = �0j ∈ [n]0¯pj/pj. (FS)0偿付能力节点的数量目标如下5：0绝对偿付能力：f AS(¯p) = �0j ∈ [n] 1{¯pj = pj}. (AS)0我们在下面给出了离散救助模型的一个例子：0例1（见图2）。令Λ = 1，L = 1，网络具有节点{1, 2}，外部资产c = (302，0)T，外部负债b=(102，1)T和内部负债矩阵P，其中pij=1{ i=j=1}。点质量冲击x=(1，0)T导致节点1违约，进而导致节点2违约，因为冲击后的资产向量是(303给节点2和16给外部债权人，反过来，节点2只能支付103给其外部债权人。最优解是以1单位现金救助节点1，此时资产向量变为(302，0)T再次。我们有OPT SoP=502，OPT SoIP=1。0最后，我们使用以下引理作为我们许多证明的工具。简而言之，引理表明，如果外部资产向量增加（逐点），则相应的清算向量（逐点）大于先前的向量。0引理1（比较引理）。设N1=(P,c1,b)和N2=(P,c2,b)是两个具有c1≥c2（w.l.o.g. withX=0）的EN实例。对于清算向量¯p1和¯p2，有¯p1≥¯p2和vT¯p1≥vT¯p2对于每个向量v>0成立。此外，如果D1是0为了使(SoIP)目标严格单调，我们需要β>0。在(SoIP)目标中，可能存在βj使得βj=0。(AS)目标不是严格递增的。为了获得ϵ-近似，我们增加了目标，包括一小部分总付款添加到由近似参数ϵ>0控制的目标中。0(a)冲击前0(b)冲击后0(c)救助后0图2：示例1。0N1的默认节点，然后向量˜δ =1D1⊙(c1−c2)≥0满足¯p1≥¯p2+˜δ，并且随后vT(¯p1−¯p2)≥vT˜δ。0分数松弛。(Rel-OptBailouts)对(OptBailouts)进行了分数松弛，允许¯zi在连续的[0，1]区间内变化，其中与松弛相关的变量由�ξ=(�p，�z)表示；0max EX�D[f(� p)]0s.t. �p ≤ AT�p + c − X + L⊙�z，0 ≤ �p ≤0L T ≤ Λ，0 ≤ � z ≤0(Rel-OptBailouts)0给定(OptBailouts)的最优解OPT f和(Rel-OptBailouts)的最优解OPTRel f，最优性条件要求OPT Rel f≥OPTf，因为松弛问题具有更大的可行域。(OptBailouts)的可行解称为SOL f，并满足SOL f≤OPTf。最后，我们用¯ξ（resp. � ξ）表示可行解，用¯ξ�（resp. �ξ�）表示最优解。问题的决策版本(OptBailouts)。问题的决策版本将网络的责任矩阵P，外部资产c，内部资产b，刺激向量L>0，刺激值预算Λ≥0用于救助，冲击分布D和下界f�作为输入，并且当且仅当存在一组节点以L进行救助，并且在均衡状态下，我们有EX�D[f(¯p)]≥f�时，回答YES。03近似算法0很容易证明，通过从3-Set-Cover问题[27]的规约，可以证明确定最佳救助方案的问题是NP-Hard的。图3展示了规约的可视化证明，完整的证明可以在完整论文中找到。为了缓解这个问题，我们开发了近似算法。我们的第一个算法基于随机舍入。具体来说，我们解决了在(Rel-OptBailouts)中给出的松弛问题，然后我们应用了一个随机舍入方案，通过以其最优值为偏差进行随机舍入决策变量。虽然舍入方案本身很简单，但分析更加微妙，并且表明该算法实现了1-βmax的近似保证。0对于由系数向量v >0给出的每个线性目标，我们的第二个结果是一种贪心算法，它总是选择具有最大福利增益的节点，同时遵守预算约束。这种类型的算法已被广泛用于∼()ζEZ Be zSOLf=Pr X = x EZ Be zSOLf x190WWW '22，2022年4月25日至29日，虚拟活动，法国里昂 Papachristou和Kleinberg0图3：NP-Hardness约简m个集合S1，...，Sm和n个项目u1，...，un。这里α ∈ (0, 3)。红色边表示价值为1 -α/3的负债。白色节点表示外部部门（作为资产或负债）。金融连接性为βSj = 1 - α/3 ∈ (0, 1)（其中j ∈ [m]），βuj = 0（其中j ∈[n]），βmax = 1 - α/3 < 1。我们设置v = 1。0最大化单调子模函数在基数约束下的问题[32]，例如影响最大化问题[28]、爆发检测[29]、设施选址问题[17]等等，其近似比率等于1 -1/e。尽管我们在本文中分析的线性目标函数族通常不是子模的，但我们能够利用Φ和引理1的性质来调整分析方法，如第3.2节所述。该算法实现了近似保证1 - e - 1 - βmax。0在合理的条件下，ζ -o(1)。此外，爬山算法高效且表现非常好，优于所有基于网络的启发式算法。舍入算法在我们的理论界限中具有更好的最坏情况近似比率，但在实际中表现略差。最后，注意到使用（AS）目标的最优救助方案在输入大小的多项式时间可计算函数内是无法近似的。图4展示了该陈述的可视化证明，再次基于3-Set-Cover问题的约简。完整的证明可以在完整论文中找到。03.1随机舍入近似0在本节中，我们基于随机舍入证明了近似保证。简而言之，我们解决了松弛问题，其中指示变量¯zi允许在[0,1]范围内变化，如（Rel-OptBailouts）中所示。如果ξ� = (¯p�,¯z�)T是松弛问题的最优解，则我们根据以下规则构造相应的舍入解：将每个舍入变量Zi设置为以概率¯z�i等于1，以概率1 -¯z�i等于0。我们首先给出舍入解的预期成本的近似保证。当我们给定冲击X = x时，我们重载符号SOL、OPT、OPTRel，使其分别表示SOL(x)、OPT(x)、OPT Rel(x)，因此SOL =EX�D[SOL(X)]（类似地，OPT = EX�D[OPT(X)]，OPT Rel =EX�D[OPT Rel(X)]）（详见附录6）：06实际上，任何满足E[Zi] ≥ ¯z�i的舍入方案都将在期望上具有相同的近似比率保证。0图4：（AS）近似难度证明概要。这里α ∈ (0, 3)，a(|I|) ∈N*是输入实例大小|I|的多项式时间可计算函数。红色边表示价值为1 -α/3的负债。灰色边表示价值为1 - α/3的负债。0n。最大金融连接性为βmax = 1 - α/3 <1。对于3-Set-Cover问题的YES答案，至少意味着k +a(|I|)∙n个可偿还节点，而NO答案意味着最多k + n个可偿还节点。0定理1. 对于给定的固定冲击X = x，线性目标函数f(¯p) =vT¯p（其中v > 0且ζ = vmax/vmin ≥1），在舍入变量Z下的预期成本满足以下结果：0利用以下事实0（分别为 E Z � Be ( � z � ) � OPT f � ）我们得到了（L-OBJ）在期望上的近似比率为 ( 1 −β max )/ ζ 7。完整的论文还包含了上述算法的运行时间分析。这里我们必须注意一个细微的问题：当我们使用独立的随机舍入方案时，当 L 的条目不同时， L T Z 的方差最多为 104 � j ∈[ n ] L 2 j，因此在满足问题约束的情况下，运行时间可能非常长。例如，如果 L j = 2 j − 1 并且� z � j = 1 / 2 ，那么随机变量 L T Z就是均匀分布0分布在集合 { 0 , . . . , 2 n − 1 }上，理论上运行时间可能是禁止的。虽然这个问题在我们后面的实验评估中没有显示出来，但完整的论文包含了一种缓解问题并以良好运行时间给出相同近似保证的方法。简而言之，我们使用[ 41]中的相关舍入方案（专门设计用于保证不同 L 条目的 L T Z高度集中）作为将线性规划的最优解舍入的预测器。问题的整数间隙 σ f （定义见[ 42]）可用于量化分数最优解和整数最优解之间的最坏情况比率。很容易得出结论，每个线性目标的整数间隙可能变得无界。具体来说，我们从完全网络 K n 开始，其中 c i = b i = 1 且 p ij =1，并且有一个点质量冲击 X i = ε ，其中 ε ∈ ( 0 , 1 )。我们还让 L = nε / k ∙ 1 且 v > 0 。在分数最优解中，我们有� z � i = k / n 且 ∥ v ∥ 1 ∙ n 的最优值被实现。07 目前尚不清楚这个分析是否紧密，以及是否可以找到具有更好近似保证的算法。¬qqj give the numerator of the (Prop-GC). The denominator of the(Prop-GC) is �j ∈[n] qjLj ¯zj:PGC(¯z;q) =�j,i ∈[n] qj(1 − qi)|Li ¯zi − Lj ¯zj |2 n − nq� · �j ∈[n] qjLj ¯zj.(Prop-GC)·1 reduces (Prop-GC) to the conventionalGC. Moreover, for L = ℓ · 1 and qT ¯z = 0 we observe that (Prop-GC)200在危机时期分配刺激支票 WWW ’22，2022年4月25日至29日，虚拟活动，法国里昂0当我们选择将 k 舍入到节点时，我们在所有 k-集合上均匀选择（因为� z � i = k / n ）。因此，最优值就是0给定任何 k -集合的值都设置为1，舍入的节点的救助金足以避免冲击，因此它们将被截断为值 ε，根据问题约束（债务只能以最多其全额支付）。由于所有节点都处于边缘违约状态（对于截断值的救助节点也是如此），我们有（见附录6中的（3））（ 1 / n ） � j ∈[ n ] ¯ p j = n − nε + kε，这意味着 OPT f = v T ¯ p ≤0∥ v ∥ ∞ [ n ( n − ε ( n − k ))] 。因此我们有 σ f ≥ ζ − 101 − ε ( 1 − k / n )01 − ε ，对于 ε → 1 ，这可能非常糟糕。03.2 贪心算法0我们考虑一族贪心爬山算法，以找到线性目标 f ( ¯ p ) = v T ¯ p的最优救助集。这些算法在 k ≤ Λ / L min步骤中运行，每个步骤中它们选择具有最大边际增益的（可行的）元素，直到违反预算约束为止，即给定固定冲击 X = x时，当前救助集合为 S t ，其中 S 0 = � ，我们有 u t + 1 ∈argmax u ∈[ n ]\ S t feasible � v T ¯ p S t ∪{ u } − v T ¯ p S t �。该算法类似于[ 32]中用于约束单调次模最大化的爬山算法，它保证了一个 ( 1 − 1 / e)-近似比率。下面我们证明在小救助制度条件下，我们的算法实现了一个近似比率为 1 − e −( 1 − β max )/ ζ − o ( 1 )。我们首先陈述小救助制度条件，该条件表明每当节点获得救助后，它在救助后仍然处于违约状态（但价值更大）。重要的是要注意，我们考虑的爬山算法族在违反小救助制度的实例上仍然可以运行，并且在实践中，贪心爬山算法是表现最好的算法，但是只有在满足该条件时才能保证理论保证。同样，给定固定冲击 x的近似保证后，我们可以后续论证该保证在期望中实现。我们陈述我们的假设0条件1（小救助制度）。在D的随机性下，对于每一步t，算法选择的节点ut产生一个清算向量¯pSt，使得¯pSt,ut < put。0这个条件表示我们在第t次迭代中包含的每个节点ut在¯pSt,ut =put的约束和默认约束不活动的情况下都没有“饱和”。在这个条件下，贪婪算法的近似比率如下：0定理2.在C1的条件下，对于每个线性目标，贪婪爬山算法都可以实现0SOL f ≥ (1 - e^-(1 - βmax)/ζ) ∙ OPT f0通过样本进行期望。通过独立采样一些冲击X1，...，Xm，应用近似算法m次，然后计算经验均值来评估EX�D[∙]。在完整的论文中，我们证明当我们通过样本来近似期望时，近似比率会以O(ε)的精度参数减少。04 公平性 4.1公平性度量0如果分配（离散或分数）遵守以下属性，我们称其为节点之间的公平分配：某个节点获得的救助金额与其邻居节点之间的差异不大。例如，“邻居”可以指所有节点对之间的不平等，具有特定属性的节点之间的不平等，以及实际网络中的节点之间的不平等。所有度量都必须是齐次的，即将所有救助金额乘以一个正数不应该影响它们的值。我们考虑以下约束来将公平性纳入我们的模型中：基尼系数。基尼系数[22]衡量了所有节点之间的刺激分配的公平性，定义为0GC(¯z)=0|L�i zi - L�j zj|02n Σj∈[n] (L�j zj) (GC)0当刺激均匀分布时，它的值为0，当一个节点获得所有救助金额时，它的值为1 - 1 /n。一个有用的优化约束是使基尼系数最多为д ∈ [0,1]，或者等价地说，对于所有的i，j ∈ [n]，满足 |L�i zi - L�j zj| ≤ 2nд 且对于所有的j ∈[n]，满足L�jzj。我们称基尼系数最多为д的分配为д-不公平分配。我们注意到这个度量的一个可能的缺点是它没有考虑到每个个体节点的债务，即它将所有节点都视为平等。这个问题通过下面介绍的(Sp-GC)度量得到缓解。基尼系数属性。我们在第5节中介绍的来自SafeGraph和美国人口普查的真实世界数据集包括描述节点的属性。这些数据集中的一个关键属性是业务所有者的少数族裔地位，如果这样的业务作为节点参与网络，或者一组人的人口统计特征，例如在我们希望施加公平约束的人口普查区块组中属于少数族裔群体的人口比例（即以近似方式衡量不同群体之间的相对援助）。这种类型的数据引发了以下度量：我们引入属性基尼系数(Prop-GC)，其中节点可以具有我们感兴趣的属性（例如SafeGraph或人口普查数据中的人口群体），我们希望在这个属性上应用公平分析。我们通过一个属性向量q ∈ [0, 1]n来建模，其中每个元素qj对应于节点j ∈[n]具有该属性的概率，如下所示：我们令nq = Σj∈[n]qj和n¬q = n -nq为（软）二分图的总权重。对于每个节点j ∈[n]，不平等性取决于是否属于少数群体，即为10注意，当 q = 1 时08 这里的“邻域”概念是一般性的，不一定指网络模型中定义的“邻域”。WWW ’22, April 25–29, 2022, Virtual Event, Lyon, FrancePapachristou and KleinbergSGC(¯z;A) =�(j,i)∈E aji |Lj ¯zj − Li ¯zi |2jn βjLj ¯zj(Sp-GC)4.2Problem Formulation & Price of FairnessmaxEX ∼D [f (¯p)]s.t.(¯p, ¯z) ∈ (OptBailouts) constraints,�i,j ∈[n] |Li ¯zi − Lj ¯zj | ≤ 2nдLT ¯z(GC-Problem)maxEX∼D�f (�p)�s.t.(p,z) ∈ (Rel-OptBailouts) constraints,2T210由于分母趋近于零，它变得无界。其中一种情况是当 q 和 ¯ z是一个0/1向量，并且当 q 的条目为1时， ¯ z的条目为0，反之亦然，当 q 的条目为0时， ¯ z的条目为1，这对应于将所有救助分配给多数群体。我们称满足(Prop-GC) 且最多为 д 的分配为 ( д , q ) -不公平。注意，(Prop-GC) 约束可以与 (GC)约束结合使用，如下所示：给定 д b , д w ≥0，我们寻求找到同时满足两个公平性约束的分配，即 PGC ( ¯ z ; q) ≤ д b ，以及 GC ( ¯ z ⊙ q ) ≤ д w 和 GC ( ¯ z ⊙ ( 1 − q ))≤ д w 。空间基尼系数。为了使 GC考虑到网络效应，我们定义其空间类比，即 (Sp-GC)，如下所示：0上述定义也出现在 [ 31 ]中，其中假设图具有单位权重。在我们的情况下，无权图的角色由相对责任矩阵 A 扮演。由于 A 是亚随机的，每行的总权重为 β i <1，边 ( i , j ) 的贡献为 a ij 。通过对和进行归一化，即 � j ∈[ n ]β j L j ¯ z j，可以比较不同人群和不同救助规模。当救助平均分配时，(Sp-GC)为0。如果 A = A T 并且一个节点获得所有救助，则 (Sp-GC)由1限制。我们称满足 (Sp-GC) 最多为 д 的分配为 ( д , A ) -不公平。我们在这里指出，与 (GC) 不同，(Sp-GC)指标考虑了每个节点的债务，即节点 j 对节点 i有显着的（与其邻居相比）责任，即它有 a ji ≈ β j，那么这种偏差在系数计算中将获得比与其余邻居的偏差更高的权重。在完整的论文中，我们证明了当 A = A T 时，(Sp-GC) 指标与A 的导纳有关。0我们对涉及上述公平性度量的优化问题提出了以下松弛：对于目标公平性度量上界 д ≥0，首先，我们考虑以下优化问题，它通过添加依赖于 GC的约束来扩展 (OptBailouts) ：0� ϖ ij ≥ 0 , − � ϖ ij ≤ L i � z i − L j � z j ≤0（Rel-GC）0对于公平性界限д≥0，可以相应地制定（Prop-GC），（Sp-GC）的优化问题放宽。这些问题的最优分数解考虑分数分配，而它们的离散对应物考虑离散分配。0然后，我们可能会问一个自然的问题，“这些公平性约束对福利目标函数的最大影响是什么？”我们定义公平性价格（PoF）[8]为0PoF = 0具有公平性的OPT。0显然，由于分子中的值指的是具有比分母中的值更大的可行区域的优化问题，因此总是PoF≥1。乍一看，一个自然的问题出现了：是否存在实例，使得离散/分数分配的PoF无界/有界？对于这个问题的答案给出了以下定理（App. 6）：0定理3（PoF有界性）。（1）存在有限的实例，其中对于离散救助，对于（GC），（Prop-GC）和（Sp-GC）定义的所有约束以及由系数向量v>0给出的任何线性目标，PoF是无界的。0（2）对于每个递增的目标f，其中f（0）= 0，∥f∥∞<∞，对于每个д≥0，分数救助的PoF是有界的（对于所有公平性度量）。05个实验0数据集。在本节中，我们使用来自两种来源的公共数据集评估我们的方法：高级别粒度数据，涉及到一个国家的金融机构对应的节点之间，国家之间的金融机构，或者同一国家的不同金融部门之间的金融交互；以及低级别粒度数据，涉及到由美国人口普查定义的匿名人群组的节点之间的数据。在后一种情况下，由于个人隐私考虑，相关的公共数据集通过匿名化或聚合进行了限制。我们使用以下数据集：德国银行。来自[15]工作的22家德国银行的数据集，报告了德国银行的内部和外部资产和负债。数据集包含n = 22，m =435条边，平均出度¯dout = 19.8。网络结构可以用ER网络G（n =22，p =0.94）来描述。SafeGraph。基于SafeGraph平台的移动数据生成的数据，时间为2020年4月。金融网络中的节点表示：（i）兴趣点节点（POI节点），它们根据其NAICS代码将各种业务分类为
我的内容管理
展开
