d4-conf-aaai-2023-1971

There is no numbered hardness result in the paper itself, so the strongest anchors available are its algorithmic results. I would lead with Theorem 3, proved here, and use Theorem 1, also proved here, as the broader companion.

My scenario is a large public allocation of standardized, indivisible aid units to households. A household’s type includes its utility for every aid-unit category, its valuation function, and—when relevant—its priority weight. Think of many households in a relatively small number \(\tau\) of eligibility or needs categories, and many aid units in a relatively small number \(r\) of categories. Both population and supplies grow together: with population normalized to mass \(1\), category \(g\) has supply \(q_g\) per capita. This is a regime with \(n\gg\tau\), not a claim that every allocation problem has a high-multiplicity regime.

The mirror keeps each household’s bundle integral. Let \(\mu_a\) be the mass of household type \(a\), and let \(u_{ag}\) be the utility a type-\(a\) household gets from one unit of category \(g\). Write \(k\in\mathbb Z_{\ge0}^r\) for an integral bundle and \(x_{a,k}\) for the mass of type \(a\) receiving that bundle. A feasible allocation satisfies
\[ \sum_k x_{a,k}=\mu_a,\qquad \sum_{a,k} k_gx_{a,k}\le q_g\quad\text{for every }g. \]
Here the fractions \(x_{a,k}\) describe how much of a type receives each bundle; they do not give any household a fractional bundle. The discrete analogue has \(N\mu_a\) households and about \(Nq_g\) copies of category \(g\).

Theorem 3 states that, for Asymmetric Nash Welfare Maximization with smooth additive valuations, there is an algorithm running in \(O(nm^2/(\epsilon\omega))\) time with approximation \(O(e^\epsilon/(\omega\ln(1+1/\omega)))\), for any smoothing parameter \(\omega\in(0,1]\). In particular, fixed \(\omega\) gives a constant approximation. The theorem is proved here.

The continuous problem I would hand to a prover is Smooth Type-Mass Nash Welfare. Its input is the type masses \(\mu_a\), per-capita supplies \(q_g\), rational utilities normalized so \(\max_g u_{ag}=1\), positive type weights \(w_a\), and \(\omega\in(0,1]\). For a feasible bundle distribution \(x\), define \(U_a(k)=\sum_g u_{ag}k_g\), \(W=\sum_a\mu_aw_a\), and
\[ F_\omega(x)= \exp\!\left( \frac{1}{W}\sum_{a,k}x_{a,k}w_a\ln(U_a(k)+\omega) \right). \]
The task is to output a feasible \(x\) whose value is within \(O(e^\epsilon/(\omega\ln(1+1/\omega)))\) of the optimum, in time polynomial in the number of types, item categories, input bit length, \(1/\epsilon\), and \(1/\omega\). The smoothing offset is part of the source problem; the continuization is of the household population. I expect this to be Class A for fixed \(\omega\): the theorem already gives a price-based algorithm for the finite-agent problem, and repeated types offer a natural way to compress it. Further questions are whether the approximation remains uniform as \(\omega\) shrinks, and what complexity boundary appears in the unsmoothed case.

Theorem 1 is the broader companion anchor. It says that for an ICA instance with differentiable valuations \(v_i:\mathbb R_+\to\mathbb R_+\), if \(u_i^{\max}=\sum_j u_{ij}\) and \(\rho^{\max}=\max_i(v_i'(0)u_i^{\max}/v_i(u_i^{\max}))\), there is an algorithm with approximation \((1+\epsilon)\max_i\mu_i\) and running time \(O(mn\ln(\rho^{\max}/\epsilon)/\epsilon)\). The result is proved here. The \(\mu_i\) are the paper’s local multiplicative curvature parameters, measuring the worst multiplicative gap between the valuation and the lower-bounding secant for a single item’s utility width.

Its mirror is Curvature-Bounded Type-Mass Welfare: use the same type masses, per-capita supplies, and integral bundles above, but give each type a differentiable, monotone concave valuation \(v_a\). Maximize
\[ V(x)=\sum_{a,k}x_{a,k}v_a(U_a(k)). \]
For a copy of category \(g\), define the secant slope
\[ \sigma_a(z,u_{ag})= \frac{v_a(z+u_{ag})-v_a(z)}{u_{ag}}, \]
and use the paper’s local-curvature expression
\[ \frac{v_a(z+z^*)}{v_a(z)+z^*\sigma_a(z,u_{ag})}, \qquad 0<z^*<u_{ag}, \]
taking its supremum over types, categories, and relevant base utilities \(z\). The question is whether one can return a feasible distribution with welfare at least \(\mathrm{OPT}/((1+\epsilon)\max_a\bar\mu_a)\) in time polynomial in the support sizes and input length, assuming finite curvature and polynomial-time value and derivative access. My prior is also Class A, following the theorem’s curvature-based primal-dual approach; the central further question is whether its pricing step remains tractable once it ranges over integral bundles rather than individual items.

These mirrors cover Theorems 1 and 3, not the whole paper. They are plausible continuizations because the unit of identity is still a household with the same utilities, valuation, and weight, and each household still receives an integral bundle. What changes is that the population is represented by type masses and goods by per-capita supplies. I am not claiming that the paper’s algorithms already solve these versions.

The soft spot is the bundle pricing problem. The paper’s algorithms reason about individual items and agents; the type-mass formulation must account for households of the same type ending up with different bundles. The variables \(x_{a,k}\) preserve that distinction, but leave a potentially large set of bundle choices to optimize over. Exact categories also require genuinely repeated utility profiles; if nearly every household or item is unique, the support compression disappears. That is a serious technical and modeling limitation, but it does not make the population regime artificial: large aid programs can have many recipients per needs category and many copies of each standardized resource.