| paper | d4-conf-ecai-2012-0201 |
| 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: Both constructive and destructive modes are \(\mathrm{NP}\)-hard, even when every allowed-ranking set is a singleton. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given candidates \(C\), chair order \(\sigma\), distinguished candidate \(d\), and \(q\) ordered cohorts with binary-rational masses \(\alpha_i>0\), \(\sum_i\alpha_i=1\), and allowed rankings \(\Omega_i\), each cohort's common ranking is revealed on arrival. Does there exist a policy that, after observing each current ranking, assigns mass \(x_i\in[0,\alpha_i]\) to the left side and the rest to the right, such that for every allowed future ranking sequence the ties-promote plurality partition runoff succeeds? In constructive mode, success means some runoff winner \(w\) satisfies \(w\succeq_\sigma d\); in destructive mode, it means no runoff winner \(w\) satisfies \(w\preceq_\sigma d\). All population mass votes in the runoff for its highest-ranked finalist.
A society is an ordered sequence of cohort types \((i,\pi_i)\), each carrying mass \(\alpha_i\), with rankings hidden until their cohort arrives. The chair chooses a fractional split \(x_i\) based on the revealed history; plurality winners from both sides advance under ties-promote, and the full mass votes among those finalists. The computational question is whether a policy guarantees the specified constructive or destructive outcome against every allowed future ranking sequence.
The model assumes a large homogeneous block's common ranking is revealed all at once, a narrower information regime whose typicality the proposed platform example does not establish.
fatal: False
Covers Theorem 9's constructive and destructive online plurality partition hardness results; leaves Theorems 1–8 and the paper's other election systems and control actions aside.
The strongest anchor is Theorem 9, proved in this paper: for plurality with ties-promote, online constructive control by partition of voters and online destructive control by partition of voters are both coNP-hard. The chair sees each voter’s ranking as it arrives, assigns that voter to one of two first-round elections, and must ensure the relevant outcome against every possible future sequence of votes. The paper proves the result by reducing from the complement of Hitting Set.
A continuous analogue I would put to the authors is Continuous Online Plurality Partition Control. Its instance has candidates \(C\), a chair ranking \(\sigma\), a distinguished candidate \(d\), and an ordered schedule of \(q\) arriving cohorts. Cohort \(i\) has rational mass \(\alpha_i>0\), with \(\sum_i\alpha_i=1\). Its members share a complete ranking \(\pi_i\); the cohort’s ranking is revealed when it arrives. The chair knows the schedule and the possible rankings, but not future cohorts’ rankings. Past cohort assignments are fixed, and the current ranking is known.
On seeing cohort \(i\), the chair chooses \(x_i\in[0,\alpha_i]\) mass for the left election and assigns the remaining \(\alpha_i-x_i\) mass to the right. This is the continuous version of assigning each arriving voter to one side: within a large group of indistinguishable voters, any aggregate split is possible. At the end, each side’s plurality winners advance under ties-promote. All population mass then votes in the runoff for its highest-ranked candidate among those finalists. The question is whether a policy, based only on rankings revealed so far, guarantees success against every allowed future sequence. In constructive mode, success means the runoff has a winner \(w\) with \(w\succeq_\sigma d\); in destructive mode, it means no runoff winner satisfies \(d\succeq_\sigma w\). A solution is such a winning contingent policy, specifying the mass split at each history. The input masses are binary rationals; natural complexity measures include \(m=|C|\), \(q\), the number \(\tau\) of relevant ranking types, and the input bit length \(L\).
This seems recognizably like the paper’s problem: the online information, partition action, plurality rule, tie handling, and adversarial guarantee all remain. A plausible high-multiplicity setting is a large participatory platform that receives rankings over proposals in a known sequence and routes them into two preliminary tallies before a shared runoff. Millions of participants may fall into relatively few operationally identical groups—same ranking, arrival cohort, and assignment options—so a mass split represents assigning the corresponding fraction of each group. The type should include any cohort feature that affects the chair’s options or information; for a small number of large cohorts, the number of types can still be modest relative to the population.
My expectation is Class B: hardness transfers, though that is a conjecture about this continuous problem, not a consequence already proved by Theorem 9. The theorem’s reduction encodes Hitting Set using the candidate agenda and the patterns of rankings: the difficulty is not simply that the electorate contains many separately named voters. That makes the underlying computational question a good candidate for the programme’s hardness-transfer story.
The soft spot is substantial: fractional assignments may change which candidates reach the runoff, and therefore may defeat the reduction’s discrete logic. The theorem’s construction also uses many gadget candidates and ballot patterns; it does not establish hardness in a low-\(\tau\), high-multiplicity regime. A referee could reasonably ask whether this is the same problem with population mass replacing counts, or a changed game whose fractional actions dissolve the hardness. That objection does not erase the mirror—the mass-partition question is precise and the online structure is preserved—but it means the reduction must be rebuilt or shown robust to fractional splits.
The immediate questions are whether the continuous version remains coNP-hard when arbitrary fractional splits are allowed, whether it becomes tractable for fixed \(m\) or restricted \(\tau\), and whether its finite discrete instances converge to the mass game as cohort sizes grow. The scope here is just Theorem 9’s online plurality partition result; I would not stretch the case to cover the paper’s other control types or its results for specially constructed election systems.
Theorem 9 is the one real anchor: it proves coNP-hardness for online plurality control by partitioning voters, in both constructive and destructive variants. The strongest mirror is the proposed cohort game, where each arriving block has positive rational mass, its shared ranking is revealed, and the chair splits that mass between the two elections. That is a precise computational question, and fractional splits are a natural mass version of partitioning.
The difficulty is that the paper’s computational object is not just a population of rankings. It is a sequence of decision points: the chair sees one vote, acts, and faces a particular set of possible future votes. A voter’s position in that sequence affects the information available when the chair acts. So a type that records only ranking forgets relevant information; a complete type must also record position. In the literal model, positions are individual slots, which leaves little high multiplicity to exploit.
Cohorts offer a way out, but they require a substantive restriction on the online process: many consecutive voters must share a ranking, and the chair must know that block structure when making decisions. Then a single revelation can determine the ballots of a large mass, which lets the chair choose a fractional split for the block. In ordinary sequential voting, repeated rankings are usually not known to arrive as a block. Grouping voters by ranking after their ballots arrive cannot recover the earlier decisions; grouping them by time window preserves the arrival structure but generally leaves many different rankings and decisions inside the window.
That leaves a recognisable follow-up for settings with genuine large, homogeneous delegations that arrive in rounds. But its input is an ordered sequence of hidden cohort rankings, rather than the paper’s sequence of individual unknown votes or the programme’s static distribution over types. The mirror needs a new assumption about how information is revealed, and its plausible applications seem narrow. I would therefore argue that Theorem 9 does not yet provide a compelling continuous mirror for the programme. The negative case is not airtight: a platform that routes large, homogeneous blocs through preliminary elections could make the cohort question sensible, and the authors might recognise it. The objection is that this rescue depends on a specialised arrival regime, not that a continuous version is impossible or that its answer would be uninteresting.
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.