| paper | d4-conf-atal-2015-0060 |
| 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}\)-complete, even for \(\alpha=1\), \(d=k\), distinct approval types of weight two, and positive dyadic masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given candidates \(C\), a finite support \(T\subseteq\{0,1\}^{m}\) of approval ballots with positive rational masses \(\mu_t\) summing to \(1\), integers \(k,d\), and a rational threshold \(\alpha\), does there exist a committee \(X\subseteq C\) with \(|X|=k\) such that \(\sum_{t\in T:\,d_H(\chi_X,t)\le d}\mu_t\ge\alpha\)?
Each type is an approval ballot \(t\in\{0,1\}^{m}\) with mass \(\mu_t\). Choose an integral committee \(X\subseteq C\) of size \(k\) to maximize the inlier mass \(\sum_{t:\,d_H(\chi_X,t)\le d}\mu_t\), and ask whether that mass reaches \(\alpha\).
The hardness reductions encode their combinatorics in candidate selection, and count-to-mass normalization adds little new optimization structure; this bounds the likely methodological payoff.
fatal: False
The mirror covers the outlier results in Theorems 7 and 10; it does not claim the ordinary Minimax Approval Voting results or the closest-string results have the same mass-based interpretation.
The strongest mirror is the paper’s outlier version of Minimax Approval Voting. A type is an approval ballot \(t\in\{0,1\}^m\); \(\mu_t\) is the fraction of the population with that ballot. Let \(T\) be the listed support, with positive binary-rational masses summing to one. The decision remains an integral committee \(X\subseteq C\) of exactly \(k\) candidates. For a distance threshold \(d\), define its outlier mass by
\[
O_d(X;\mu)=\sum_{t\in T:\,d_H(\chi_X,t)>d}\mu_t.
\]
This changes the population description, while preserving the paper’s committee, approval ballots, Hamming distance, and outlier criterion.
That model fits a large membership organization consulting its members on a fixed slate of projects or nominees. Members submit standardized approval ballots, so those with the same ballot are indistinguishable for this problem. The population might have millions of members but only hundreds or thousands of recurring ballot types. In the pair-ballot case used below, each type approves a pair of candidates; many members can share each pair type. Asking what fraction of members are close enough to a proposed slate is a natural version of the paper’s question about how many voters it satisfies.
The lead question is Continuous Outlier Minimax Approval Optimization: given \(C,T,\mu,k,d\), return an exact-\(k\) committee \(X\) minimizing \(O_d(X;\mu)\). The solution is the committee and its outlier fraction. This mirrors the paper’s approximation result.
Theorem 7, proved in this paper, says that for some \(\epsilon>0\), a polynomial-time \((1+\epsilon)\)-approximation algorithm for Minimax Approval Voting with Outliers would imply \(P=NP\). The paper’s approximation objective is to minimize the number of outliers at fixed committee size and distance threshold. Its proof reduces MAX-2-SAT to that problem, using clause ballots and repeated “fixing” ballots. The continuous instance groups identical ballots and assigns each type its multiplicity divided by the total number of voters. For every committee, outlier mass is then exactly the discrete outlier count divided by the electorate size, so the reduction’s approximation gap is preserved. In particular, the repeated fixing ballots become larger masses on their types; aggregation does not remove their force. Thus the continuous optimization problem also admits no PTAS unless \(P=NP\). This is a hardness-transfers result: the reduction’s combinatorics are encoded in the candidate coordinates and ballots, not in needing one voter per unit of mass.
A second, closely related question is Mass-Threshold Continuous Minimax Approval Voting: given the same \(C,T,\mu,k,d\) and a rational threshold \(\alpha\), decide whether there is an exact-\(k\) committee \(X\) with
\[
\sum_{t\in T:\,d_H(\chi_X,t)\le d}\mu_t\ge\alpha.
\]
A solution is such a committee, together with a set of inlier types whose mass reaches \(\alpha\). Here the population fraction is the decision threshold, rather than the objective.
Theorem 10, also proved in this paper, says that Minimax Approval Voting with Outliers is W[1]-hard when parameterized by \(s,d,k\), where \(s\) is the number of voters to satisfy. Its proof reduces parameterized \(k\)-Clique: make one candidate for each graph vertex and one ballot approving the two endpoints for each edge; set committee size \(k\), distance \(d=k-2\), and \(s=\binom{k}{2}\). A size-\(k\) committee is within distance \(k-2\) of an edge ballot exactly when it contains both endpoints. Satisfying at least \(\binom{k}{2}\) edge ballots therefore means the selected vertices form a clique.
The same construction gives the continuous decision problem with uniform mass \(1/|E|\) on each edge type and \(\alpha=\binom{k}{2}/|E|\) (trivial cases with too few edges can be handled directly). A committee reaches that mass exactly when it contains at least \(\binom{k}{2}\) edges, hence when it is a clique. This makes the mirror W[1]-hard parameterized by \(k+d\), with \(\alpha\) an ordinary rational input. Replicating each edge type’s voters leaves \(\mu\) unchanged, so the scenario can have \(N\gg\tau\). This is another hardness-transfers result, and a particularly direct one: the hard object is the choice among candidates, while the voter types simply encode graph edges.
Theorem 7 is my lead because its outlier objective makes population mass central: it turns a count of excluded voters into a fraction of society, and its reduction already uses repeated ballots that aggregate naturally. Theorem 10 provides a crisp decision anchor and an explicit clique interpretation.
The weakest point is that the paper motivates outliers by counts, not fractions, and its reductions are engineered rather than evidence about a particular real electorate. Still, replacing a count \(s\) out of \(n\) voters by the fraction \(\alpha=s/n\) preserves the authors’ approval types, committee constraint, distance measure, and satisfaction rule. I would expect the authors to recognize this as their outlier problem on a population distribution. These mirrors cover Theorems 7 and 10; they do not claim that the paper’s non-outlier results have the same mass-sensitive interpretation.
The strongest case against is that neither mirror seems to call for the continuous optimization machinery ChoCo hopes to bring into ComSoC. In both, the society is a rationally weighted list of approval ballots, while the decision is still an integral \(k\)-candidate committee. The appeal is therefore mainly a high-multiplicity complexity question. That may make the programme’s payoff smaller than in a problem where continuous modeling exposes a new LP or convex formulation.
But this is a concern about payoff, not a defeat of either anchor.
For Theorem 7, the strongest mirror is exactly the proposed minimization of outlier mass. Given a discrete instance with \(N\) voters, set \(\mu_t\) to the count of ballot \(t\) divided by \(N\). Then every committee has outlier mass equal to its discrete outlier count divided by \(N\). The approximation ratios are unchanged, and the repeated fixing ballots in the reduction remain concentrated mass on their ballot types. Conversely, any rational distribution can be expanded into a finite multiset using a common denominator. Aggregating the reduction’s duplicate ballots therefore preserves its force. The theorem supplies a valid hardness result for the distribution model, even if it does not supply a new algorithmic technique.
For Theorem 10, the continuous threshold question also survives. Give each graph-edge ballot mass \(1/|E|\), and set \(\alpha=\binom{k}{2}/|E|\). Reaching that mass at distance \(k-2\) means selecting all endpoints of at least \(\binom{k}{2}\) edges, exactly the clique condition in the reduction. Every edge ballot can represent many members, with no change to the distribution. This is a direct mass-based decision question. The reduction’s combinatorics live in the candidate choice, but that is not a reason to reject a well-posed population mirror; hardness that carries over is part of the programme’s intended landscape.
I cannot make a credible universal case that no scenario works. Approval ballots fully describe voters for these problems, and large populations sharing ballot types are plausible. The paper’s outlier questions ask how much of that population a committee serves, which gives mass a natural role. The honest negative case is weak: these mirrors may yield less new optimization structure than some other continuizations, but both anchors remain worthwhile computational questions under the stated programme.
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.