一种计算有传递的所得税的分解算法

这确保给定向量E（0）和sharesP矩阵∈ P、 如果我们使用算法1进行迭代，我们只有一个最终的个人初始收入分布。然而，正如我们在下一节所示，没有必要同时分配所有公司的收入。事实上，如果我们只分配任意子集的公司的收入（记住，负收入的公司不会分配），则最终归属收入的向量与使用算法1.4股份矩阵的数学性质计算的向量相同。下一个引理表明，无需迭代，计算归属收入的唯一原因是要知道哪些公司的最终归属收入为负值(∞)= {i∈ NS：E(∞)i<0}。引理1。让P∈ P是一组公司n的股份矩阵。那么，对于任何子公司 NSPS·P∞= P∞.注意，这个引理意味着PkSP∞= P∞对于任何k=1。∞. 这将是下一节中提出的算法的关键。证据根据方程式（2），PS·P的第i行∞如果我/∈ S由（PS·P）给出∞)io=（PS）io·P∞= Pio·P∞= P∞io其中给出了最后一个等式，因为P·P∞= P∞. 相反，如果我∈ S、 然后（PS·P∞)io=（PS）io·P∞= ei·P∞= P∞io证明结果。前面的引理说，如果在一次迭代中，我们不对一个子公司S的收入进行属性化，而在接下来的迭代中，我们像往常一样使用矩阵P对收入进行属性化，那么最终的属性化收入将与我们不跳过任何迭代的情况相同。

此外，因为在所有步骤i中，子集S（ni）包含最后的子集S（nk），引理1表示pns（n）·Pn-nS（n）·Pn-nS（n）···Pnk-1.-nk公司-2S（nk-1） ·P∞S（nk）=P∞此外，P∞S（n）·P∞S（n）·P∞S（n）··P∞S（nk-1） ·P∞S（nk）=P∞S（nk）。因此，从方程（5）中，最终归属收入的向量可以计算为(∞)= E（0）P∞S（nk），其中S（nk）=S（E(∞)).该属性表示，如果我们能够猜测将以负归属收入结束的公司子集，我们只需一步就能找到这种最终状态。不幸的是，无法先验地知道集合S（E(∞)) 以负属性结束的公司的数量来自初始信息P和E（0）。然而，下一个定理表明，当开始在每次迭代中分配公司的任意子集（记住，具有负归属收入的公司不会分配）然后返回到通常的经营时，该算法仍然收敛到最终归属收入的向量E(∞).定理1。设{E（j）}j≥0是一系列收入向量，使得^E（0）=E（0）和^E（j）=^E（j-1） PT（j-1） 对于j=1。K其中T（0），T（k-1） 是指T（j）公司的子集 S（^E（j）），且设^E（j）=^E（j-1） PS（^E（j-1） ）对于j>kthen，limj→∞^E（j）=E(∞).证据请注意，如果^E（k）满足S（^E（k）） S（E）(∞)), 那么从引理1，我们知道PT（0）··PT（k-1） ·P∞S（E）(∞))= P∞S（E）(∞))（9） 因此，^E(∞)= E（0）·P∞S（E）(∞))= E类(∞).让我们假设有一个i*∈ S（E）(∞)) 使^E（k）i*> 在不丧失一般性的情况下，我们可以假设这是第一次迭代*存在。因此，S（E(∞)) * S（^E（k））butS（E(∞))  S（^E（k-1） ）。

在这种情况下，等式（9）仍然成立，andE（0）·PT（0）·PT（k-1） |{z}E（k）·P∞S（E）(∞))= E（0）·P∞S（E）(∞))= E类(∞)然而，这是不可能的，因为^E（k）i*> 0和i*∈ S（E）(∞)), 所以我*不分配其收入，以及组成部分i*of^E（k）·P∞S（E）(∞))必须大于0，导致矛盾。这个定理意味着，如果我们从E（0）开始，我们能够找到一个收入向量“E”，比如“Ei”≤ 0我∈ NS，使用子集T（0），T（k-1） 根据定理中指出的性质（即使我们使用矩阵PTi在有限时间内迭代），\'E是向量E(∞), 因为“EPS（\'E）=”E。这个断言是理解下一节中提出的算法有效性的关键。5计算最终归属收入的算法算法算法1可能需要有限的迭代次数才能收敛到最终归属收入，这是不允许的。这可能会受到迭代的限制，直到一小部分还没有被归属，但仍可能导致多次迭代。通过迭代计算（n+1）=E（n）P，从引理1和方程（3）计算最终归属收入向量的不同方法∞S（n），其中S（n）=S（E（n））。此过程将在不超过| NS |次迭代中完成。然而，从计算的角度来看，反转大型矩阵的成本很高。具体而言，sizek×k密集矩阵的反演计算复杂度为O（k2.3728）（见Le Gall 2014、Coppersmith和Winograd1987）。尽管如此，大多数软件，包括事实上的标准库LAPACK（Andersonet al.1999），都实现了经典的O（k）算法。因此，所提出的解决该问题的算法对于许多公司来说都是难以计算的。定理1证明，我们可以将问题分解为更小的子问题，以获得最终的属性收益。

