| paper | d4-conf-aaai-2026-2791 |
| 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: Uniformity and coverage are both \(\mathrm{NP}\text{-hard}\), already for \(\tau=3\) and equal masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a finite set \(A\) of alternatives that are Pareto optimal under three evaluator types \(T\), their rational scores \(u_t(a)\), rational masses \(\mu_t>0\) summing to \(1\), and a slate size \(k\), compute an optimal size-\(k\) slate \(S\subseteq A\). For uniformity, maximize \(\min_{a,b\in S,\ a\ne b}D_\mu(a,b)\); for coverage, minimize \(\max_{a\in A}\min_{s\in S}D_\mu(a,s)\), where \(D_\mu(a,b)=\sum_{t\in T}\mu_t|u_t(a)-u_t(b)|\). Theorem 8 establishes hardness on the subfamily with \(\mu_t=1/3\).
A society of evaluators is a distribution \(\mu\) over three complete evaluation types, each assigning a rational score \(u_t(a)\) to every alternative. Alternatives remain indivisible and the decision is a discrete slate \(S\subseteq A\) of size \(k\); type masses weight the evaluator disagreements through \(D_\mu\).
For cardinal scores, mass weighting can be absorbed into a rescaling of the objective coordinates, so the mirror adds no new geometry; this limits its novelty but does not invalidate the population interpretation.
fatal: False
The mirror covers the hardness results in Theorem 8 and Proposition 12. It leaves the two-objective algorithms, the fixed-\(d\) approval algorithm in Proposition 11, the axiomatic results, and the experiments outside its scope.
The strongest case is that the paper supplies its own bridge: it treats alternatives as candidates and objectives as voters, and says the voter analogy is especially apt when objectives represent human evaluators. The mirror keeps the paper’s central task intact: choose exactly \(k\) alternatives from a finite Pareto front. It makes the evaluator population continuous.
A type \(t\) is a complete evaluation rule over the alternatives: \(u_t(a)\) is the score that type gives alternative \(a\). A rational distribution \(\mu\) over types gives each type’s fraction of the evaluator population; \(\tau\) is the number of types with positive mass. Scores and masses are part of the input, encoded in binary. Assume every alternative is Pareto optimal across the supported types. Define \(D_\mu(a,b)=\sum_t\mu_t|u_t(a)-u_t(b)|\) and \(D^+_\mu(a,b)=\sum_t\mu_t\max\{u_t(a)-u_t(b),0\}\). For a size-\(k\) slate \(S\), uniformity maximizes \(\min_{a,b\in S,\ a\ne b}D_\mu(a,b)\); coverage minimizes \(\max_{a\in A}\min_{s\in S}D_\mu(a,s)\); directed coverage minimizes the same expression using \(D^+_\mu\). The solution is an optimal slate \(S\), not a fractional selection of alternatives.
My lead is Three-Type Continuous Uniformity/Coverage Pareto Pruning. An instance gives a finite Pareto front \(A\), \(k\), three evaluator types with positive rational masses summing to one, and their rational scores for every alternative. It asks for an optimal size-\(k\) slate under either uniformity or coverage. Theorem 8, proved in this paper, states that uniformity and coverage Pareto pruning are NP-hard even for three objectives. Set the three type masses to \(1/3\) and use the paper’s three coordinates as the type scores: each distance is just the paper’s Manhattan distance scaled by \(1/3\), so the optimal slates are unchanged. Thus the mirror inherits the hardness even with only three types. A plausible regime is a large panel of evaluators grouped into three stable evaluation archetypes, with many people in each group. I expect the hardness to transfer: the reduction’s combinatorics lie in choosing among alternatives, and persist when each type represents a population share.
A second, complementary mirror is Approval-Population Pareto Pruning. Here a type is an approval set \(B_t\subseteq A\), and \(\mu_t\) is the fraction of evaluators with that approval set. For alternatives \(a,b\), disagreement distance is \(\sum_t\mu_t\,\mathbf{1}[\,|\{a,b\}\cap B_t|=1\,]\), and directed loss from presenting \(b\) in place of \(a\) is \(\sum_t\mu_t\,\mathbf{1}[a\in B_t,\ b\notin B_t]\). The instance asks for an optimal size-\(k\) slate under uniformity, coverage, or directed coverage using those quantities. Proposition 12, proved in this paper, states that all three problems are NP-hard even when every objective is an approval objective. Map each objective in a paper instance to a type of mass \(1/d\); the resulting distances are the original approval distances scaled by \(1/d\), preserving the optima. This fits a large evaluator body whose members fall into approval-pattern types, with many evaluators per type. I again expect hardness to transfer, through the alternative-selection problem and the growing number of supported types.
These mirrors cover the paper’s computational results in Section 4, not its axiomatic analysis or experiments. The approval version raises a useful boundary question: for fixed \(\tau\), there are at most \(2^\tau\) distinct approval profiles for alternatives, so what exact and parameterized algorithms can exploit that finite pattern space when the type masses are rational? The three-type cardinal result raises the opposite question: which restrictions on scores, \(k\), or geometric structure can help when hardness already holds at \(\tau=3\)? In both cases the continuous model keeps the slate discrete and changes the evaluator population through masses, so it remains the paper’s Pareto-pruning problem.
The weakest point is the interpretation of objectives as a population. In many engineering applications, objectives are physical criteria rather than people, and repeated criteria may be understood as reweighting. The mirror is most convincing for settings where objectives really do represent evaluators: the paper itself makes that connection and studies ordinal and approval objectives partly because those forms are natural for human evaluators. I would expect the authors to recognize this as a continuous population version of their problem in that regime.
The strongest case against is that the proposed population sits uneasily with the paper’s main applications. In engineering, healthcare, and operations research, objectives are usually criteria such as cost, reliability, and performance—not people. Giving one criterion more “mass” would reweight its importance, which is a different modeling choice from saying more people share an evaluation type. The slate is selected for a decision maker; the evaluator population does not itself choose or change the alternatives.
That objection does not defeat the three-type anchor. The paper explicitly motivates its voter analogy by noting that objectives can represent human evaluators. A large panel grouped into three stable evaluation types is plausible, and the mass model preserves the Pareto-pruning task. Theorem 8 then transfers exactly: equal masses scale all Manhattan distances by \(1/3\), leaving optimal slates unchanged. More generally, for cardinal scores, the mass can be absorbed into the coordinates, since
\[
\sum_t \mu_t |u_t(a)-u_t(b)|
=\sum_t |\mu_tu_t(a)-\mu_tu_t(b)|.
\]
That makes the mirror mathematically close to the paper’s existing cardinal problem, but sameness of the answer is not a sound reason to reject a well-posed population question.
The approval anchor is harder to dismiss. Its population can be a large panel grouped by approval pattern, and every cohort can contain many evaluators even when the number of types grows. For rational masses, weighted approval distances can also be represented by repeating each approval type in proportion to its mass. That is a re-encoding of the paper’s approval-objective geometry, but the compressed mass input still expresses a high-multiplicity regime. Proposition 12 transfers to equal-mass types, and the paper’s fixed-objective result already points toward tractability when support is fixed. Neither fact makes the population interpretation incoherent.
So the negative case rests mainly on whether a panel of evaluators is a convincing use of this paper’s model. The paper itself supplies that use case, and I cannot honestly defeat either computational anchor under the programme’s rules. The “criteria are not people” objection is valid for many applications, but it does not rule out the evaluator-population mirror.
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.