| paper | d4-conf-aaai-2012-0027 |
| 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: Achieving approximation ratio \(\max\{1,\delta\log m\}\) is \(\mathrm{NP}\)-hard for some constant \(\delta>0\), even with dyadic rational masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.4
statement extracted from the paper’s text layer
Given candidates \(C\), a rational distribution \(\nu\) over rankings of total mass \(1-\beta\), a caucus of mass \(\beta>0\) with common true ranking \(R\), and a target \(p\) ranked first by \(R\), find a ranking \(L\) minimizing \(d_{\mathrm{swap}}(R,L)\) such that \(p\) is the unique Maximin winner under \(\mu_L=\nu+\beta\delta_L\), or report that none exists. Here \(M_{\mu_L}(c)=\min_{d\ne c}\sum_{t:\,c\succ_t d}\mu_{L,t}\), and the required condition is \(M_{\mu_L}(p)>M_{\mu_L}(q)\) for every \(q\ne p\).
A continuous ranking-type distribution for the background electorate plus a homogeneous, coordinated caucus of mass \(\beta\). The caucus acts as one unit, choosing a common ranking \(L\); its per-member cost is \(d_{\mathrm{swap}}(R,L)\), and its goal is to make \(p\) the unique Maximin winner.
The discrete hardness embedding uses \(\beta=1/n\), so it does not establish the complexity of the distinctive fixed-positive-mass caucus regime.
fatal: False
The mirror covers the swap-distance hardness results for Maximin and Copeland-\(\alpha\); it leaves the scoring-rule and Bucklin algorithms, the other distance measures, and their results unaddressed.
The best positive case is an atomic-background continuum: represent the large, ordinary electorate by rational masses over rankings, while retaining the paper’s manipulator as a bloc that submits one common ranking. That preserves the paper’s central choice—one report close to a true ranking—and makes the society itself a distribution over voter types.
For either problem below, the instance has candidates \(C\), a rational background distribution \(\nu\) over rankings with total mass \(1-\beta\) and support size \(\tau\), a bloc of mass \(\beta>0\) with common true ranking \(R\), and a target \(p\), which is \(R\)’s top-ranked candidate. The bloc chooses one ranking \(L\) for all its members. The resulting society is
\[
\mu_L=\nu+\beta\delta_L.
\]
A solution is a ranking \(L\) that makes \(p\) the unique winner and minimizes the per-member cost \(d_{\mathrm{swap}}(R,L)\). If no such ranking exists, the optimum is \(+\infty\). The bloc’s type includes its ranking and its role in the problem; the background has only \(\tau\) supported ranking types. In a high-multiplicity regime, many voters share those few rankings, alongside a homogeneous, coordinated bloc.
A plausible setting is a large association election with a handful of common candidate rankings and a caucus whose members share a ranking and coordinate on one ballot. The caucus might be a substantial share of the electorate. When it is as small as one voter, it can affect the outcome only in a sufficiently close election.
Lead: Continuum Optimal Maximin Manipulation. For each ranking, define its Maximin score in \(\mu_L\) as
\[
M_{\mu_L}(c)=\min_{d\in C\setminus\{c\}}\sum_{t:\,c\succ_t d}\mu_{L,t}.
\]
The question is: given \(C,\nu,\beta,R,p\), find a ranking \(L\) minimizing \(d_{\mathrm{swap}}(R,L)\), subject to
\[
M_{\mu_L}(p)>M_{\mu_L}(q)\qquad\text{for every }q\ne p.
\]
The strict inequalities reflect the paper’s adversarial tie-breaking convention.
The anchor is Theorem 4.4, proved by the paper’s authors. It states that for some \(\delta>0\), \((d_{\mathrm{swap}},\mathrm{Maximin})\)-OPTMANIPULATION has no polynomial-time \(\delta\log |C|\)-approximation unless \(P=NP\). The paper obtains the result through a reduction from Set Cover, using the cited Set Cover inapproximability result. This is my strongest anchor: it is a hardness result with logarithmic inapproximability, and the reduction’s combinatorics are in the candidate set.
Second anchor: Continuum Optimal Copeland-\(\alpha\) Manipulation. Use the same instance and objective. For each pair \(a,b\), let
\[
w_{\mu_L}(a,b)=\sum_{t:\,a\succ_t b}\mu_{L,t}.
\]
Copeland-\(\alpha\) gives a candidate one point for each pairwise win, \(\alpha\) points for each pairwise tie at \(1/2\), and zero for each loss. The question is to minimize \(d_{\mathrm{swap}}(R,L)\) subject to \(p\) being the unique Copeland-\(\alpha\) winner.
The anchor is Theorem 4.5, also proved by the authors. For every \(\alpha\in\mathbb{Q}\cap[0,1]\), it states that \((d_{\mathrm{swap}},\mathrm{Copeland}_\alpha)\)-OPTMANIPULATION has no polynomial-time \(\delta\log |C|\)-approximation for some \(\delta>0\), unless \(P=NP\). It shows the hardness extends across the paper’s full Copeland-\(\alpha\) family.
These are continuous-population questions: the fixed society is a rational distribution over types, and its pairwise scores are computed from mass. They do not continuize outcomes, lotteries, or time. They also retain the paper’s target, true ranking, manipulation action, distance objective, and winner condition. A discrete instance with \(n\) voters embeds exactly by taking \(\beta=1/n\) and giving each background ranking mass equal to its number of nonmanipulating voters divided by \(n\). The normalized pairwise scores yield exactly the same winners, and the manipulator’s cost is unchanged. Thus both mirrors inherit hardness from their named results: they are expected to be hardness-transferring, Class B cases. The continuous input generalizes the empirical distribution to arbitrary binary-rational masses, with running time measured in \(|C|\), \(\tau\), and their bit length.
The weakest point is that the bloc sends one common report. Its mass is continuous in the society, but the model does not let the bloc split across different reports. A referee who requires a fully divisible manipulation action may regard this as too conservative. The version that permits \(x_L\ge 0\) with \(\sum_L x_L=\beta\), and moves each part of the bloc to a different ranking, is a further question: the paper’s one-voter hardness does not by itself settle it, since fractional splitting could change the reduction. The one-report model is compelling precisely because it preserves the paper’s individual choice while making the background electorate a continuous object. The paper’s scope mirrored here is its swap-distance hardness for Maximin and Copeland; this case makes no claim about its scoring-rule or Bucklin results.
The strongest case against both anchors is a semantic one. Theorem 4.4 for Maximin and Theorem 4.5 for Copeland-\(\alpha\) are genuine computational results, so lack of a result to mirror is no objection. The difficulty is keeping the paper’s *single manipulator* while making the population continuous.
If that manipulator has measure zero in a nonatomic society, changing their ranking does not change any pairwise mass. Except at the boundary where the target already ties, the winner condition is therefore unaffected; the optimization collapses to cost \(0\) or infeasibility. Giving the manipulator positive mass avoids that collapse, but turns the intervention into a coordinated bloc: many voters jointly choose one report. Sharing a type makes those voters alike; it does not make them one decision-maker. If they can choose reports independently, the natural model instead permits a mass split across rankings, which is a coalition or bribery problem rather than the paper’s one-vote manipulation problem.
This exposes a limit in what the two theorems establish for a continuum. The proposed embedding is exact when the bloc has mass \(\beta=1/n\), but that is a vanishing-mass slice as the electorate grows. The results do not by themselves settle the more distinctive regime of a bloc with fixed positive mass. That weakens the case that these particular theorems motivate the continuum question; it does not show the question is uninteresting.
And that is where the negative case falls short. A coordinated caucus in a large association election is a plausible setting, and a positive-mass bloc changing its common ballot is a well-defined mass intervention. The society is still represented by rational masses over ranking types, and both Maximin and Copeland have natural mass-based winner conditions. The programme explicitly allows population-driven changes to the model, so dismissing the bloc as outside scope would not hold.
The same objection applies to both anchors, but it does not defeat either best version. I cannot make an honest universal case that neither has a worthwhile continuous mirror: the case against is weak, and both anchors survive it.
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.