| paper | d4-conf-ecai-2025-0204 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: For both cost rules, the continuous threshold problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
Input finite sets of household types \(A\) and unit types \(J\), rational population masses \(\mu_a\) summing to \(1\), per-capita unit supplies \(q_j\), initial compatible sets \(N_a\), relaxable sets \(D_a\), discomforts \(\rho_{aj}\), and a per-capita budget \(\beta\). Choose advice masses \(z_{a,S}\geq 0\) for bundles \(S\subseteq D_a\), with \(\sum_{S\subseteq D_a}z_{a,S}=\mu_a\), satisfying either \(\sum_{a,S}z_{a,S}|S|\leq\beta\) or \(\sum_{a,S}z_{a,S}\sum_{j\in S}\rho_{aj}\leq\beta\). For every partial-compliance split \(y_{a,S,R}\geq0\), where \(R\subseteq S\) and \(\sum_{R\subseteq S}y_{a,S,R}=z_{a,S}\), form cohorts compatible with \(N_a\cup R\). Require that, in every resulting maximum mass flow, initially protected type masses and every cohort with \(R\neq\varnothing\) are fully matched. Find a feasible advice policy maximizing the maximum-flow value under full compliance.
A nonatomic population distributed over finitely many complete agent types, with per-capita supplies of resource types. Advice bundles and compliance split type mass into cohorts; a bipartite mass flow assigns one indivisible resource to each matched infinitesimal agent. Optimize matched mass subject to the budget and universal participation guarantees.
The mirror covers only Theorem 1’s one-to-one SNH-SB problem, for both size and total-cost bounds; it leaves the other guarantee combinations, many-to-one and one-to-many results, and experiments unmirrored.
I think there is a credible continuous mirror of the paper’s robust facilitation problem. The strongest regime I see is a large public housing placement platform: many thousands of households, matched to standardized unit classes. A household type records the full profile the platform uses—eligibility, acceptable unit classes, and discomfort for relaxing each restriction. A unit type records the features that affect compatibility. This is a high-multiplicity scenario only where the platform’s intake uses a finite set of such profiles, so the number of households \(N\) is much larger than the number \(\tau\) of occupied household types. It would be a mistake to claim this of every housing platform.
My anchor is Theorem 1, proved in this paper; its proof is in Appendix A.1. It says that Algorithm 1, with its specified weight function, solves the one-to-one SNH-SB optimization problem for either aggregate-cost function: given the compatibility graph, relaxable incompatibilities and their discomforts, budget \(\beta\), and either total cost or size, it returns a relaxation set that obeys the budget, gives strong no-harm and strong benefit even under partial compliance, and maximizes the resulting maximum-matching size among such sets. The paper gives running time \(O(\log |Y|\max(|X|,|Y|)^3)\). The theorem is proved here, though its proof uses matching-theoretic facts cited to earlier work. The paper has no named hardness theorem, so I use this algorithmic anchor rather than padding the case with nearby algorithmic variants.
Here is the continuous problem I would hand to a prover. Call it SNH-SB Population Facilitation. The input is finite sets \(A\) of household types and \(J\) of unit types; rational masses \(\mu_a\geq 0\) with \(\sum_{a\in A}\mu_a=1\); rational per-capita supplies \(q_j\geq 0\); and, for each \(a\), its initially compatible unit types \(N_a\subseteq J\), its relaxable types \(D_a\subseteq J\setminus N_a\), and rational discomforts \(\rho_{aj}\) for \(j\in D_a\). It also gives a rational per-capita budget \(\beta\) and chooses either total discomfort or size as the cost measure.
The facilitator chooses masses \(z_{a,S}\geq 0\), one for each \(S\subseteq D_a\), with \(\sum_{S\subseteq D_a}z_{a,S}=\mu_a\). Here \(z_{a,S}\) is the mass of type \(a\) advised to relax exactly the restrictions in \(S\); \(S=\varnothing\) means no advice. The budget is either \(\sum_{a,S}z_{a,S}|S|\leq\beta\) or \(\sum_{a,S}z_{a,S}\sum_{j\in S}\rho_{aj}\leq\beta\). Under full compliance, the objective is to maximize the mass matched.
To state the guarantee precisely, allow any partial-compliance realization: for every advised mass \(z_{a,S}\), split it into masses \(y_{a,S,R}\geq 0\) for \(R\subseteq S\), with \(\sum_{R\subseteq S}y_{a,S,R}=z_{a,S}\). A cohort \((a,S,R)\) then has compatibility set \(N_a\cup R\). An allocation is a fractional flow from these cohorts to unit types, with each cohort’s outgoing flow at most its mass and total flow into unit type \(j\) at most \(q_j\). Flow represents splitting a population into subgroups assigned whole units; it does not give an individual a fractional unit. The baseline-protected types are those whose entire mass is matched in every maximum flow before any advice. A policy is feasible if, for every partial-compliance realization and every maximum flow afterward, all baseline-protected types remain fully matched and every cohort with \(R\neq\varnothing\) is fully matched. The problem is to find a feasible policy \(z\) within budget that maximizes the maximum-flow value under full compliance. Its solution is the advice mass distribution \(z\).
This keeps the paper’s actual question intact: choose which restrictions to ask agents to relax, maximize allocation, and protect both guaranteed participants and those who comply. The continuous object is the population share receiving each recommendation. Grouping households is legitimate only when their modeled compatibility and discomfort are identical. Grouping repeated unit slots and scaling their supplies is the natural capacity adjustment for this large-population regime; it is part of the mirror, not a switch to a different outcome-space question.
I would tentatively expect this mirror to be Class A. For any fixed advice and compliance realization, allocation is a bipartite flow problem, and the participation tests are statements about saturation in every maximum flow. That gives a plausible route through flow structure and continuous optimization. The hard part is finding a compact exact method for choosing advice while enforcing guarantees across all partial-compliance patterns; the bundle space \(S\subseteq D_a\) can be exponential. The prover’s central questions are whether those constraints admit efficient separation, and whether the finite-population and mass versions have a useful two-way dictionary. Theorem 1 itself does not establish that continuous result.
The mirror covers only the one-to-one SNH-SB optimization result. It does not claim that the paper’s experiments or all its guarantee variants have been continuized. My weakest point is that universal guarantees over fractional cohorts might not capture how the original platform treats named agents under every possible compliance pattern. I think the objection is contained if types are complete and the platform is genuinely indifferent among their members: the continuous guarantee protects the whole type mass, which is exactly the mass-level analogue of protecting every identical individual. It fails if the platform uses individual distinctions that the type description leaves out.
The strongest negative case is that Theorem 1’s guarantee is pointwise. In the finite graph, strong no harm protects each named agent in every maximum matching, and strong benefit protects each agent who relaxes a restriction. For a nonatomic population, the closest analogue is that a positive-mass cohort is fully matched. That permits a null set of individuals to be left unmatched without changing the flow or the guarantee. To retain the paper’s literal person-by-person promise, one would have to keep those identities in the type space; with many distinct individuals, the support grows with the population and the high-multiplicity advantage disappears. In settings such as housing, where one exceptional applicant may matter, that is a real change in what the guarantee says.
But this does not defeat the proposed mirror. If applicants fall into a fixed set of genuinely complete, repeated types, then all members of a type are interchangeable in the paper’s model. Full saturation of a type’s mass is a sensible analogue of protecting all its members, and splitting that mass by recommendation and compliance pattern can represent partial compliance. Scaling unit supplies with the population is also a coherent co-modification. The proposed public-housing regime is plausible, and the paper supplies a named computational anchor in Theorem 1.
So the pointwise-versus-mass distinction is the best objection I can make, but it does not rule out the better mirror. It identifies a semantic choice the authors would need to defend: whether the continuous guarantee protects almost all members of a cohort or promises protection to every identifiable person. Under the proponent’s exchangeable-type assumption, the former is meaningful and faithful enough to survive. I can’t honestly claim that this anchor has been defeated or make a strong universal case against a worthwhile mirror.
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.