| paper | d4-conf-atal-2017-0310 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given an even candidate set \(X\) and a rational distribution \(\mu\) over complete rankings of \(X\), compute an extended dominating \(m/2\)-subset graph \(G\) maximizing \(\sum_{(x,y)\in E(G)} d_\mu(x,y)\), where \(d_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t-\sum_{t:y\succ_t x}\mu_t\). The graph is a tournament whose upper set has size \(m/2\) and dominates its complement; the question is to return a maximizing graph, equivalently its selected upper set and internal orientations.
Use ranking types as the support of \(\mu\), with each binary-rational mass recording that type's population fraction. The decision is the upper set of size \(m/2\) and the orientations within each block; cross-block orientations are fixed by domination, and the objective is the sum of population margins over all graph edges.
The optimization depends only on pairwise margins, so computing those from \(\mu\) takes \(O(m^2\tau)\) preprocessing and leaves the paper's weighted-tournament problem; this limits the mirror's additional computational content, though the proponent acknowledges that the full distribution is compressed to pairwise summaries.
fatal: False
The mirror covers Theorem 3 and Proposition 2; it does not extend their conclusions to the paper's other rules, constraints, or properties.
A plausible regime is a large party or association election over a fixed slate. Each voter’s type is their complete ranking of the candidates; voters with the same ranking are indistinguishable for these rules. The society is a rational distribution \(\mu\) over the \(\tau\) rankings that occur, with \(N\gg\tau\). The output remains the paper’s ranking or graph over candidates; only the population is continuized. This is a natural high-multiplicity regime for the paper’s profile-based rules.
My lead is the paper’s Theorem 3, which states that computing \(\mathrm{MED}_{\mathrm{ExtDom}_k}(V)\) is NP-hard even when \(k=m/2\). The paper proves this by reduction from *oneway section*; the proof is in its long version and omitted from the proceedings text.
Here is a continuous version of that problem. Given an even-sized candidate set \(X\) and a rational distribution \(\mu\) over complete rankings of \(X\), define the population margin
\[
d_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t-\sum_{t:y\succ_t x}\mu_t.
\]
A solution is an extended dominating \(m/2\)-subset graph \(G\): a tournament whose candidates divide into \(S\) and \(X\setminus S\), with \(|S|=m/2\), and every candidate in \(S\) pointing to every candidate outside it. The task is to return a graph maximizing
\[
\sum_{(x,y)\in E(G)}d_\mu(x,y).
\]
Its upper set \(S\) is the selected committee; the internal orientations preserve the extended graph structure the authors study. Equivalently, for each candidate pair within either block, an optimal graph orients the edge toward the positive margin, while cross-block edges are fixed. This makes the objective—and the question—fully specified by the population distribution.
I expect this mirror to be Class B: hardness transfers. Any finite profile \(V\) maps to its empirical distribution \(\mu_t=n_t/n\); the continuous margins are the discrete margins divided by \(n\), so the maximizing graphs are unchanged. The hard part is choosing the partition among alternatives, not distinguishing individual voters. A useful next question is whether the hardness persists when the support size \(\tau\) is restricted, and whether other ranges of \(k\) admit parameterized algorithms.
A second, distinct anchor is Proposition 2: computing \(\mathrm{MH}_{\mathrm{ExtCh}_k}\) and \(\mathrm{MH}_{\mathrm{PlCh}_k}\) is NP-hard, even for \(k=m\). At that value of \(k\), both constraints yield rankings. The proposition follows from cited NP-hardness results for Slater ranking [1, 7, 5]; the paper does not present that hardness as a new reduction.
The corresponding continuous problem is: given \(X\) and a rational distribution \(\mu\) over rankings, assume no pair has a tied population majority, and orient each pair according to its majority to obtain the tournament \(T_\mu\). Return a ranking \(R\) minimizing
\[
|E(R)\setminus E(T_\mu)|+|E(T_\mu)\setminus E(R)|.
\]
This is the continuous Slater-ranking problem: the chosen ranking minimizes the number of pairwise orientations it reverses against the population majority tournament. Requiring strict majorities mirrors the paper’s odd-electorate assumption. The objective intentionally uses the majority direction, not the size of the majority margin.
This is also Class B. An odd finite electorate gives a strict-majority distribution, and its Slater rankings are exactly the rankings minimizing this distance. So the paper’s hardness remains in the continuous formulation. A natural follow-up is whether the problem’s complexity changes with \(\tau\), or if one replaces the sign-only objective with a margin-weighted one.
These two mirrors cover only Theorem 3 and Proposition 2. I would not generalize their conclusions to the paper’s other rules or constraints. Their strongest point is that the paper already defines its rules on profiles and on majority or weighted-majority relations, making the move to a distribution over ranking types direct.
The weakest point is that these models retain only pairwise summaries of \(\mu\). In the Slater mirror, all margin magnitudes disappear once the majority directions are fixed; in the median mirror, the full distribution matters only through pairwise margins. A critic could say these are weighted-tournament problems in a new input language. That is a real limitation, but the input language has a clear population interpretation, and the empirical-profile map gives a precise high-multiplicity bridge. The positive case is for sensible continuous-population versions of these specific computational questions, not for a new tractability result.
The strongest case against both mirrors is that the paper has already compressed away the population. Slater computation takes a majority tournament as input; the median rule takes a weighted tournament. For the proposed continuous versions, one computes
\[
d_\mu(x,y)=\sum_t\mu_t\bigl(\mathbf 1[x\succ_t y]-\mathbf 1[y\succ_t x]\bigr)
\]
from the support and then runs the paper’s graph problem. That takes \(O(m^2\tau)\) preprocessing. The rules never use the distribution beyond those pairwise summaries.
For Proposition 2, this is especially direct: the paper defines minimum Hamming distance on tournaments, and Slater is the \(k=m\) case. Giving the tournament a population interpretation does not create a new computational problem. For Theorem 3, the same objection applies to the weighted margins. The continuous median objective is exactly the paper’s weighted-tournament objective after rescaling rational margins; its hard instances already arise from profiles. A distribution over rankings supplies a natural story for those weights, but no extra information that the computation uses.
That is the best collision argument, but it does not establish the requested universal negative. A distribution over complete ranking types is a sensible model for a large party or association election, and the paper does not itself give the population as a list of types with rational masses. An algorithm parameterized by support size and bit length, or a formal high-multiplicity dictionary, could still be useful even when these particular rules factor through pairwise margins. Those are meaningful avenues, not objections the paper settles merely by stating the tournament problem.
Nor do the better versions repair the negative case. For Slater, allowing tied population margins with a natural tie convention avoids relying on an odd finite electorate, but the computation still reduces to the same tournament problem. For the median rule, asking only for the selected committee rather than the full extended graph makes the output more application-facing, but still leaves a well-posed population-input problem with the same margin objective. One could instead ask how much ranking mass must move to change the chosen committee; that would make population masses operationally central, but it adds an intervention question not asserted by Theorem 3.
So I can argue that the two proposed mirrors add little computational content beyond the paper’s existing aggregate inputs. I cannot honestly argue that no worthwhile continuous mirror exists in any scenario: the type regime is plausible, and the mirrors are well-posed. The negative case is therefore weak at its central claim.
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.