| paper | d4-conf-atal-2014-0264 |
| 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}\text{-complete}\), already for \(\tau=1\) and \(q_\ell=\tfrac12\) for every category. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given finitely many complete additive valuation types \(\mathcal T\), rational masses \(\mu_t\ge 0\) summing to \(1\), nonnegative values \(w_{t\ell}\), and rational per-capita supplies \(q_\ell\in[0,1]\), does there exist a mass assignment \(x_{t,S}\ge 0\) to integral bundles \(S\subseteq[m]\) such that \(\sum_S x_{t,S}=\mu_t\) for each \(t\), \(\sum_{t,S:\ell\in S}x_{t,S}=q_\ell\) for each category \(\ell\), and every bundle assigned positive mass satisfies \(\sum_{\ell\in S}w_{t\ell}\ge\sum_{\ell=1}^m q_\ell w_{t\ell}\)?
A society has finitely many valuation types with masses \(\mu_t\); category \(\ell\) has \(Nq_\ell\) indivisible copies in a population of size \(N\), with each person receiving at most one copy of that category. The decision variables \(x_{t,S}\) assign fractional mass of each type to integral bundles, while requiring every assigned bundle to meet that type’s PFS threshold. The question is whether a complete allocation meeting all per-capita supplies exists.
The mirror covers Proposition 3’s additive PFS-existence result. It leaves the other fairness criteria, their associated results, and the \(k\)-additive results outside its scope.
The strongest mirror is Mass-PFS-Exist, anchored on Proposition 3: “[PFS-Exist] is NP-complete, \(\forall n\ge2\).” The paper proves this result here, describing its proof as similar to Proposition 1’s Partition reduction. In full, [PFS-Exist] asks whether an additive fair-division instance with \(n\) agents and indivisible goods has an admissible allocation in which every agent \(i\) receives utility at least their proportional fair share, \(u_i^{\mathrm{PFS}}=\frac{1}{n}\sum_{\ell\in O}w(i,\ell)\). This is the right anchor because it is a hardness result about the existence of a fair allocation.
Here is the continuous problem. There are \(m\) recurring resource categories and a finite support \(\mathcal T\) of complete additive valuation types. Type \(t\) has mass \(\mu_t>0\), with \(\sum_t\mu_t=1\), and values category \(\ell\) at \(w_{t\ell}\). Category \(\ell\) has per-capita supply \(q_\ell\in[0,1]\): in a population of \(N\) people, there are \(Nq_\ell\) indivisible copies, and each person may receive at most one copy of that category. Take \(N\) large enough to clear the rational denominators in the masses and supplies. This fits, for example, a large course allocation with many students, a small number \(\tau=|\mathcal T|\) of recurring preference profiles, and seats per course scaled with enrollment.
Name the decision problem Mass-PFS-Exist. Its instance is \((\mathcal T,\mu,w,q)\). A solution is a finite-support assignment \(x_{t,S}\ge0\), where \(x_{t,S}\) is the mass of type-\(t\) people receiving the integral bundle \(S\subseteq[m]\). It must allocate every type and use every category’s supply:
\[
\sum_{S\subseteq[m]}x_{t,S}=\mu_t,\qquad
\sum_{t\in\mathcal T}\sum_{S:\ell\in S}x_{t,S}=q_\ell.
\]
Every bundle receiving positive mass must satisfy that type’s PFS guarantee:
\[
x_{t,S}>0\ \Longrightarrow\
\sum_{\ell\in S}w_{t\ell}\ \ge\
\sum_{\ell=1}^{m}q_\ell w_{t\ell}.
\]
The right-hand side is exactly the paper’s proportional fair share after scaling the goods supply with the population: total value of all goods to a person’s type, divided by population size. People still receive whole, indivisible bundles; it is the mass of people assigned to each bundle that can be fractional.
This mirror has a clean hardness argument. Set \(\tau=1\) and \(q_\ell=\tfrac12\) for every category. The population’s average utility is then exactly \(\tfrac12\sum_\ell w_\ell\), the PFS threshold. If every assigned bundle must meet that threshold, every positive-mass bundle must attain it exactly. So any such bundle gives a subset of value half the total. Conversely, a Partition witness \(S\) yields a feasible allocation: assign mass \(\tfrac12\) to \(S\) and mass \(\tfrac12\) to its complement. Thus this restricted continuous problem is NP-hard by the same Partition structure underlying Proposition 3. I expect hardness to transfer: the reduction’s combinatorics live in the item values and catalogue size \(m\), not in population multiplicity. The mirror therefore remains hard even with one voter—or, here, valuation—type.
The case for plausibility is that this keeps the paper’s PFS question and its individual guarantee intact. It does not judge only a type’s average utility: every person receiving positive mass must receive an acceptable integral bundle. The co-modification is the supply regime—repeated resource categories with per-capita quantities—needed to make a large population meaningful. This covers Proposition 3’s additive PFS-existence result; it does not claim a mirror for the other criteria or the \(k\)-additive result.
The weakest point is that recurring categories with a one-copy-per-person cap are more specific than the paper’s model of a finite set of globally unique objects. That regime is natural for courses or recurring allocation slots, but an author might want a broader repeated-goods model. The next questions are whether Mass-PFS-Exist is NP-complete in its full form, how its complexity depends on \(\tau\), and which other discrete hardness results survive when the population is scaled but bundle indivisibility remains.
The only named anchor in the proponent’s case is Proposition 3, the NP-completeness of \([{\rm PFS\text{-}Exist}]\). I can’t find a solid objection that defeats its continuous mirror. With \(Nq_\ell\) copies of category \(\ell\) among \(N\) people, the paper’s PFS threshold becomes \(\sum_\ell q_\ell w_{t\ell}\). The proposed model keeps each person’s bundle integral and makes only the assignment mass fractional. Repeated course seats are a plausible setting, and agents sharing a complete valuation type fit the high-multiplicity premise.
The Partition reduction also checks out. For one type and \(q_\ell=\tfrac12\), the average utility of assigned bundles is exactly half the total value. If every positively assigned bundle must meet that threshold, each must attain it exactly. A half-value subset gives a feasible assignment by splitting mass equally between it and its complement; any feasible assignment contains such a subset. The hardness already present at one type suggests this is Class B, with combinatorics in the goods and their values. Under the programme’s criteria, that is a useful boundary result, not a reason to discard the question.
My best negative point is about likely research yield: this mirror may mainly carry a familiar discrete hardness argument into a repeated-goods model, rather than expose a new tractable use for continuous optimization. But the paper’s globally unique goods do require a supply co-modification for a growing population, and the programme explicitly allows that. Since the mirror remains a sensible population-level computational problem and its hard answer would still map the boundary, I can’t make the requested universal case that no worthwhile mirror exists.
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.