| paper | d4-conf-ijcai-2020-0448 |
| 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→P discrete result → its continuous mirror
Answer: Exactly solvable with \(\operatorname{poly}(m,L)\) exact demand queries and bit operations, returning at most \(m+1\) supported bundles; hence admits a PTAS. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
Given \(m\) goods categories, rational per-capita supplies \(b_j\in[0,1]\), and one agent type with a common normalized, monotone, subadditive valuation \(v:2^{[m]}\to\mathbb{Q}_+\) accessible by demand queries, find a finite-support distribution \(x_S\ge0\) over integral bundles \(S\subseteq[m]\) maximizing \(\sum_S x_Sv(S)\), subject to \(\sum_Sx_S=1\) and \(\sum_{S\ni j}x_S=b_j\) for every category \(j\).
A population of mass one has a single complete agent type with valuation \(v\); each agent receives an integral bundle, while \(x_S\) is the mass assigned bundle \(S\). Category supplies scale with population, and the objective is average social welfare. The configuration LP has bundle variables \(x_S\); its pricing problem is \(\max_{S\subseteq[m]}(v(S)-\sum_{j\in S}y_j)\), the paper’s demand query, so the expected outcome is Class A.
Theorem 2 uses individually distinct goods, while the mirror assumes repeatable categories with a common valuation over category bundles; the paper does not itself specify that inventory convention.
fatal: False
The mirror covers Theorem 2’s \(p=1\) average-social-welfare APX-hardness; it leaves the \(p<1\) hardness cases, Theorem 1’s simultaneous approximation algorithm, and the supporting structural results unclaimed.
My lead is a narrow \(p=1\) mirror: Continuous Identical-Valuation Social-Welfare Allocation.
The anchor is Theorem 2, proved in the paper’s Appendix B using a reduction from cited Gap-3DM hardness. It states that, for every \(p\in(-\infty,1]\), maximizing \(p\)-mean welfare is APX-hard when agents have an identical subadditive valuation, even with demand-oracle access: for some constant \(c>1\), it is NP-hard to approximate the optimum within factor \(c\). I rely on its \(p=1\) case, where the objective is average social welfare.
Here is the continuous problem. There is a population of mass \(1\), all of one complete agent type with the same normalized, monotone, subadditive valuation \(v:2^{[m]}\to\mathbb{Q}_{+}\), given by a demand oracle. There are \(m\) goods categories, with rational per-capita supplies \(b_j\in[0,1]\). A solution assigns mass \(x_S\geq0\) to each integral bundle \(S\subseteq[m]\), subject to
\[
\sum_{S\subseteq[m]}x_S=1,
\qquad
\sum_{S\ni j}x_S=b_j\quad\text{for each }j.
\]
Each agent receives a whole bundle; \(x_S\) is the fraction of the population receiving \(S\). The question is to maximize
\[
\sum_{S\subseteq[m]}x_Sv(S),
\]
and return a finite list of bundles and their assigned masses. This is the continuous form of the paper’s underlying social-welfare allocation problem, rather than a question about an encoding.
The regime is a large, standardized cohort—say, recipients of a public benefits package—with a common value schedule in which goods can substitute for one another. The paper itself points to common monetary valuations with substitutes as a stylized setting. The number of agents can be very large while the number of agent types is \(\tau=1\). Supply scales with cohort size: for example, the paper’s \(n\)-agent instance has \(b_j=1/n\) for each good, and larger cohorts can have proportionally more copies of each category. This makes the high-multiplicity interpretation explicit.
I expect this mirror to be tractable (Class A). Its configuration LP has exponentially many bundle variables, but its dual has only \(m+1\) variables. Separating a dual constraint amounts to finding
\[
\max_{S\subseteq[m]}\left(v(S)-\sum_{j\in S}y_j\right),
\]
which is exactly a demand query at prices \(y_j\). Thus the demand-oracle model in the anchor supplies the pricing operation needed for polynomial-time LP optimization. A basic optimal solution can be reported with at most \(m+1\) positive-mass bundles. The discrete APX-hardness therefore need not survive this population relaxation: the mass distribution can split continuously among integral bundles, and the matching obstruction in the paper’s reduction may be lost when bundle assignments no longer need integer counts.
The mirror covers the \(p=1\) case of Theorem 2. It does not claim that the paper’s hardness transfers for other \(p\). Natural further questions are whether efficient pricing or approximation is possible for \(p\in(0,1)\), for Nash welfare \(p=0\), and for \(p<0\), where the relevant transformed bundle values differ.
The weakest point is the supply scaling: the paper starts with individually distinct goods, while this mirror gives each category a stable per-capita supply as the population grows. The model remains recognizable as the same allocation problem because each recipient still gets an indivisible bundle and the valuation remains the paper’s common subadditive valuation; the co-modification is to the population-scale inventory.
The strongest negative case is about fidelity to the anchor. Theorem 2 is a named computational result, and its \(p=1\) case is exactly the APX-hardness of maximizing average social welfare under identical subadditive valuations. So there is a result to mirror.
But the paper’s instance has \(m\) goods total, each allocated once. If \(m\) stays fixed while the population grows to \(n\), the corresponding per-capita supply of each good is \(1/n\). Then
\[
\frac{1}{n}\sum_{i=1}^n v(A_i)
\leq \frac{1}{n}\sum_{g=1}^m v(\{g\}),
\]
so average welfare vanishes. That literal limit is a poor mirror.
The stronger version fixes this by scaling inventory with the population: give each category a stable per-capita supply and extend the common valuation to the resulting copies. That is a real modeling choice. The paper’s goods are distinct objects, and its hardness construction uses their identities; it does not specify how values behave when goods are replicated. A mirror therefore needs authors to accept a goods-and-valuation extension, not just replace \(n\) named agents with mass. This is the best reason to doubt that the proposed formulation is *the* faithful mirror of Theorem 2.
It does not defeat the better mirror, though. Repeated units of a category being substitutes is plausible in the paper’s own monetary-values setting. Each person can still receive an integral bundle, while the mass of people receiving each bundle is continuous. With per-capita capacities \(b_j\), the resulting allocation LP has bundle variables \(x_S\), and its pricing problem is the paper’s demand query, \(\max_S\bigl(v(S)-\sum_{j\in S}y_j\bigr)\). The single-type population is still a legitimate high-multiplicity regime; its type distribution happens to have support size one. The continuous assignment records how that population is divided among bundles, rather than making goods divisible for each individual.
The LP may make the continuous answer straightforward, but that does not make the question out of scope or already done in the sense that rules out a mirror. The only substantial objection is that scaling the goods requires a valuation-extension convention. Since a plausible convention yields a well-posed population mirror that the authors could recognize, I cannot honestly defeat this anchor. The case against a worthwhile continuous mirror 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.