分解问题的自然方法是使用强连接组件。给定参与矩阵P，我们可以定义一个有向图G=（V，a），其中每个顶点V∈ V是纳税人，我们加了一个弧（u，V）∈ A当且仅当puv>0时。此图上的强连接组件表示所有公司都间接拥有自己的一个子集。众所周知，任何有向图都可以分解为一组强连通分量，这样，如果我们将每个强连通分量收缩为avertex，我们就会得到一个有向无环图（见Bang-Jensen和Gutin 2008）。此外，Tarjan\'salgorithm（Tarjan 1972）允许将图分解为强连通的组件，并返回它们在时间O（| V |+| E |）上的非循环排序。因此，我们可以应用这种分解来更有效地解决我们的问题。给定强连接组件的非循环记录，我们可以计算给定组件中每个付款人的归属收入，并将其分配给其他强连接组件中的相应股东。

由于这是一种非循环排序，初始部分中的纳税人将不会获得进一步的收入，因此获得的归属收入将是确定的。算法2计算每个纳税人的归属收入输入：纳税人NS，NP，参与矩阵P，初始收入E（0）输出：归属收入E1:E← E（0）2：执行Tarjan算法计算强连通组件的无环排序。3： 对于每个强连接组件C do 按照之前计算的非循环顺序4：如果C={v}，则 组件只有一个顶点5：如果Ev>0，则 纳税人有正收入6：对于每个股东 将其收入分配给股东7：欧盟← 欧盟+Ev·puv8：9月底：欧盟← 010：结束if11：其他 组件至少有两个corporations12:repeat13:Redo← 014:S← NS \\{v∈ C：Ev>0} 仅考虑收入为正的C公司15:E← E·P∞S 将其收入分配给股东16：如果存在v∈ CT使Ev>0，然后17：重做← 1. 负收入的公司现在有正收入18:end if19:until Redo=020:end if21:end forPseudocode所提出的算法如算法2所示。请注意，对于每个强关联的组成部分C，为了获得其纳税人的最终归属收入，需要反演一个大小不超过| C |的矩阵，每次C中的纳税人以负收入完成正收入时，都会重复该矩阵。因此，获得组件的attributedincome的计算复杂性要求对大小为| C |的矩阵进行不超过| C |的逆运算。

因此，只有当强连接组件的大小很小时，才适合使用此算法，这在公司网络中是预期的，我们将在下一节中看到。在算法结束时，企业的归属收入E为非正，个人的归属收入E为非负。因此，我们的最终归属收入E满足E=E·PS（E），因此根据定理1及其后续讨论，所得收入实际上是最终归属收入E的向量(∞).6计算实验和数据分析我们提出了一种获得最终归属收入的算法，并表明其性能取决于其连接组件的大小，因此强烈依赖于网络的拓扑特征。因此，在本节中，我们将对智利纳税人网络进行分析，以了解其特点，并在此网络上对我们的算法进行基准测试。本节所述数据由智利税务局提供，与2015财年相对应。最初的纳税人网络由1240809个个人和786293个公司组成，通过2568 182个链接连接，其中≈ 90%的人将公司与个人联系在一起。然而，我们可以通过删除一些无关紧要的组件来简化这个网络，这些组件包括一个公司，它什么都不拥有，只属于个人。由于收入分配可以在算法1的一次迭代中求解，因此这些组成部分是微不足道的。

