Computing Tarski Fixed Points in Financial Networks
创建于 更新于
摘要
本文研究金融网络中以Tarski定理为基础的清算（clearing）固定点问题，提出首个强多项式时间算法用于计算最小清算态，算法通过“顺序注入外部资产 + 解若干线性规划（LP）”模拟自下而上的迭代并在每次迭代中处理“洪泛（flooding）”与线性增长两种情况以保证最多2n次重要事件收敛 [page::0][page::1]. 报告同时推广到任意单调分段线性(payment)函数与默认成本(default cost)情形，并给出多项式时间求解最大清算态、判断区间可达性（range-clearing）与在最小清算态下决策并计算债权交易（claims trade, creditor-positive）的多项式算法与结构性结论 [page::2][page::3][page::12][page::17]. 算法复杂度为 O((n+k)·(n^3 + m))，并通过SCC分解、特征向量/线性方程组与LP构建保证多项式可解性 [page::10].
