带有衍生品的金融网络清算：从难解性到算法

《Information and Computation》：Clearing financial networks with derivatives: From intractability to algorithms

　　

金融网络背景下的清算问题是评估一家公司对系统性风险敞口的计算挑战，即公司的资产与负债比率，称为清算回收率（clearing recovery rate）。当仅涉及简单债务合同时，该问题是易处理的；而当存在称为信用违约互换（Credit Default Swaps, CDSes）的复杂衍生品合同时，该问题是FIXP-完全的，并且对于一个小但未明确指定的常数?，寻找近似?-解是PPAD-困难的。研究人员提出了一个从Pure-Circuit问题到涉及CDSes的清算问题的直接归约，并建立了改进的?-解的显式不可近似性界限。研究人员证明了对于?≤2?34，寻找?-解是PPAD-困难的。即使在引入中央清算机构后，这种难解性仍然存在。此外，研究人员提供了一个基于优化的框架，用于在存在中央清算机构的情况下计算问题的精确解，以及当这些机构与覆盖型CDSes（covered CDSes）相结合时的一个简单多项式时间算法。

**论文解读：带有衍生品的金融网络清算：从难解性到算法**

**研究背景与问题**

金融网络系统性风险的研究中，核心计算挑战是清算问题（clearing problem），即计算每家银行在系统一次性清算时应支付的负债比例，该比例被称为清算回收率（clearing recovery rate）。Eisenberg与Noe的开创性工作建立了该问题的数学形式：当仅涉及简单债务合同时，清算回收率对应某函数的不动点，且存在多项式时间算法。然而，当引入名为信用违约互换（Credit Default Swap, CDS）的衍生品合同时，问题变得极为复杂。CDS是一种价值基于第三方（参考银行）回收率的合约，其投机性被认为是2007年金融危机和2011年欧债危机的诱因之一。Schuldenzucker等人将包含CDS的金融网络模型化为一个不动点问题，但该问题可能产生无理数的清算回收率，使得精确计算在计算上不可行。因此，研究的焦点转向近似解：弱近似（weak approximation）要求找到向量x使得|x-f(x)|
**研究内容与结论**

研究人员通过从Pure-Circuit问题到清算问题的直接归约，证明了对于?≤2-√3/4（约0.0669），计算弱?-近似清算回收率是PPAD-困难的。该下界显著优于此前未明确的下界（约1/150）。进一步，即使要求使用中央CDS债务人（Central CDS Debtor, CCD，类似于中央清算对手方），该难解性依然成立。在正面结果方面，研究人员为包含CCD的金融网络提出了一个混合二元线性规划（Mixed-Binary Linear Program, MBLP）框架，可精确计算清算向量，从而得到一个指数时间算法。当CCD与覆盖型CDSes（covered CDSes，即CDS的名义本金不超过参考银行相关债务的本金）同时被强制采用时，研究人员设计了一个多项式时间算法，通过将覆盖型CDS转换为纯债务合同，进而利用Eisenberg-Noe的多项式算法求解。这些结果发表在《Information and Computation》上。

**主要技术方法**

1. **Pure-Circuit归约**：利用Pure-Circuit问题（变量取值{0,1,⊥}，含NOT、OR、PURIFY门）的PPAD-完全性，构造金融网络“门”（如NOT门、OR门、PURIFY门），使得任意?-近似清算向量经过映射m_δ（将[0,1]空间划分为[0,1/2-δ]→0, (1/2-δ,1/2+δ)→⊥, [1/2+δ,1]→1）后对应于满足Pure-Circuit实例的赋值。通过一阶语言L(R,F,C)处理区间运算，简化门行为的分析，并优化参数δ以最大化不可近似性下界。

2. **混合二元线性规划**：针对具有中央CDS债务人（CCD）的网络，引入二元决策变量y_i指示银行i的偿付能力（资产>负债或资产<负债），将不动点条件中的min算子线性化，构建MBLP，其可行解集即为所有清算向量。通过枚举2^|N|种y配置并求解线性规划，得到指数时间算法。

3. **覆盖型CDS转换**：对于同时具有CCD和覆盖型CDS的网络，对每个覆盖型CDS执行转换步骤：增加参考银行R对虚拟节点的债务，调整相关方的外部资产和债务本金，从而将CDS消除，得到仅有简单债务的等效网络，再使用Eisenberg-Noe的多项式时间算法求解。

**研究结果**

**第3节：?-Cds-Clearing的难解性**

- **3.1 现有技术水平**：总结此前结果：通过?-Generalized-Circuit归约得到?<1/150时的PPAD-硬度，本研究实现了约十倍的改进。

- **3.2 一阶语言**：定义语言L(R,F,C)，包含关系符号?（区间偏序）、函数符号{+,?,·,/}及常数符号，专门处理[0,1]内的区间运算；给出有效替换规则（如σ_1?, σ_±, σ₊, σ_*）和引理2（若x≥y则y?x），用于分析金融门中输出银行回收率区间的包含关系。

- **3.3 将Pure-Circuit归约到?-Cds-Clearing**：构造映射m_δ，并分别设计NOT门、OR门、PURIFY门的金融网络，通过一阶语言推导出在任意?-近似清算向量下输出银行回收率所在区间（如Claim 1-3）。通过求解函数?(δ)=δ·(1-2δ)/(1+4δ)的最大值，得到最优δ*=(√3-1)/4，对应?*=2-√3/4≈0.0669。定理2宣告该下界的成立。推论1表明该结果适用于任何满足有限责任和绝对优先的支付方案。

**第4节：特殊金融拓扑的（难）可解性**

- **4.1 中央CDS债务人**：定义中央CDS债务人（CCD）为所有CDS的唯一债务人、无债务合同、资产充足。推论2表明?-难解性仍适用于CCD实例。正面结果为定理3：针对CCD实例的混合二元线性规划（MBLP）的可行解与清算向量一一对应。定理4据此给出指数时间算法（算法1），可优化任意线性目标函数（如总流动性最大化）。注1讨论该框架可解决文献中因多重清算向量导致的“违约歧义”问题。

- **4.2 中央CDS债务人与覆盖型CDSes**：定义覆盖型CDS（covered CDS）满足c_i,j^R ≤ c_R,j。定理5：当网络同时具有CCD和覆盖型CDS时，存在多项式时间算法。证明通过转换步骤（将每个覆盖型CDS转化为债务合同和虚拟节点），得到纯债务网络，使用Eisenberg-Noe算法求解（算法2）。并指出该算法可推广到多个高资本CDS债务人的情形。

**讨论与结论**

**讨论部分**：本研究首次给出Cds-Clearing问题的大常数显式不可近似性下界，为后续理论研究及启发式方法奠定基础。主要开放问题是如何改进下界；直觉上可通过减少门中CDS合约数量来降低误差。后续工作Dohn等人通过优化PURIFY门系数获得了改进的下界，但其近似定义略有差异。设计多项式时间近似算法是重要挑战；在缺乏纯算法方法时，所提出的MBLP可用于经验性研究。另一个方向是基于机器学习的清算向量算法。

**研究结论**：定理2：计算?-弱近似清算回收率在?≤2-√3/4时是PPAD-困难的。定理3与4：对于具有中央CDS债务人的网络，存在指数时间算法计算精确清算向量并优化线性目标。定理5：当网络同时采用中央CDS债务人和覆盖型CDS时，存在多项式时间算法计算精确清算向量。这些结果与禁止裸CDS的监管政策一致，并为实际应用提供了首个精确可解方案。