| paper | d4-conf-ecai-2025-0041 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathsf{NP}\text{-complete}\), already with \(m=1\) and unrestricted \(d\); polynomial-time decision and rational-position construction for fixed \(d\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a dimension \(d\), distinct types \(x^1,\ldots,x^\tau\in\{-1,+1\}^d\), positive rational masses \(\mu_i\) summing to \(1\), and a rational threshold \(q\in[0,1]\), place the incumbent at the origin and decide whether there is a position \(y\in\mathbb{R}^d\) for which \(\sum_{i=1}^{\tau}\mu_i\mathbf{1}[\|x^i-y\|_2<\|x^i\|_2]\ge q\); return such a position when one exists.
A finite-support society \(\mu\) over voter ideal-point types, with each type receiving its mass and the incumbent fixed at the origin; the new candidate chooses \(y\in\mathbb{R}^d\), and the objective is to reach a target share of voters strictly closer to \(y\) than to the incumbent.
Exact repeated ideal points are more restrictive than approximate survey clusters, and the hard instances allow support to grow with the constraints; this leaves relevance at small support less established.
fatal: False
The mirror covers the one-opponent plurality hardness of Theorem 1 and the fixed-dimension algorithm of Theorem 2; it leaves the many-candidate approximation results, rank objective, and positional-scoring extensions aside.
The strongest mirror is the paper’s one-opponent plurality problem. A type is a voter’s ideal policy point \(x^i\); people of that type share the same spatial preferences. A society is a finite-support distribution \(\mu\) over those types, with rational masses \(\mu_i>0\) summing to \(1\). Put the incumbent at the origin, and let the new candidate choose a policy point \(y\). The share of the electorate won is
\[ W_\mu(y)=\sum_{i=1}^{\tau}\mu_i\, \mathbf{1}\!\left[\|x^i-y\|_2<\|x^i\|_2\right]. \]
Ties go to the incumbent, as in the paper.
Lead problem — Mass-OCP-D\(_2\). The input is a dimension \(d\), types \(x^i\in\{-1,+1\}^d\) with rational masses \(\mu_i\), and a rational threshold \(q\in[0,1]\). Decide whether some candidate position \(y\in\mathbb{R}^d\) satisfies \(W_\mu(y)\ge q\); a yes-solution includes such a position. This is exactly the paper’s vote-threshold question with the vote count normalized to a share: if type \(i\) occurs \(n_i\) times in a finite electorate of size \(N\), set \(\mu_i=n_i/N\) and \(q=k/N\). Repeated voters of the same type can be merged without changing the answer.
My anchor is Theorem 1, proved in this paper: OCP-D\((\nu_2)\) is NP-complete with one existing candidate and all voter coordinates in \(\{-1,+1\}\). The paper proves this by reducing from FLShb: matrix rows become voter locations, columns determine the issue dimension, the incumbent is at the origin, and the threshold is preserved. The same reduction gives hardness for Mass-OCP-D\(_2\) by assigning each row type its frequency divided by the number of rows. This is my strongest anchor because the mirror preserves the underlying decision problem and its hardness.
A plausible regime is a large multi-issue constituency whose voters fall into repeated, standardized ideal-policy profiles. For instance, a survey or established political segmentation might identify recurring positions on \(d\) issues, with many voters in each group. The electorate may have \(N\) people and only \(\tau\) distinct profiles, with \(N\) much larger than \(\tau\); cloning every profile equally many times leaves the distribution and answer unchanged. For the hardness instances, \(d\) and \(\tau\) can still grow. So this is a high-multiplicity regime, but the hardness is driven by the issue dimension and support structure, not by needing to distinguish individual voters.
There is a useful tractability companion. Theorem 2, also proved here, says that with one opponent, fixed dimension \(d\), and \(\ell_p\) distance for integer \(p>1\), OCP\((\nu_p)\) can be solved in time \(\Theta(n^{d+1})\), including finding an actual candidate position. Its continuous analogue, Mass-OCP-Max\(_2\), takes rational voter ideal points \(x^i\in\mathbb{Q}^d\) with rational masses and asks for a position \(y\) maximizing \(W_\mu(y)\), returning both \(y\) and the maximum share. For fixed \(d\), the paper’s arrangement algorithm can enumerate regions using the \(\tau\) distinct types and sum their masses, giving a polynomial-time algorithm in \(\tau\) and the mass bit length. The mirror thus retains a recognizable boundary: variable dimension gives the hardness anchor, while fixed dimension gives an algorithmic result.
I expect Mass-OCP-D\(_2\) to be Class B: the finite problem embeds exactly by rational normalization, so the discrete hardness transfers. The fixed-dimension optimization version is tractable by the paper’s region-enumeration method. Natural follow-up questions include whether the dimension dependence can be made FPT, how the weighted problem behaves with multiple opponents, and which results extend to other norms. This case covers the paper’s one-opponent plurality results; it does not claim a mirror for the many-candidate approximation results, rank objective, or positional-scoring extensions.
The authors should recognize these as their problems: the metric, truthful voting rule, incumbent, candidate action, tie convention, and vote objective all remain the same. The policy space was already continuous in the paper; the mirror’s new continuous object is the electorate distribution \(\mu\). My weakest point is that exact repeated ideal points can be a strong modeling assumption, and the hardness survives through a weighted restatement of the finite input rather than a new continuum-specific mechanism. Standardized issue profiles make that regime plausible, and the high-multiplicity bridge is precisely why this restatement still matters for ChoCo.
The strongest case against is about how much population structure these mirrors actually capture. A complete type here must include the voter’s exact ideal point \(x\in\mathbb{Q}^d\). Aggregation merges only voters with identical points. In the hardness reduction, the support can grow with the number of constraints, so converting vote counts to rational masses may leave \(\tau\) essentially as large as the original electorate description. Theorem 1 then gives a clean high-multiplicity restatement, but its reduction does not show that the computational question becomes useful when a society has a small, reusable vocabulary of types.
Theorem 2 has the same limitation in the opposite regime: fixed \(d\) lets the arrangement algorithm enumerate regions and add type masses, but the mirror remains a weighted point-set problem. Replacing survey bins with exact types also needs care: voters grouped into one approximate profile can fall on different sides of a candidate’s boundary, so treating the whole group as a single location changes their votes. An atomless ideal-point distribution would avoid that grouping assumption, but its computational meaning depends on how the distribution is represented, and the paper’s finite-support results do not answer that version.
That is the strongest negative case I can make, and it does not defeat the anchors. The authors’ model admits a plausible regime of large constituencies with repeated, exact policy profiles. There the vote share is well-defined, the type is complete, Theorem 1 transfers by rational normalization, and Theorem 2 extends by summing masses over the arrangement regions. Those are legitimate population continuizations under ChoCo’s stated bridge; the fact that they resemble weighted finite instances is not, by itself, a collision or a scope objection.
So the case against is weak. It raises a real question about whether exact profile groups are common enough, and whether the results matter when \(\tau\) is small, but the proposed profile-based scenario answers the first concern well enough to keep the mirror worthwhile. I cannot honestly say that no worthwhile continuous mirror exists for this paper.
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.