| paper | d4-conf-ecai-2025-0201 |
| 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: \(\mathrm{NP}\)-hard for Hamilton and every fixed divisor method specified in the question, even when \(s_j=1\) in every district. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given fixed districts and parties, district seat counts, an apportionment method \(R\), a target party \(P^\star\), a seat target \(\ell\), rational masses \(\mu_{j,i}\) on district–party voter types with \(\sum_{j,i}\mu_{j,i}=1\), a rational global eligibility threshold \(\theta\), and a rational mass budget \(\beta\), is there a within-district transfer \(x_{j,i,k}\geq 0\) with \(\sum_k x_{j,i,k}\leq\mu_{j,i}\) and \(\sum_{j,i,k}x_{j,i,k}\leq\beta\) such that \(P^\star\) receives at least \(\ell\) seats? After transfer, party \(i\) is eligible in every district if its total mass is at least \(\theta\); its support in district \(j\) is then its post-transfer mass there, or zero if it is ineligible. Apply \(R\) separately in each district using the paper’s tie-breaking rule.
Types are district–party pairs \((j,i)\) carrying rational mass \(\mu_{j,i}\). The decision variables \(x_{j,i,k}\) move voter mass from party \(i\) to party \(k\) within district \(j\), at unit cost per mass transferred; the total cost is \(\sum_{j,i,k}x_{j,i,k}\). The threshold is a population share \(\theta\), while district seat counts and the target \(\ell\) remain integral.
The mirror covers Theorem 2’s regular thresholded target-seat bribery for divisor-sequence methods and LRM, with unrestricted within-district vote changes. It leaves the winner model, district-limit results, parameterized results, and domain restrictions unmirrored.
The strongest anchor is Theorem 2, proved in this paper by a reduction from X3C: for every divisor-sequence method and for the largest-remainder method, R-THRESHOLD-MAB is NP-complete. This is the regular bribery problem in a multidistrict election with a general electoral threshold: given district seat counts, a distinguished party, a target of at least \(\ell\) total seats, and a budget \(K\), can votes be changed within the districts, without moving voters between districts, so the party gets at least \(\ell\) seats? The apportionment method is applied separately in each district, while the threshold depends on a party’s total votes across the election. The result covers unrestricted vote changes and is established here; the paper contrasts it with the polynomial-time result for the no-threshold problem cited from Bredereck et al. [9].
A natural mirror keeps that problem intact while making the electorate a distribution. Take a fixed set of districts and parties. A type is a district–party pair \((j,i)\): it describes a voter’s district and current vote, which are the features the paper’s cost model uses. Let \(\mu_{j,i}\) be the fraction of the whole electorate in that type, with \(\sum_{j,i}\mu_{j,i}=1\). Parties that do not run in a district are excluded from that district’s types and possible transfers. The regime is a large election with many voters but a modest number of positive-mass district–party types—for example, a parliamentary electorate with millions of voters represented by polling shares across districts and parties. The paper itself motivates campaign planning and post-election auditing as applications of its model.
For a discrete election of \(N\) voters, normalize the threshold and budget to shares: \(\theta=\tau/N\) and \(\beta=K/N\). A continuous instance gives rational initial masses \(\mu_{j,i}\), rational \(\theta,\beta\), district seat counts, the distinguished party \(P^\star\), a target \(\ell\), and an apportionment method \(R\). A proposed action is a rational mass transfer \(x_{j,i,k}\geq 0\), moving voters from party \(i\) to party \(k\) within district \(j\). Transfers out of a type cannot exceed its initial mass; each district’s total mass stays fixed. The action’s cost is \(\sum_{j,i,k}x_{j,i,k}\), which must be at most \(\beta\).
After the transfer, party \(i\)’s total mass determines threshold eligibility: if it is at least \(\theta\), its support in district \(j\) is its post-transfer mass there; otherwise its support is zero in every district. Apply \(R\), with the paper’s tie-breaking rule, to each district’s supports. The continuous decision question is whether there exists a feasible transfer \(x\) for which \(P^\star\) receives at least \(\ell\) seats in total. A transfer satisfying these conditions is a solution. Seats remain integral; the continuous object is the electorate and the bribery action.
This is a strong mirror because it retains the paper’s central interaction: vote changes in one district can change a party’s threshold eligibility and thereby affect seat allocation across all districts. The mirror does not depend on fractional seats or on changing the paper’s party-level voting model. I would expect the question to be continuum-specifically hard, though Theorem 2 does not establish that. Threshold eligibility is still a discrete switch in a mass model, and the target is still an integer seat total; together they leave room for combinatorial difficulty.
The key caveat is that the paper’s X3C reduction may not carry over. Its construction uses parties at the threshold and relies on exact vote transfers: in the reverse direction, each of \(3n\) element parties must lose exactly one vote. In the continuous model, an arbitrarily small transfer can push a party below threshold. That can erase the reduction’s exact-cover constraint. So this is a genuine computational question for the programme, not a claim that the paper’s NP-hardness survives continuization. Further questions include whether the minimum successful bribery mass is efficiently computable, how district-specific mass caps affect complexity, and whether similar mirrors for the winner model remain hard.
The mirror covers Theorem 2’s regular, thresholded problem. I would keep that as the sole anchor: it is the paper’s direct threshold-hardness result and supports a precise continuous question. The weakest point is the gap between its integral reduction and the fractional transfers here; a prover would need a new hardness argument or an algorithm exploiting that gap.
The strongest case against the proponent’s anchor is that Theorem 2’s reduction depends on indivisible votes: moving exactly three votes can make a party eligible, while removing exactly one vote from each element party pushes it below the threshold. In a mass-transfer version, those exact-cover gadgets can dissolve: a briber may split transfers and move an arbitrarily small amount across a threshold. So the paper’s hardness result does not itself establish what the continuous question would capture.
But that does not defeat the best mirror. Keep districts and parties fixed, represent each district–party pair by a voter type, normalize the threshold and budget by total electorate, and allow rational mass transfers within each district. A party’s total mass still controls its eligibility everywhere; the apportionment rules still allocate integral seats within districts; and the target remains whether the distinguished party gets at least \(\ell\) seats. Those choices follow the paper’s model closely. Large elections with many voters sharing a modest number of district and party choices make this a sensible high-multiplicity regime.
One can argue that this leaves a finite-dimensional optimization problem with threshold and seat-allocation decisions, rather than exposing the kind of continuous structure that might yield an LP algorithm. But that is a prediction about the tools or answer, not a reason the computational question is unworthy. The programme explicitly includes cases where continuization does not help.
So I cannot honestly defeat this anchor. The reduction’s loss of indivisibility weakens any claim that the continuous problem inherits Theorem 2’s hardness, but it leaves a well-posed and natural computational mirror. The negative case here 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.