| paper | d4-conf-atal-2017-0331 |
| 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: polynomial-time solvable · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given finitely many score types \(T\), rational scores \(a_t\ge 0\), rational masses \(\mu_t\ge 0\) summing to one, and trio templates \(g\) with repetition, maximize \(\rho\) over \(q_g\ge 0\) subject to \(\sum_g c_t(g)q_g=3\mu_t\) for every type \(t\), and require every template with \(q_g>0\) to satisfy \(\bigl(\sum_{t\in g}a_t/3\bigr)^2\ge\rho\).
Types are score levels, and each unit of mass represents learners with the same score. The variable \(q_g\) gives the number of trios of composition \(g\) per unit population; the mass constraints assign the whole society, while the objective maximizes the least trio happiness.
The mirror is anchored to Theorem 8’s score-based MoA hardness result for \(k=3\). It leaves the general-compatibility results, other objectives, and the PAC learning result aside.
The strongest anchor is Theorem 8, proved in this paper. It states that computing an optimal partition for the minimum-of-averages objective (MoA) is NP-hard when pairwise compatibility has the score structure \(W_{ij}=s_i s_j\). Its reduction from strongly NP-hard 3-Partition already uses groups of size \(k=3\). Here MoA means maximizing the happiness of the worst group: \(\max_{\Pi}\min_i H(S_i\mid W)\), where \(H(S\mid W)=|S|^{-2}\sum_{u,v\in S}W_{uv}\). Under the score structure, a group’s happiness is \(\bigl(\sum_{u\in S}s_u/|S|\bigr)^2\).
My lead mirror is Continuous Score-MoA-3. An instance gives a finite set \(T\) of score types, a rational score \(a_t\ge 0\) and rational population mass \(\mu_t\) for each type, with \(\sum_t\mu_t=1\), plus a rational threshold \(\rho\). A type is just its score: in this model, that fully determines its compatibility with every other type. A group template is an unordered triple \(g=\{t_1,t_2,t_3\}\), with repetitions allowed. The question is whether there is a distribution \(q\) over group templates such that
\[
\sum_g c_t(g)q_g=3\mu_t\quad\text{for every }t,
\qquad
q_g>0\ \Longrightarrow\
\frac{(a_{t_1}+a_{t_2}+a_{t_3})^2}{9}\ge\rho,
\]
where \(c_t(g)\) counts how many slots of the triple use type \(t\). The solution is the distribution \(q\): it specifies the share of trios of each composition. The constraints ensure that the society’s type masses fill the trio slots exactly. Maximizing \(\rho\) gives the continuous MoA optimum.
A plausible regime is a large recurring online study or training programme that assigns learners to trios. Suppose the score measures peer influence or capacity to help, and the model treats that score as the complete description relevant to group happiness. Many learners may share each standardized score level, so the population size can be much larger than the support size \(\tau=|T|\). Each actual group remains a trio; \(q\) describes what fraction of trios should have each type composition. The mirror fits the paper’s study-group motivation and its score-based MoA problem.
I expect Class A for this mirror. For fixed group size three, there are only \(O(\tau^3)\) templates. At a given \(\rho\), feasibility is a linear program over the templates whose happiness meets the threshold. The optimum is one of the \(O(\tau^3)\) template happiness values, so testing those thresholds yields an exact polynomial-time algorithm in \(\tau\) and the input bit length. The discrete hardness in Theorem 8 is therefore a candidate for dissolving under fractional mass allocation. A discrete partition maps to a feasible \(q\); conversely, a rational \(q\) can be realized by a sufficiently large replication of the same type proportions. That does not promise the same optimum for the original finite cohort, but it gives a precise high-multiplicity interpretation.
The mirror covers the paper’s score-based MoA hardness result, not its general-compatibility hardness, other objectives, or PAC learning result. It also suggests questions about rounding \(q\) for a fixed finite cohort, and about what happens when group size \(k\) is part of the input and the number of group templates grows.
The weakest point is that the paper studies partitions of individually named users, while this mirror lets a type’s mass be split among different trio templates. That is a real change for a single finite cohort. It is credible for a large recurring programme with many users at each score level, where allocating proportions of a cohort is meaningful; it is less persuasive for a small one-off team assignment.
The strongest case against is that Theorem 8’s hardness does not establish a high-multiplicity regime. Its 3-Partition reduction treats scores as item values; it does not show that hard instances contain many users of the same score. In realistic settings, influence or capacity scores may be individually measured, so the support can grow with the cohort. Then the proposed LP still solves the continuous problem, but its advantage over the cohort’s actual indivisible assignment is less clear.
That objection does not defeat the stronger mirror. In a recurring programme with standardized score levels, equal-score users are interchangeable under \(W_{ij}=s_i s_j\), and the type is a complete description for this objective. The distribution \(q\) over trio compositions is then a direct population-level assignment. Since rational solutions can be implemented exactly by replicating the cohort sufficiently many times, the fractional groups are not merely an artifact of an isolated finite cohort. The LP has \(O(\tau^3)\) trio templates and gives a precise polynomial-time mirror of the paper’s NP-hard result. Its simplicity is not a decisive objection: showing that multiplicity dissolves this hardness is squarely within the programme’s purpose.
So the honest case against is limited to practical fit: this mirror is most compelling when score levels repeat and assignments recur. I cannot defend the universal claim that no worthwhile mirror exists. Theorem 8’s anchor survives.
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.