d4-conf-aaai-2026-3180

My lead is the mass version of CCMU, anchored on Theorem 2.4, proved in this paper by a reduction from Independent Set. The theorem says that CCMU is NP-hard when groups have a non-laminar structure, and that it cannot be approximated to any positive multiplicative factor. The reduction makes one item for each graph vertex, one group for each graph edge, and two platforms. Utility \(1\) goes to platform \(a\), utility \(0\) to \(b\), and the utility threshold is the requested independent-set size. Group costs on \(a\) penalize assigning both endpoints of an edge there; platform costs encode the threshold. Thus a zero-cost matching meeting the utility threshold exists exactly when the graph has an independent set of the requested size.

Here is the continuous problem I would hand to a prover. The instance has a finite platform set \(P\); a support \(T\) of \(\tau\) item types, each with rational mass \(\mu_t>0\) and \(\sum_{t\in T}\mu_t=1\); and a finite family of possibly overlapping groups \(\mathcal G_1,\ldots,\mathcal G_q\). Each type \(t\) specifies its allowed platforms \(A_t\subseteq P\), its utility \(u_{tp}\) for every \(p\in A_t\), and its group-membership set \(J_t\subseteq[q]\). The instance also gives a rational utility threshold \(\ell\) and rational convex piecewise-linear cost functions \(\Phi_p,\Psi_{pj}:[0,1]\to\mathbb Q\). Choose masses \(y_{tp}\geq 0\) to assign, subject to \(\sum_{p\in A_t}y_{tp}\leq\mu_t\) for every type and \(\sum_{t,p}u_{tp}y_{tp}\geq\ell\). Write \(\sigma_p=\sum_t y_{tp}\) and \(\nu_{pj}=\sum_{t:j\in J_t}y_{tp}\). The task is to find a feasible assignment minimizing \(\sum_{p\in P}\bigl(\Phi_p(\sigma_p)+\sum_{j=1}^q\Psi_{pj}(\nu_{pj})\bigr)\), or report infeasibility. Each infinitesimal person is assigned to at most one platform; \(y_{tp}\) is the mass of type \(t\) assigned there, not a fractional bundle given to an individual.

This is a plausible high-multiplicity regime for a large hiring or school-placement cohort: millions of applicants but a much smaller support of recurring qualification, platform-eligibility, utility, and demographic profiles. Those details belong in the type because they affect the assignment problem. Demographic groups can overlap, as in the paper’s arbitrary-group case, while platforms remain finite. For an \(N\)-person discrete instance, set \(\mu_t=n_t/N\), scale the utility threshold to \(\ell/N\), and obtain mass cost curves by linearly interpolating the discrete convex costs at integer loads and evaluating them at \(N\sigma_p\) and \(N\nu_{pj}\). Then every integral assignment in the finite instance has the same cost in the mass model. This makes explicit the scaling needed to compare counts with population fractions.

I expect this mirror to be tractable, Class A. With the stated cost representation, each convex piecewise-linear cost is the maximum of finitely many affine functions. Minimizing the objective over the linear assignment and utility constraints therefore reduces to a linear program of size polynomial in \(m\), \(\tau\), \(q\), the number of allowed type-platform pairs, the cost-function descriptions, and the input bit length. Overlap among groups changes which type masses contribute to each \(\nu_{pj}\); it does not make the feasible region nonconvex. So Theorem 2.4’s hardness is exactly the kind of integrality hardness that may disappear in the continuous population model. This is a proposed mirror result, not a claim that Theorem 2.4 itself says anything about the continuous problem.

The authors should recognize it as their problem: it keeps their one-platform-per-item assignment, platform-specific utilities, utility threshold, and both platform and group costs. It changes the population granularity while preserving those ingredients. The mirror covers the underlying CCMU problem with arbitrary overlapping groups, and specifically asks what becomes of Theorem 2.4; it does not purport to mirror every result or experiment in the paper.

The follow-up questions are whether the mass optimum can be rounded while preserving the utility threshold, how the integrality gap behaves as type multiplicities grow, and which structural conditions beyond disjoint or laminar groups yield a small gap. Those questions provide the bridge back to the paper’s discrete setting.

The weakest point is the regime behind the hardness anchor. The reduction encodes graph incidence through edge-groups on vertex-items, so its type support generally grows with the graph; it does not show that the hard instances have many agents but few exact types. The mirror is credible because repeated, standardized assignment profiles are plausible in large cohorts, not because Theorem 2.4 establishes high multiplicity. The continuum also deliberately permits a type’s mass to split across platforms; that is the population-level relaxation whose algorithmic consequences the mirror is asking about.