| paper | d4-conf-atal-2011-0197 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: A deterministic polynomial-time \(4/3\)-approximation exists; every fixed factor \(a>1\) is achievable. Computing additive \(\epsilon\)-approximations in time polynomial in \(m,\tau,L,1/\epsilon\) is NP-hard, and therefore impossible unless \(\mathrm{P}=\mathrm{NP}\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 3.5
statement extracted from the paper’s text layer
Given candidates \(C\), target \(p\), and a rational distribution \(\mu\) over the nonmanipulators’ ranking types, find the infimum \(\lambda^\star=\inf_{\nu\ge 0}\sum_r\nu_r\) such that \(p\) is the unique Maximin winner under the normalized society \(\rho=(\mu+\nu)/(1+\sum_r\nu_r)\), where \(\nu_r\) is manipulator mass reporting ranking \(r\). Determine the computational complexity of this optimization in \(m\), the support size \(\tau\), and the input bit length \(L\), including whether an \(\epsilon\)-approximate optimum can be computed efficiently.
Types are complete rankings of \(C\); the incumbent society has rational type masses \(\mu\), and manipulators contribute decision masses \(\nu_r\) across rankings. Minimize total manipulator mass, with Maximin scores computed from the normalized combined society.
The mirror covers UCO under Maximin and uses Proposition 3.5 as motivation; it does not transfer that proposition’s approximation threshold or cover the paper’s greedy approximation theorems and average-case discussion.
The strongest positive case is a narrow one: the paper’s Unweighted Coalitional Optimization problem has a natural continuous-population form, and Proposition 3.5 gives that form a meaningful computational question to inherit.
Consider a large association election with a fixed electorate of, say, hundreds of thousands of voters but only dozens or hundreds of distinct ranking types. A coordinated bloc shares a preferred candidate \(p\), has equal voting power, and can submit any ranking. The bloc’s common target and capabilities make it one type for this problem; the incumbent electorate’s types are complete rankings. Here \(N\) can be very large while the number of supported types \(\tau\) stays moderate. This is a credible high-multiplicity regime for the paper’s unweighted model.
Lead mirror — Continuous Maximin UCO. Let \(C\) be the candidates, \(p\in C\) the target, and \(\mu\) a distribution over rankings of \(C\), with rational masses summing to \(1\). Choose a nonnegative mass \(\nu_r\) of manipulators to report each ranking \(r\), and minimize their total mass \(\sum_r\nu_r\). For any mass distribution \(\rho\), define
\[ \operatorname{MM}_{\rho}(c) = \min_{d\ne c}\sum_{r:\,c\succ_r d}\rho_r. \]
The resulting society is \(\mu+\nu\); require \(p\) to be its unique Maximin winner. The objective is the infimum
\[ \lambda^\star = \inf_{\nu\ge 0} \left\{ \sum_r\nu_r: \operatorname{MM}_{\mu+\nu}(p)> \operatorname{MM}_{\mu+\nu}(c) \ \text{for every }c\ne p \right\}. \]
A solution reports \(\lambda^\star\) and, for any requested rational \(\epsilon>0\), a feasible \(\nu\) of mass at most \(\lambda^\star+\epsilon\). Using an infimum handles cases where strict victory can be approached but not attained at the minimum mass. The input has the paper’s structure: supported ranking types with binary-rational masses, target candidate, and an optimization over coordinated reports. A discrete instance embeds by setting \(\mu_r=n_r/N\) and scaling manipulator counts by \(N\).
The anchor is Proposition 3.5, proved in this paper. It states that, unless \(P=NP\), no polynomial-time algorithm approximates UCO under Maximin with a ratio strictly better than \(3/2\). The proof uses instances with optimum \(2\): a ratio below \(3/2\) would force the algorithm’s integer answer below \(3\), hence to \(2\), and the paper invokes NP-completeness of the corresponding two-manipulator CCUM problem, cited from Xia et al. [13]. This is a genuine hardness anchor for the continuous mass-minimization question, even though the proposition’s numerical bound depends on integer coalition size.
My forecast is Class B for the continuous optimization problem: the ballot space still consists of rankings of \(m\) candidates, and its pairwise-comparison geometry remains central. A natural LP formulation has a variable for each ranking; a column-generation approach exposes a pricing problem over rankings with weighted pairwise terms. That makes persistent computational hardness plausible. This is a forecast, not a result of Proposition 3.5: the continuous pricing question and its complexity would need to be analyzed directly.
The weakest point is exactly the integrality step in Proposition 3.5. In the mirror, mass can be split among rankings, so the argument “an answer below \(3\) must equal \(2\)” disappears. In particular, the \(3/2\) inapproximability threshold does not follow. I would treat it as an open question whether that threshold survives, not present it as transferred hardness. This is also why the mirror is worth asking: it tests whether Maximin’s manipulation difficulty comes from indivisible coalition size or remains in the ranking and pairwise-score structure.
This case covers UCO under Maximin and Proposition 3.5. Further questions include whether \(\lambda^\star\) is polynomial-time computable in \(m,\tau,L\); whether any approximation threshold survives on positive-optimum instances; and how the continuous optimum relates to discrete optima as the voter-count denominator grows. The paper’s discrete greedy approximation theorems and its average-case discussion are outside this mirror.
The strongest negative case is that Proposition 3.5’s hardness does not transfer. Its proof depends on integer rounding: with optimum \(2\), an approximation ratio below \(3/2\) forces the algorithm to return exactly \(2\), deciding the two-manipulator problem. In the mass version, that threshold disappears. A rational mass solution can be cloned into a larger discrete electorate, but that gives a different UCO instance; it does not restore Proposition 3.5’s integer gap. So the proposition supports no continuous \(3/2\)-inapproximability claim.
The best attempt to reject the mirror itself is that UCO adds hypothetical manipulators to a fixed electorate. Thus \(\mu+\nu\) is not a fixed-mass society as written. But normalization preserves Maximin winners, and the coalition can be described as a mass of agents with the same target and capabilities, distributing their ballots across complete rankings. A large coordinated bloc is a plausible high-multiplicity regime. This is an extension of the input model, but a natural, author-recognizable one; it does not erase who gets what or fractionalize ballots.
I cannot make the universal negative case honestly. The proposed continuous UCO remains a well-posed computational question, with ranking structure that could still make optimization difficult. The anchor survives as motivation to study that question, though Proposition 3.5 supplies no transferred continuous hardness result. Any verdict against the mirror would need a stronger objection than the paper provides.
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.