| paper | d4-conf-aaai-2026-0853 |
| 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: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(m\) goods and two finite-support rational distributions \(\mu,\nu\) over \(\Delta_m=\{u\in\mathbb{Q}_{\ge 0}^m:\sum_{j=1}^m u_j=1\}\), with their supports and masses listed explicitly, and a rational threshold \(d\), decide whether there exist a good permutation \(\pi\in S_m\) and a coupling \(\lambda\) of \(\mu,\nu\) such that \(\sum_{u,v}\lambda_{uv}\lVert u-\pi(v)\rVert_1\le d\).
Each type is a normalized additive valuation vector over the same \(m\) indivisible goods, and each society is a finite-support distribution of rational mass over types. The objective minimizes total matched mass-weighted \(\ell_1\) valuation difference over a coupling of the two societies and a common permutation of the goods; study complexity in \(m\), total support size \(\tau\), and input bit length \(L\).
The mirror covers Theorem 1’s hardness for valuation distance; it does not cover the paper’s other distance-computation results, its instance maps and experiments, or its singular-value characterizations.
I would anchor the case on Theorem 1 (Appendix C.2), proved in this paper. It says that, given two allocation instances with the same numbers of agents and goods and a threshold \(d\), deciding whether their valuation distance is at most \(d\) is NP-hard. The valuation distance minimizes the total entrywise \(\ell_1\) difference between their utility matrices over a permutation of the agents and a permutation of the goods. The paper proves this by reducing from the previously established NP-hard \(d_{\text{Spear}}\)-Isomorphic Distance problem, scaling ordinal rankings into normalized utility vectors.
Here is a continuous-population version of that exact metric. Fix \(m\) indivisible goods and let \(\Delta_m=\{u\in\mathbb{Q}_{\ge 0}^m:\sum_j u_j=1\}\). A type is a complete additive valuation vector \(u\in\Delta_m\); a society is a finite-support distribution \(\mu\) over such types, with rational masses summing to one. Given two societies \(\mu,\nu\) over the same goods and a rational threshold \(d\), define their Continuous Valuation Distance as \(D(\mu,\nu)=\min_{\pi\in S_m}\min_{\lambda\in\Gamma(\mu,\nu)}\sum_{u,v}\lambda_{uv}\lVert u-\pi(v)\rVert_1\). Here \(\pi\) relabels the goods, and \(\lambda\) is a coupling: it matches mass of type \(u\) in \(\mu\) to mass of type \(v\) in \(\nu\), with the prescribed marginals. The decision problem asks whether \(D(\mu,\nu)\le d\); a yes answer can be witnessed by a good permutation and a coupling of cost at most \(d\). The instance is given by its two support lists, rational masses and utility vectors, and the threshold; natural complexity parameters are \(m\), total support size \(\tau\), and bit length \(L\).
This is a direct population mirror of Theorem 1. For a discrete matrix \(U\) with \(n\) agent rows \(u_i\), form its empirical society \(\mu_U=\frac1n\sum_i\delta_{u_i}\). Then \(D(\mu_U,\mu_{U'})=\frac1n d_{\mathrm{val}}(U,U')\). To see why, expand repeated types into their individual agents: with equal agent masses, the optimal transport problem has an optimal integral assignment, so its cost is exactly the best agent permutation’s cost divided by \(n\). Thus an instance of Theorem 1 maps to the continuous problem by replacing threshold \(d\) with \(d/n\). The unrestricted continuous decision problem is therefore NP-hard: hardness transfers. This is an exact embedding, not a claim based on an approximation or on the paper’s demand-distance proxy.
A plausible high-multiplicity regime is a large fair-division platform comparing two cohorts’ valuation profiles over the same large inventory of indivisible goods. The paper assumes \(m\ge n\), so this would be a large inventory as well as a large participant cohort. If users value goods through standardized menus, categories, or reusable valuation templates, many agents can share the same complete vector, giving \(n\) far larger than \(\tau\). Each mass then means a fraction of the cohort with that valuation. Comparing cohorts up to agent and good relabeling is precisely what the paper’s valuation distance is intended to do; the continuous version simply lets matching agents’ mass split across types. The authors can recognize this as their metric applied to a population distribution. The utility model and the goods remain unchanged; the population becomes the continuous object.
The scope is deliberately narrow: it mirrors Theorem 1’s exact valuation-distance computation. It does not claim that the paper’s map, allocation-feature experiments, or singular-value characterizations have thereby become continuous-population results. Nor is this a claim that the paper’s own small datasets demonstrate a high-multiplicity regime.
That last point is the weakest part of the case. Theorem 1 establishes hardness when support may grow with the number of agents; it does not show that hardness persists when \(\tau\ll n\), or for fixed \(\tau\). So the continuous problem is both a sensible analogue and NP-hard in its unrestricted form, but the potentially distinctive high-multiplicity complexity landscape remains open. The natural next questions are whether the problem is tractable or hard for bounded support, what dependence on \(m,\tau,L\) is possible, and whether the paper’s tractable demand-distance computation yields a useful approximation for this population metric.
The strongest negative case is that Theorem 1 concerns a distance used to compare instances, not an allocation decision. The paper’s experiments are also mostly tiny, and its hard instances need not have a small support of valuation types. In ordinary elicitation, exact utility vectors over many goods may be nearly all distinct; grouping merely similar vectors would change the metric and could change a threshold decision. So the paper does not establish that its continuous mirror yields a useful complexity landscape in a realistic high-multiplicity regime.
But that objection does not defeat the mirror. The paper’s distance is itself a computational problem, and its invariances carry over directly: rows are anonymous, goods may be relabeled, and a cohort can be represented by a distribution over complete valuation vectors. For empirical societies \(\mu_U=\frac1n\sum_i\delta_{u_i}\), the proposed transport distance equals the paper’s valuation distance divided by \(n\): with equal atom masses, an optimal coupling can be chosen as a permutation assignment. Thus Theorem 1 transfers to the continuous problem. A recurring platform cohort whose users choose from standardized valuation templates gives a plausible high-multiplicity setting; the paper’s own datasets need not demonstrate it.
The unresolved point is whether the problem has an interesting tractability result when the support size \(\tau\) is moderate. The hardness reduction does not answer that, and the paper supplies no such regime. That weakens the case’s immediate payoff, but under the programme’s standard it is not a reason to reject a sensible computational question. I cannot honestly defeat this anchor: the negative case is weak here.
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.