d4-conf-aaai-2020-1284

A credible mirror is a large assistance programme in which millions of households fall into a much smaller number \(\tau\) of actuarial profiles. A type records everything the allocation problem uses: income \(c_t\), initial reserve \(u_t\), shock arrival rate \(\beta_t\), shock distribution \(F_t\), and social weight \(w_t\). The society is a distribution \(\mu\) over those profiles. This is plausible where eligibility rules and risk models use recurring household categories; it is a regime with \(N\gg\tau\), not a claim that every welfare decision is high-multiplicity.

The allocation should allow a type’s mass to receive different grant amounts. Let \(\lambda_t\) be a measure on nonnegative per-household income subsidies, with total mass \(\lambda_t(\mathbb R_{\ge0})=\mu_t\). Then \(\lambda_t(A)\) is the fraction of society that has type \(t\) and receives a subsidy in \(A\). For per-capita budget \(b\), the constraint is \(\sum_t\int x\,d\lambda_t(x)\le b\). The objective is to minimize
\[ \sum_t\int w_t\,\psi(c_t+x,u_t,\beta_t,F_t)\,d\lambda_t(x). \]
A solution is a collection of these measures, which can be represented by subsidy levels and the mass receiving each. This is a direct high-multiplicity analogue: a finite population maps to measures with atoms of size \(1/N\), and repeated households of a type give repeated atoms at that type’s risk profile. Allowing arbitrary mass splits is the continuum limit of assigning different grants to otherwise identical households.

My lead anchor is Proposition 7, proved in this paper. It says that the paper’s abstract MIN-SUM problem—given explicit descriptions of \(f_1,\ldots,f_n\), minimize \(\sum_i f_i(x_i)\) over \(x_i\ge0\) with \(\sum_i x_i\le B\)—is weakly NP-hard, even when each \(f_i(x)=\min\{1,g_i(x)\}\) for convex \(g_i\). The continuous mirror is Mass-Split MIN-SUM Curve Allocation: its instance is a finite support of response-curve types with binary-rational masses \(\mu_t\), a per-capita budget \(b\), and the same kind of explicitly described penalty curves \(f_t\). It asks for measures \(\lambda_t\) of mass \(\mu_t\) minimizing \(\sum_t\int f_t(x)\,d\lambda_t(x)\) subject to the budget above. This is the same subsidy-and-risk trade-off, while allowing a cohort to split among subsidy levels.

For this mirror, I expect the discrete weak hardness may dissolve when the curves have a tractable representation: with rational piecewise-linear curves and a finite relevant subsidy range, the mass-allocation problem is a linear program over masses assigned to subsidy levels. That would be a Class A result for that input family. It does not follow from Proposition 7 that the paper’s hardness reduction survives this mass-splitting relaxation, and the proposition does not establish hardness for the paper’s particular ruin-probability curves. The further question is whether the same tractability extends to the full clipped-convex curve family and to ruin curves derived from shock distributions, or whether pricing over those curves creates continuum-specific hardness.

A second, more directly risk-specific anchor is Theorem 6, also proved here. It states that for the paper’s min-sum income-subsidy problem with arbitrary shock distributions, initial wealth, and drift, if \(X\) is the optimum, then for any \(\epsilon,\delta>0\) a solution of value at most \((1+\epsilon)X+\delta\) can be found in time polynomial in \(n,1/\epsilon,\log(1/\delta)\). The proof assumes efficient access to the inverse ruin-probability functions; Corollary 9 gives a version using value access under a Lipschitz condition.

Its mirror is Mass-Split Ruin-Subsidy\(_\infty\), the measure problem above with types specified by \((c_t,u_t,\beta_t,F_t,w_t)\) and ruin penalty \(w_t\psi(c_t+x,u_t,\beta_t,F_t)\). I expect a Class A approximation result when the ruin curves have efficient evaluation and pricing or convex-envelope procedures, with running time governed by \(\tau\), input bit length, and approximation parameters. Theorem 6 makes that direction credible, but does not prove it: its dynamic programme allocates to finitely many agents, whereas this mirror can divide a type’s mass across grants. A prover would need to handle that measure-valued choice directly. For convex ruin curves, Jensen’s inequality reduces the allocation to one grant per type; the open difficulty is the general-curve case.

Both mirrors cover the paper’s income-subsidy min-sum objective, not its wealth-subsidy variants or every result in the paper. The authors could plausibly recognize them: the agent-level loss is still ruin probability, the decision is still income subsidy, and the objective is still aggregate weighted vulnerability. The type-level stochastic response curve is also exactly the paper’s own MIN-SUM abstraction.

The weakest point is that Proposition 7’s generic functions need not be realizable as ruin curves from household shock models, while Theorem 6 does not automatically extend to split mass. So the strongest positive claim is a precise, natural high-multiplicity question with a clear tractability route—not that either named result already solves the continuous version.