| paper | d4-conf-sagt-2021-0006 |
| 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: \(\mathsf{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 7
Given a finite skill set \(S\), supported binary expertise types \(T\subseteq\{0,1\}^{S}\) with rational masses \(\mu_t>0\) summing to \(1\), and team capacity \(\kappa\), compute a rational allocation \(y_q\ge 0\) over integral team compositions \(q\in\mathbb{Z}_{\ge 0}^{T}\) with \(1\le\lVert q\rVert_1\le\kappa\), satisfying \(\sum_q q_t y_q=\mu_t\) for every type \(t\). Each team composition receives utility \(U(q)=\sum_{s\in S}\max_{t:q_t>0}t(s)\). The output must be Pareto optimal: there is no feasible allocation whose utility distribution for each type can be coupled with the output’s so that every unit of mass gets at least its previous utility and a positive mass gets strictly more.
A society is a rational distribution \(\mu\) over complete expertise profiles. Teams retain integral compositions \(q\), while rational frequencies \(y_q\) describe how often each team forms. The task is to output any feasible allocation maximal under typewise Pareto dominance; there is no scalar optimization objective.
The hardness construction grows with the number of skills and distinct expertise profiles, so it does not establish whether instances with small support admit an efficient algorithm.
fatal: False
The mirror covers Theorem 7(iii), the hardness of finding a Pareto-optimal partition; it leaves the theorem’s other claims and the paper’s stability and welfare results aside.
My lead is Continuous-PO-HEG. The strongest case is for a genuine high-multiplicity mirror of the paper’s Pareto-optimal partition problem; I expect its hardness to transfer, rather than disappear.
The anchor is Theorem 7, proved in this paper. In \((0,1)\)-HEGs, it says: (i) deciding whether a perfect partition exists is NP-hard; (ii) finding a socially optimal partition is NP-hard; (iii) finding a Pareto-optimal partition is NP-hard; and (iv) verifying whether a partition is Pareto optimal is coNP-complete. The theorem proves these claims by reductions from SET-COVER. I rely on (iii) as the anchor; the other claims are further questions for the mirror. [Theorem 7 in the paper](https://arxiv.org/pdf/2011.01778)
Here is the continuous problem. Let \(S\) be a finite skill set, and let \(T\subseteq\{0,1\}^{S}\) be the supported expertise types, with rational masses \(\mu_t>0\) summing to \(1\). Type \(t\) specifies which skills its members have. A team has at most \(\kappa\) people, as in the paper. Its composition is an integral vector \(q\in\mathbb{Z}_{\ge0}^{T}\) with \(1\le\lVert q\rVert_1\le\kappa\): \(q_t\) is the number of type-\(t\) members on that team. Its joint utility is
\[ U(q)=\sum_{s\in S}\max_{t:q_t>0}t(s). \]
An allocation is a rational, nonnegative frequency \(y_q\) of teams of each composition, normalized per person, satisfying \(\sum_q q_t y_q=\mu_t\) for every type \(t\). Thus team membership stays integral, while the population can be divided fractionally among many teams of each composition.
For precision, let \(F_{t,h}(y)=\sum_{q:U(q)=h}q_t y_q\), the mass of type \(t\) receiving utility \(h\). Say \(y'\) Pareto-dominates \(y\) if, within every type, its utility distribution can be matched to the old one so that no mass receives lower utility, and some positive mass receives higher utility. Continuous-PO-HEG asks: given \(S,T,\mu,\kappa\), output a feasible rational list of team compositions and frequencies that is Pareto optimal under this comparison.
A plausible regime is a large pool assigned to many small project teams: for example, people with standardized skill credentials drawn from a recurring labor or training cohort. People with the same complete skill profile are one type; there may be far more people than distinct profiles, and team capacity remains small. This is the authors’ team-formation question at high multiplicity: aggregate how often each kind of team forms, while each person still receives the same team utility the paper defines. The typewise matching in the Pareto comparison treats agents with identical game-relevant profiles as interchangeable, as the model does.
The hardness case is concrete. In the paper’s SET-COVER reduction, skills represent universe elements, each set becomes a binary expertise profile, and the added universal-expertise agents all share one profile. Give each profile its reduction mass, with the universal profile receiving the mass of all those agents. These are rational proportions. Uniformly replicating the agents preserves those proportions while making the population arbitrarily large relative to the support size. The paper’s construction guarantees a team without a universal member; in the mass model, positive frequency of such teams is still forced by the same capacity count. Such a team reaches utility \(|S|\) only if its set profiles cover all skills. If a perfect allocation exists, every Pareto-optimal allocation must be perfect, since \(|S|\) is the maximum utility. If no cover exists, no allocation can be perfect. So a Continuous-PO-HEG solver would decide the SET-COVER instance by checking whether its output assigns positive mass to any team below utility \(|S|\). I therefore expect hardness to transfer (Class B): the reduction’s combinatorics lie in the skill profiles and team cap, not in how many copies of each profile there are.
The mirror covers Theorem 7(iii), not the paper’s whole collection of results. It also raises natural follow-ups: whether perfect-partition existence and social-welfare optimization remain hard in this mass model, and whether checking Pareto optimality is coNP-complete or changes under fractional team frequencies.
My weakest point is the Pareto comparison. A referee could ask whether typewise rematching is the right continuous analogue of comparing named agents. I think it is: the paper’s utility uses only the coalition’s expertise profile, so two members of one type are indistinguishable for the problem’s purposes. The other limitation is substantive: this is a faithful continuum question, but a negative one. Its value is to test—and likely establish—a boundary where continuization does not dissolve the paper’s hardness.
The strongest case against is a priority argument, not a claim that the mirror is ill-posed. Continuous-PO-HEG is a credible high-multiplicity version of the paper’s problem. People with the same complete expertise profile are interchangeable for the model, teams can retain integral compositions, and the society can record how often each composition occurs. Comparing utility distributions within each type is a defensible continuum version of Pareto dominance.
The proponent’s hardness argument also appears to survive. In the set-cover construction, give each expertise profile its original count as mass, normalized by the total population \(n+x\). Any feasible allocation needs total team frequency at least \(1/\kappa\), since each team has at most \(\kappa\) members. Teams containing a universal-expertise member have total frequency at most \(x/(n+x)\). The construction chooses \(x\) so that \((\kappa-1)x<n\), hence \(x/(n+x)<1/\kappa\). Some positive mass must therefore be in teams without a universal member. Such a team reaches utility \(|S|\) only if its at most \(\kappa\) set profiles cover all skills.
Conversely, given a cover of size at most \(\kappa\), one can pad it to \(\kappa\) set agents and put those agents in a team without a universal member. The remaining \(n-\kappa\) set agents fit alongside the \(x\) universal agents, since \(x(\kappa-1)\ge n-\kappa\). This gives a perfect mass allocation. If one exists, every Pareto-optimal allocation must be perfect: the perfect allocation raises every below-maximum utility without lowering anyone’s. So a solver for the proposed mirror would distinguish whether a cover exists. The reduction’s essential combinatorics survive aggregation.
The reservation is about how much this result would establish about *high multiplicity*. The reduction’s support consists of the set profiles, so its hardness comes from growing numbers of skills and distinct expertise types. Replicating every agent can make each type numerous while leaving the support size unchanged, but that replication does not simplify the reduction. In a practical cohort with a small, standardized set of expertise profiles, this hardness construction may be a poor description of the regime. It shows hardness when support grows; by itself, it says little about the algorithmic value of continuous optimization when support is small.
That reservation could justify giving this mirror lower priority if the programme seeks new continuous techniques or a sharp result for modest support. It does not defeat the mirror: establishing a Class B boundary is explicitly within the programme’s aims, and the proposed allocation is a sensible object to study. I cannot honestly make the universal negative case here; the strongest objection is that the result may be an inexpensive hardness transfer whose practical reach depends on the support regime.
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.