| paper | d4-conf-atal-2013-0093 |
| 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(\mathrm P\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 11
statement extracted from the paper’s text layer
Input a finite candidate set \(C\), a society \(\mu\) with rational masses over complete ranking and party types, a distinguished leading type \(\ell\) of mass \(\mu_\ell\), its top candidate \(w\) (initially a Maximin winner), a finite list \(\mathcal D\) of allowed destination types including types with zero current mass, and a rational threshold \(q\). Is there a departure mass \(r\in[q,\mu_\ell]\) such that, for every \(x\in\mathbb R_{\ge 0}^{\mathcal D}\) with \(\sum_{j\in\mathcal D}x_j=r\), \(w\) remains a Maximin winner in \(\mu^x=\mu-r\delta_\ell+\sum_{j\in\mathcal D}x_j\delta_j\)? For each society \(\nu\), define \(M_\nu(a,b)=\sum_t\nu_t\,\operatorname{sgn}_t(a,b)\) and \(\operatorname{score}_\nu(a)=\min_{b\ne a}M_\nu(a,b)\); \(w\) remains a winner exactly when \(\operatorname{score}_{\mu^x}(w)\ge\operatorname{score}_{\mu^x}(c)\) for every \(c\in C\).
Use a rational-mass society over complete ranking and party types, with the leading source type \(\ell\) distinguished so only its mass can depart. A transfer is a nonnegative vector \(x\) over the listed destination types; it removes total mass \(r\) from \(\ell\) and distributes that mass among destinations. The objective is to find the largest \(r\) for which every such transfer leaves \(w\) a Maximin winner, or decide whether that largest robust-safe mass is at least \(q\).
Theorem 11’s reduction encodes X3C using a destination catalog that grows with the instance, while the proposed high-multiplicity story emphasizes a small catalog; the proponent does not address this gap in the hardness motivation.
fatal: False
The mirror covers the mass analogue of Maximin-pessimistic-voter-losing in Theorem 11. It leaves the other Maximin and Copeland results and all scoring-rule results untouched.
The strongest mirror is the Maximin robustness result. Theorem 11, proved in this paper, states that Maximin-pessimistic-voter-losing is coNP-complete. In the paper’s decision problem, the input is a party election, its leading party and winner \(w\), and a threshold \(q\). The question is whether at least \(q\) leading-party voters can leave while \(w\) remains a winner for every allowed assignment of those voters to other parties. The proof reduces from the complement of X3C: its construction makes an exact cover possible exactly when there is a way to move \(k\) voters that makes \(w\) lose. Thus the universal safety question is hard because the discrete departures can encode choosing one voter for each selected set.
Here is the continuous version I would ask a prover to solve. Let \(\mu\) be rational masses over the currently represented preference types, each a complete ranking of the candidates. Let \(\ell\) be the leading type, with mass \(\mu_\ell\), and let its top candidate \(w\) be an initial Maximin winner. The input also lists the allowed destination party types \(\mathcal D\), including types with zero current mass, and a rational threshold \(q\). A type includes its ranking and any transfer restrictions relevant to the problem; under the paper’s unrestricted transfers, parties with the same ranking can be merged.
For an amount \(r\in[q,\mu_\ell]\), a transfer is a vector \(x\geq 0\) over \(\mathcal D\) with \(\sum_{j\in\mathcal D}x_j=r\). It removes mass \(r\) from \(\ell\) and adds \(x_j\) to destination type \(j\). Call the resulting society \(\mu^x\). The decision problem is: does there exist an \(r\geq q\) such that \(w\) remains a Maximin winner in \(\mu^x\) for every such transfer \(x\)? A yes-instance has a witnessing safe departure mass \(r\); equivalently, the optimization version returns the largest robust-safe mass. This keeps the paper’s key quantifiers—choose how much leaves, then withstand every redistribution—while replacing voter counts with population mass.
That is a plausible high-multiplicity regime: a large membership organization or shareholder electorate with many participants but a small catalog of disciplined voting platforms. Millions of voters may follow one of a few complete rankings, and the leading bloc’s loss is naturally measured as a fraction of the electorate. The paper already makes party discipline central to its model. Here mass means the share of voters following each platform, and \(x_j\) means the share of the leading bloc that defects to platform \(j\). The destination choices and winner rule are the paper’s; the continuum changes the granularity of departure.
I expect this mirror to be Class A: tractable. For a society \(\nu\), define the pairwise margin
\[
M_\nu(a,b)=\sum_t \nu_t\,\operatorname{sgn}_t(a,b),
\]
where \(\operatorname{sgn}_t(a,b)=1\) if type \(t\) ranks \(a\) above \(b\), and \(-1\) otherwise. Maximin assigns \(a\) the score \(\min_{b\ne a}M_\nu(a,b)\). A challenger \(c\) defeats \(w\) only if its minimum margin is strictly greater than \(w\)’s.
For each possible challenger \(c\) and each candidate \(e\) that could attain \(w\)’s minimum margin, an unsafe transfer can be described by linear constraints: \(e\) is a minimum-margin opponent of \(w\), and every opponent of \(c\) gives \(c\) a margin strictly above \(M_{\mu^x}(w,e)\). The transfer variables, their total \(r\), and a positive slack for that strict advantage are all in a linear program. Projecting each such feasible region onto the single coordinate \(r\) gives an interval of departure masses at which that challenger can defeat \(w\). There are only polynomially many \((c,e)\) pairs; their intervals identify the unsafe masses, and LP endpoint checks determine whether a safe \(r\geq q\) exists. With rational input, this suggests a polynomial-time algorithm in the number of candidates, supported types, listed destinations, and bit length.
The paper’s reduction is a reason to expect a real change in complexity: exact cover relies on selecting whole voters, one at a time, for set-parties. In the mirror, transfer mass can split among destinations, so that selection structure no longer applies directly. This does not show that all Maximin losing-voter variants become easy, or that every discrete instance is approximated well. It gives a concrete continuous problem and a specific LP route for the universal-safety question in Theorem 11.
The weakest point is that splitting a party’s departing population fractionally may be a poor model if defections must happen as coordinated blocks, or if only particular members can leave. In that regime the continuous question would not preserve the paper’s action model. But the paper permits individual voters in the leading party to choose destinations; for large populations, replacing those individual choices with mass transfers seems a credible high-multiplicity relaxation of precisely the result in Theorem 11.
The best objection is that Theorem 11’s hardness construction is a poor picture of the high-multiplicity regime that makes a population continuum compelling. Its number of destination parties grows with the X3C instance, and the zero-member parties encode the sets in that instance. By contrast, the paper’s Theorem 2 puts Maximin voter-losing in P when the number of parties is fixed. In the natural regime of many voters but a small catalog of platforms, the discrete problem is already tractable; the coNP-completeness result does not describe that regime.
That objection weakens the case for prioritizing this mirror, but it does not defeat it. Theorem 2’s enumeration takes \(n^k\) time for \(n\) voters and fixed \(k\) parties, so a continuous algorithm polynomial in the number of platforms and the binary input length could still make a substantial difference for high-multiplicity inputs. And allowing the platform catalog to grow does not make the continuous question incoherent; it just makes the catalog part of the input.
The stronger version of the mirror also survives the party-label concern. Treat current party affiliation as part of a voter’s type, so only mass in the leading party is eligible to move, and list the allowed destination platforms separately, including empty ones. Many people may then share each complete type, and the adversary’s redistribution is precisely a mass transfer. Maximin winner status is expressible through pairwise margins, so the resulting question is well-posed. I see no continuous computational treatment in the paper that already answers it.
So I cannot honestly defeat the sole anchor. The high-multiplicity objection narrows the regime in which the paper’s hardness result motivates the mirror, but a large electorate with many members per platform remains plausible, and the continuous robustness question remains worthwhile. The negative case is weak.
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.