| paper | d4-conf-sagt-2025-0008 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: For every fixed rational \(\alpha\in[0,1)\), clearing existence is \(\exists\mathbb{R}\)-complete and hence \(\mathrm{NP}\)-hard, even with equal masses. An exact decision algorithm runs in \((\tau+1)^{O(\tau)}L^{O(1)}\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given finitely many types \(T\) with positive rational masses μ_t summing to \(1\), per-institution external assets \(e_t\), and debt and CDS schedules \(d_{st}\) and \(h_{st\mid v}\) between types, with obligations allocated pro rata, decide whether there exists \(r\in[0,1]^T\) satisfying the paper's clearing equations for fixed α<1 and β=1. Here \(q_{st}(r)=d_{st}+\sum_v(1-r_v)h_{st\mid v}\), \(L_s(r)=\sum_t q_{st}(r)\), and \(I_t(r)=\sum_s(\mu_s/\mu_t)r_s q_{st}(r)\); type \(t\)'s assets are \(A_t=e_t+I_t\) and its post-default-cost assets are \(A'_t=\alpha e_t+I_t\).
A finite-support population of interchangeable institution types, each with mass μ_t and shared per-institution assets and exposure schedules. The decision variables are type recovery rates \(r_t\); the task is to decide whether they satisfy the type-level clearing equations. Exact aggregation turns each type into one bank with assets and contracts scaled by its mass.
The type model aggregates exactly to a finite τ-bank network, while institution-specific counterparties may force τ to grow with the population; the proponent acknowledges the homogeneity limitation but does not address this exact reverse aggregation.
fatal: False
The mirror covers Theorems 1, 3, and 4. It leaves the paper's CDS-CanDefault question and the β<1 existence case unresolved.
I would defend a pro-rata type model of CDS clearing. It keeps the paper’s clearing equations and makes the population the continuous object. Take a finite support \(T\), with rational masses \(\mu_t>0\) summing to \(1\). A type is a cohort of interchangeable institutions: members share the same external assets \(e_t\) and the same contract schedule to every other type. Let \(d_{st}\) be the debt a type-\(s\) institution owes to the type-\(t\) cohort, and \(h_{st\mid v}\) the CDS notional it owes that cohort with type \(v\) as reference. Obligations to a cohort are allocated pro rata across its mass.
For a vector of type recovery rates \(r\), write \(q_{st}(r)=d_{st}+\sum_v(1-r_v)h_{st\mid v}\). Type \(s\)’s liabilities per institution are \(L_s(r)=\sum_t q_{st}(r)\), and type \(t\)’s incoming payments per institution are \(I_t(r)=\sum_s(\mu_s/\mu_t)r_s q_{st}(r)\). Set \(A_t=e_t+I_t\) and \(A'_t=\alpha e_t+\beta I_t\). A clearing solution is \(r\in[0,1]^T\) such that \(r_t=1\) if \(A_t(r)\ge L_t(r)\), and \(r_t=A'_t(r)/L_t(r)\) otherwise. The instance includes the rational masses, assets, contract schedules, default-cost parameters, and the usual non-degeneracy condition. The solution is a recovery rate for every type; there is no optimization objective, because the paper’s underlying question is clearing.
The mass ratios matter: they describe how payments from one cohort are spread over another. This is a genuine population model, with cohort shares as inputs, while retaining the paper’s bilateral debt and CDS structure at type level. It is not a continuous outcome or noise model.
My lead anchor is Theorem 3, proved in this paper: for every fixed \(\alpha<1\), deciding whether a non-degenerate financial network with default costs \((\alpha,1)\) has any clearing recovery-rate vector, \(\textsc{CDS-HasClearing}(\alpha,1)\), is \(\exists\mathbb{R}\)-complete. The continuous question is: given the type-model instance above with \(\beta=1\) and fixed \(\alpha<1\), does any type recovery vector satisfy the clearing equations? A solution is such a vector; the decision answer is yes exactly when one exists. This is the strongest anchor for the exact, nonlinear existence question. The paper proves the result by reducing bounded quartic feasibility through polynomial-evaluation and network gadgets, drawing in part on an infeasibility gadget from earlier work.
Two other anchors are worth keeping because they cover distinct clearing questions. Theorem 1, proved here, says that \(\varepsilon\)-CDS-Clearing is PPAD-hard for \(\varepsilon\le 5-2\sqrt 6\approx0.101\). Its instances are non-degenerate networks without default costs, and a valid output \(r\) must satisfy \(\lVert f(r)-r\rVert_\infty\le\varepsilon\) and the solvency guard \(a_i(r)\ge(1+\varepsilon)l_i(r)\Rightarrow r_i=1\) for every bank. Here \(f_i=a_i/\max(a_i,l_i)\). The corresponding continuous problem, Type-CDS-\(\varepsilon\)-Clearing, asks for type rates satisfying those same conditions with \(a_i,l_i,f_i\) replaced by \(A_t,L_t,f_t=A_t/\max(A_t,L_t)\). A solution is the approximate rate vector, not an encoding of it. The paper’s reduction uses Pure-Circuit; Pure-Circuit’s PPAD-completeness is cited from Deligkas et al.
Theorem 4, proved here, says \(\textsc{CDS-CanSurvive}\) is \(\exists\mathbb{R}\)-complete without default costs. Given a network and a bank \(b\), it asks whether some clearing recovery vector makes \(b\) solvent. The continuous question, Type-CDS-CanSurvive, gives a target type \(t^\star\) and asks whether some type-level clearing vector has \(r_{t^\star}=1\); its witness is that vector. The hardness proof again uses polynomial evaluation, this time to make solvency equivalent to a polynomial having a root.
The regime I have in mind is a large clearing consortium of smaller intermediaries—such as member institutions using standardized exposure schedules—with many institutions in each of a smaller number of balance-sheet and contract-pattern classes. A type is complete for this model: members share external assets, default-cost parameters, and obligations to each counterparty class. Their incoming flows are equal because the model allocates claims pro rata. Mass is the fraction of institutions in the class. Real systems with named, idiosyncratic counterparties fit this only approximately; the mirror is most plausible for pooled or standardized exposure regimes.
There is a direct reason the authors should recognize these questions as mirrors of their own. Given any \(n\)-bank instance in the paper, make one continuous type per bank, set \(\mu_i=1/n\), and copy its external assets and debt and CDS notionals into the type schedules. Then \(\mu_s/\mu_t=1\), so each type’s clearing equation is exactly the original bank’s equation. The recovery vectors correspond one to one. This applies to the approximate and decision questions as well. Thus the mirror does not average away the network interactions: its type-to-type schedule retains the original network data, and its clearing conditions are the paper’s. On these unrestricted type instances, I expect hardness to transfer (Class B) for all three anchors.
That transfer does not show hardness when the number of types is fixed or small. In the reduction, the number of types grows with the encoded network. The most useful follow-up questions are therefore whether these problems admit algorithms parameterized by \(\tau\), how the continuous \(\textsc{CanDefault}\) question behaves, and whether the type-level existence problem remains \(\exists\mathbb{R}\)-complete when \(\beta<1\). The paper itself leaves the latter discrete case open.
The weakest point is the economic regime: financial institutions are not usually a vast crowd of interchangeable entities, and their counterparty relationships can be highly specific. My mirror depends on a block-homogeneous, pro-rata exposure model, and its hardness reduction does not establish hardness for a fixed-\(\tau\), empirically typical consortium. I think the case still holds because that regime is a coherent population model of clearing, its aggregate equations follow directly from the paper’s, and it preserves the paper’s central question of computing clearing payments.
The strongest case against these mirrors is an exact aggregation identity. In the proposed model, a cohort’s members share a recovery rate and exposure schedule, and payments to a cohort are allocated pro rata. Replace each type \(t\) by one aggregate bank and set
\[
\widehat e_t=\mu_t e_t,\qquad
\widehat d_{st}=\mu_s d_{st},\qquad
\widehat h_{st\mid v}=\mu_s h_{st\mid v}.
\]
If \(q_{st}(r)=d_{st}+\sum_v(1-r_v)h_{st\mid v}\), the aggregate bank has liabilities \(\widehat L_t=\mu_tL_t\) and incoming payments
\[
\widehat I_t=\sum_s\mu_s r_s q_{st}(r)=\mu_t I_t.
\]
Its assets and post-default-cost assets are therefore \(\mu_t A_t\) and \(\mu_t A'_t\). Since \(\mu_t>0\), the clearing conditions are unchanged. The recovery vectors correspond exactly. The approximate fixed-point map and solvency guard are unchanged too, since multiplying assets and liabilities by the same positive mass leaves their comparisons and ratios intact.
That identity reaches all three anchors. Theorem 3’s type-level existence question is existence for a finite network of \(\tau\) aggregate banks. Theorem 1’s approximate-clearing question has the same map and guard on that network. Theorem 4’s question asks whether the aggregate bank for the target type can be solvent. Rational masses merely rescale rational input values. Conversely, any finite network can be encoded as a type model by choosing positive masses and scaling the per-member contracts accordingly. These are the paper’s computational problems on a reparameterized input, rather than new continuous-population problems.
The proposed “one type per bank” embedding uses \(\tau=n\), so it establishes correspondence but supplies no repeated population. If many institutions genuinely share a type, the aggregation above compresses them to one node per type. This makes the proposed consortium scenario plausible, but also makes its clearing computation exactly a \(\tau\)-bank network computation. If institutions have distinct counterparty and CDS-reference patterns, those patterns are part of a complete type; grouping them while ignoring the differences can change the clearing equations. Then the number of types can grow with the number of institutions, and the supposed multiplicity advantage disappears.
A more ambitious mirror could use a continuum of institution types and an exposure kernel. That might be worth studying in its own right, but these theorems do not specify its input representation or computational problem. Asking whether a named bank survives is also problematic in an atomless model: an individual has measure zero. Asking whether a positive-mass cohort can survive is meaningful, but finite block-constant kernels return to the aggregate-network identity above. A richer kernel model would need new choices about encoded inputs and solution concepts before it became a computational mirror of these results.
This negative case is strongest against the specific finite-support mirror. It is not a proof that no financial-network continuum could ever be useful. A population model for standardized institutions might make aggregation itself economically valuable, and a carefully specified kernel model could lead to new questions. But for the three stated anchors, the cleanest proposed high-multiplicity regime collapses exactly to the paper’s finite network model; the more heterogeneous alternatives require a different model before their computational questions are defined.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.