| paper | d4-conf-atal-2017-0249 |
| 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: For each fixed \(\alpha\in\{0,1\}\), the decision problem is \(\mathrm{NP}\)-complete. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Claim 2
statement extracted from the paper’s text layer
Given a candidate set \(A\), bundle size \(k\), threshold \(\ell\), fixed \(\alpha \in \{0,1\}\), and an explicit binary-encoded rational distribution \(\mu\) over a support of \(\tau\) strict rankings of \(A\), does there exist a bundle \(B \subseteq A\), \(|B|=k\), such that \(\left|\{(x,y): x \in B,\ y \notin B,\ p_\mu(x,y)>1/2\}\right|+\alpha\left|\{(x,y): x \in B,\ y \notin B,\ p_\mu(x,y)=1/2\}\right|\ge \ell\), where \(p_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t\)?
Types are strict rankings \(t\) with rational masses \(\mu_t\); choose a discrete bundle \(B \subseteq A\) of size \(k\). Its objective is the number of cross pairs \((x,y)\), \(x \in B,\ y \notin B\), with \(p_\mu(x,y)>1/2\), plus \(\alpha\) times the number with \(p_\mu(x,y)=1/2\).
The mirror covers Copelandₖ(α) threshold hardness for α ∈ {0,1}, the tie-free Copelandₖ algorithm, and Dec-Maximinₖ hardness. It leaves the approximation results and the Ranked Pairs and Schulze algorithms unexamined.
I see a credible population mirror here, with one qualification about the paper’s labels: its hardness results are printed as Claim 2 and Claim 4, so I retain those names. The matching tractability result is Theorem 1. The strongest anchor is Claim 2.
Take the paper’s cable bundle scenario. There are \(m\) candidate channels and a fixed bundle size \(k\). A type is a customer’s complete strict ranking of those channels; a society is a rational distribution \(\mu\) over the \(\tau\) rankings with positive mass. The mass \(\mu_t\) is the fraction of customers with ranking \(t\). This is a plausible regime when a very large customer base falls into relatively few stable preference groups, so \(N\) is much larger than \(\tau\). Ranking is the paper’s entire model of an agent’s preferences, so grouping customers by identical rankings preserves everything its rules use.
For any channels \(x,y\), write \(p_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t\). A neighboring bundle pair differs by one channel, and the first bundle defeats the second exactly when the included channel is preferred to the excluded one by more than half the population. This keeps the paper’s bundle-selection question intact: choose \(k\) channels by majority comparisons. The population is continuous; the bundle and candidate set remain discrete.
Lead — Claim 2, proved in this paper. The paper proves that, for each \(\alpha\in\{0,1\}\), it is NP-complete to decide whether there is a size-\(k\) bundle with Copeland\(_k(\alpha)\) score at least a given threshold \(\ell\). The score counts the neighboring bundles it defeats, plus \(\alpha\) times the number of tied neighboring bundles. The paper proves hardness for both values: its reductions use Max-DICUT with prescribed part sizes for \(\alpha=0\), and one-way bisection for \(\alpha=1\).
The continuous question is: given \(A,k,\alpha,\ell\) and an explicit rational distribution \(\mu\) over rankings, does there exist \(B\subseteq A\), \(|B|=k\), such that
\[
\left|\{(x,y):x\in B,\ y\notin B,\ p_\mu(x,y)>1/2\}\right|
+\alpha\left|\{(x,y):x\in B,\ y\notin B,\ p_\mu(x,y)=1/2\}\right|
\ge \ell?
\]
A solution is such a bundle \(B\); the decision problem is in NP because its score can be checked by summing the rational masses for each pair. I expect NP-completeness, with hardness transferring from the discrete problem. Any finite profile maps directly to its empirical distribution, \(\mu_t=n_t/n\); the paper’s reductions construct profiles of polynomial size, so this mapping preserves polynomial encoding size. The reduction’s combinatorics are in the candidate set and the choice of bundle, which is the programme’s Class B pattern. This is the strongest mirror: it asks whether the paper’s hardness survives when voters are represented by population shares, and the paper’s own reductions give a direct reason to expect that it does.
Theorem 1, proved in this paper, provides the tie-free boundary. It says that Algorithm 1 computes a Copeland\(_k\) winning bundle in polynomial time when the tournament graph has no ties. Its continuous counterpart takes the same distribution input, requires \(p_\mu(x,y)\ne 1/2\) for every pair, and asks for a size-\(k\) bundle maximizing the number of neighboring bundles it defeats. A solution is any maximizing bundle. This is polynomial in \(m,\tau,L\): compute each pairwise mass, each channel’s number of pairwise victories, then choose the \(k\) highest-scoring channels. It mirrors the paper’s problem directly. Together with Claim 2, it gives a meaningful distinction between tie-free instances and the specified tie-scoring variants.
Claim 4, also proved in this paper, anchors a separate Maximin question. The paper proves that Dec-Maximin\(_k\)—whether some size-\(k\) bundle has every outgoing edge in \(W^{(k)}\) of weight at least a given threshold—is NP-complete. In the distribution model, given a rational \(\theta\in[0,1]\), ask whether there exists \(B\subseteq A\), \(|B|=k\), with
\[
p_\mu(x,y)\ge\theta
\quad\text{for every }x\in B,\ y\notin B.
\]
A solution is a bundle satisfying every pairwise threshold. Again, membership in NP follows from exact rational comparisons, and hardness transfers by normalizing the finite-profile counts by the number of voters. In the paper’s reduction, the count threshold is \(R/2\), so the continuous reduction uses the fixed threshold \(\theta=1/2\). This hardness also comes from combinatorics on the candidate set; it is not caused by having to represent each voter separately.
Further questions include how Copeland’s complexity varies with \(\alpha\), given the paper’s tractable \(\alpha=1/2\) result and its hardness at \(0\) and \(1\); whether either hard problem becomes tractable for restricted support size or structured ranking supports; and how the paper’s size-relaxed Maximin approximation behaves when thresholds are expressed as population shares.
The weakest point is that these rules depend only on pairwise comparison masses, so the mirror does not appear to call for new continuous-optimization machinery. The transferred hardness is also a caution against promising a tractability gain. But that does not make the mirror a restatement: the paper gives finite voter profiles, while the proposed instances are distributions encoded by support and rational mass. The authors should recognize the model—the same rankings, majority comparisons, and bundle objectives remain—and the resulting complexity boundary is exactly the kind of computational question the continuization programme is meant to chart.
The strongest case against this mirror is about its marginal value. Every rule in the paper factors through the pairwise majority matrix: the distribution over rankings is used only to compute whether each pairwise mass is above, below, or equal to \(1/2\). Once those comparisons are known, the rest is a problem on a weighted graph over candidates or bundles. The continuous society creates no fractional decision variable, and the paper’s algorithms do not need continuous optimization machinery. That makes this a poor fit for the programme’s second motivation: bringing new optimization tools to problems that otherwise go unmodeled.
That concern applies to all three anchors. Claim 2’s continuous instance is a rationally weighted version of the paper’s pairwise graph problem; the paper’s finite-profile reductions already yield rational distributions by dividing counts by the number of voters. Claim 4 has the same direct normalization for its threshold. Theorem 1’s argument also carries over directly: compute pairwise masses, count each candidate’s victories, and select the \(k\) highest-scoring candidates. The continuous formulations are clean, but they appear to add little mathematical work beyond changing counts to shares.
That is the honest negative case, and it is weak against the assignment’s standard. A distribution over rankings is a sensible high-multiplicity society; majority comparisons remain well-defined; and the paper proves named computational results that can be asked over that society. The fact that their answers may transfer immediately, or that the underlying algorithms use no new continuous-optimization technology, does not defeat the mirrors under the stated rules. I cannot responsibly claim that any of the three anchors fails. Claim 2 is the strongest: its continuous question is well-posed and its finite-profile hardness reduction transfers directly. The negative case supports a concern about research priority, not the conclusion that no worthwhile mirror exists.
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.