经过简化后，新的纳税人网络由356 372名个人和152 914家公司组成，其中有1 122 875个链接≈ 75%的人将公司与个人联系在一起。在简化网络中，公司平均拥有1.78家公司，每个公司的平均所有者数量为7.23人，其中5.48人为个人，1.75人为公司。此外，40%和34%的公司的内部学位分别为0和1，45%的公司的外部学位为2。此外，个人拥有的公司平均数量为2.39家，其中56%和20%的个人拥有1级和2级学位。问题的复杂性是由公司而非个人给出的。因此，我们通过删除个人来分析公司网络。该网络有152个135个强连接组件，其中只有268个包含多个节点。如图1所示，268个组件中的200个由2个节点组成，最大的组件由396个节点组成。因此，使用本文描述的算法，我们必须求逆的最大矩阵是396×396矩阵。如图2和图3所示，最大的强连接组件中的公司是高度连接的。

实际上，该组件节点的平均出度和入度均为8.21（仅考虑属于该组件的两个节点之间的链接）；有10家公司直接连接到组件的100多个其他节点，超过10%的节点直接连接到至少40个节点。虽然只有一个复杂的强连通分量，但许多强连通分量是弱连通的，为总共91 011家公司创建一个由90 322个强连接组件组成的大型弱连接组件（如果我们不删除图1：强连接组件的大小图2：最大强连接组件中节点的入度和出度图3：最大强连接组件图弱连接组件分析，最大弱连接组件将连接462 649个纳税人，超过简化网络的90%的节点）。这增加了问题的复杂性，因为算法必须尊重强连接组件的优先级。然而，81%的弱连接组件由不超过3家公司组成。本文描述的算法是使用C编程语言实现的，使用BLAS/LAPACK库来反转矩阵。注意，即使矩阵Q是parse，则（I）的逆- Q） 不一定是稀疏的，因此必须为整个矩阵Q分配内存。这使得使用公式（5）无法解决问题，因为Q的大小为152 914×152 914，需要150 GB以上的RAM才能反转此矩阵。我们为这个数据实例实现了算法2。该算法需要344个矩阵求逆来计算最终的归属收入。完整的算法运行时间不到10秒。

相比之下，算法1的实现需要几个小时才能完成，直到公司的最大收入低于1美元。7结论通过与马尔可夫链的类比，我们构建了一个有效的算法来计算流转税制中纳税人的最终归属收入。算法的复杂性取决于纳税人网络中最大的强连通组件的大小。我们还认为，这一最终收入是独一无二的，对于公司归属于收入的任何顺序都是稳健的。这一事实允许我们将问题分解为强连通的组件，这些组件可以使用Tarjan算法获得。分解是所提出算法的关键特性，使我们能够在几秒钟内求解大规模网络。快速计算所得税的算法可以帮助税务机关进行进一步的分析，例如评估混合系统的影响，允许实体选择是否将其收入归属，预测未来几年的税收，评估免税的影响，或者简单地计算从不同类型的实体（如外国公司）获得的收入。

在更一般的情况下，对于任何国家（有或没有传递实体），这种方法可以更好地估计最富有的十分位数的财富分配情况，这在基于调查的研究中通常被低估（世界银行，2015年）。致谢作者感谢研究部Servicios Incpuestos Internos，特别是Carlos Recabarlen，向我们介绍了这个问题及其相关性，以及他们的宝贵合作，使我们获得了这些结果。参考安德森、爱德华、白昭君、克里斯蒂安·比肖夫、苏珊·布莱克福德、詹姆斯·德梅尔、杰克·东加拉、杰里米·杜克罗兹、安妮·格林鲍姆、S·哈默林、艾伦·麦肯尼等，1999年。LAPACK用户指南，第9卷。工业和应用数学学会，费城，宾夕法尼亚州。Bang-Jensen，Jorgen，Gregory Z Gutin。有向图：理论、算法和应用。SpringerScience&Business Media。比约纳、安德斯、拉兹洛、洛夫、阿斯茨。有向图上的芯片游戏。代数组合学杂志1（4）305–328。Burnham，Paul F.2012年。通过个人所得税对企业征税。技术代表、国会预算办公室、美国国会。URL地址http://www.cbo.gov/publication/43750.Coppersmith，Don，Shmuel Winograd。通过算术级数进行矩阵乘法。第十九届ACM计算理论年会的筹备工作。ACM，1–6。恩格尔，亚瑟。1975年。概率算盘。数学教育研究6（1）1–22。法国勒加尔,科伊斯。张量幂和快速矩阵乘法。第39届符号和代数计算国际研讨会论文集。ACM，296–303。美利奴，克里尔。芯片游戏。离散数学302（1）188–210。塔扬，罗伯特。深度优先搜索和线性图算法。暹罗计算杂志1（2）146–160。世界银行。2015