| paper | d4-conf-ijcai-2015-0363 |
| 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: Both \(\mathrm{WINNER1}\) and \(\mathrm{WINNER0}\) are \(\mathrm{NP}\)-hard, even with all candidates initially running and no initial blocks. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
Given a finite candidate set \(C\), candidate preferences, a fixed tie-breaking order, voter ranking types \(T\) with positive rational masses \(\mu_t\) summing to \(1\), an initial state, and a designated candidate \(c^\star\), does there exist a finite sequence of single-candidate improving moves that reaches an equilibrium where \(c^\star\) wins? For WINNER1, when a candidate withdraws, every type blocks that candidate; each type votes for its highest-ranked running candidate not blocked, or its highest-ranked running candidate if all running candidates are blocked. For WINNER0, no candidates are blocked. Initial refusal histories can be represented by splitting types that share a ranking but have different histories.
A distribution over complete voter types carrying rational mass, with Plurality scores computed from type-level ballots and a finite set of strategic candidates. Candidate actions and preferences remain as in the paper; in WINNER1, type-level blocked sets record refusal history and update deterministically on withdrawal.
The mirror covers WINNER1 in Theorem 2 and WINNER0 in Theorem 3. It leaves aside Theorem 1’s stochastic convergence result, SET reachability, and Theorem 4’s static existence problem.
The cleanest mirror is the paper’s Plurality WINNER problem with a continuous voter population. It leaves the strategic candidate set finite and makes the voters the continuous object. That fits a plausible regime: a large online contest with a fixed slate of entrants, where many viewers share one of a small number of rankings over the entrants. The viewers are the population; the entrants remain individual strategic players. The relevant scale is many viewers \(N\), but relatively few ranking types \(\tau\).
For the mirror, an instance gives a finite candidate set \(C\), each candidate’s strict preference order over possible winners, a fixed tie-breaking rule, and a support \(T\subseteq L(C)\) of voter-ranking types. Each type \(t\) has positive rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Mass means the fraction of the audience with that ranking. For a running set \(A\), each type’s mass votes for its highest-ranked eligible candidate, and the weighted Plurality scores determine the winner. A candidate’s action is to enter or withdraw; a move is improving when it changes the winner to one that candidate prefers. A solution is a finite sequence of such single-candidate improving moves ending at an equilibrium with a designated winner.
The lead anchor is Theorem 2, proved in this paper: WINNER1 is NP-complete. WINNER1 asks whether, given a candidacy game, an initial state, and a designated candidate, there is an improvement path to an equilibrium in which that candidate wins, when every voter blocks a candidate after that candidate withdraws (\(p_v=1\) for all voters). The paper’s reduction is from X3C, and its hardness holds even from the truthful initial state in which all candidates run.
Its continuous counterpart, Continuous-WINNER1, has the same question over the rational type masses just described. The initial state includes the running set and, if voters have already blocked candidates, the blocked sets for each type. When a candidate withdraws, every type adds that candidate to its blocked set, as every individual voter would at \(p_v=1\). In a state \((A,(B_t)_{t\in T})\), type \(t\) votes for its highest-ranked candidate in \(A\setminus B_t\), or, if that set is empty, its highest-ranked candidate in \(A\). The question is whether an improving path reaches an equilibrium where \(c^\star\) wins. The reduction’s all-running, no-blocks starting state remains a hard special case.
The expected classification is Class B: hardness transfers. A discrete profile with \(n_t\) voters of type \(t\) maps to \(\mu_t=n_t/N\), where \(N=\sum_t n_t\). Dividing every Plurality tally by \(N\) preserves every winner, candidate move, and equilibrium along the path. The paper’s X3C instances therefore give hardness for the continuous problem. Its NP membership argument also carries over: a witnessing path has polynomial length in the candidate count, and comparisons of rational weighted tallies take polynomial time in their bit length. Thus Continuous-WINNER1 should be NP-complete. A further question is whether useful tractability emerges under restrictions on the number or structure of voter-ranking types, even though the unrestricted hardness remains.
A second, distinct anchor is Theorem 3, also proved in this paper: WINNER0 is NP-hard. It asks the same designated-winner reachability question when voters never block withdrawn candidates (\(p_v=0\) for all voters). The paper proves hardness by reducing from RX3C; the reduction again works from the truthful all-candidates-running state. The theorem states NP-hardness, not NP-completeness.
Continuous-WINNER0 uses the same rational type-mass input, but has no blocked-candidate sets: every type always votes for its highest-ranked running candidate. Its question is whether an improvement path from the given initial running set reaches an equilibrium where \(c^\star\) wins. The RX3C reduction transfers by the same normalization of voter counts, so I expect Class B hardness, at least NP-hardness. Since the \(p=0\) state is just a subset of candidates, explicit state-graph search gives a \(2^{|C|}\operatorname{poly}(\tau,L)\) upper bound; the exact complexity and whether the problem is in NP are natural further questions.
These are recognizable as the paper’s problems because the continuous versions preserve its strategic actors, Plurality rule, candidate preferences, one-at-a-time improving moves, and equilibrium-reachability objective. Only the voter population becomes a distribution over the same complete preference types. A plausible instance regime is a contest with a very large audience and a small number of recurring preference groups, each with a stable ranking of the contestants. The mass representation then expresses audience shares directly. It does not turn the contestants into types or make their strategic choices fractional.
The scope here is deliberately limited to Theorems 2 and 3: the two WINNER reachability results at the extreme refusal probabilities. It does not mirror the probabilistic convergence result for \(p_v>0\), the SET problems, or the static \(\exists\)WINNER problem.
My weakest point is that this mirror does not promise a new optimization method or a tractability gain. The hardness reductions’ combinatorics live in candidates and their strategic choices, so replacing voter counts by exact rational shares preserves the hard part. A referee might regard the continuous formulation as weighted Plurality reachability with a new interpretation. That is a real limitation, but it does not make the question ill-posed: it is an exact high-multiplicity version of the paper’s problem, and it gives a clear boundary case where continuization does not dissolve the hardness.
I cannot make a convincing case that either anchor lacks a worthwhile continuous mirror. The strongest objection I can offer is a project-prioritization concern: in both problems, the strategic choices belong to the finite set of candidates, while voter masses only determine Plurality scores. That makes the mirrors look like high-multiplicity versions of the original reachability problems. But under the programme’s stated criteria, that is not a decisive objection.
For Theorem 2 / WINNER1, the continuous version is coherent even with the refusal history included. From the truthful all-running start, voters of the same ranking type acquire the same blocked-candidate set: when \(p_v=1\), every voter blocks each candidate who withdraws. If type \(t\) has \(n_t\) voters among \(N\), set \(\mu_t=n_t/N\). At every running set and blocked-set state, each continuous Plurality score is the discrete score divided by \(N\). Winners, including lexicographic ties, therefore agree; so do candidate incentives and the reachable-equilibrium question. A stronger mirror could ask which outcomes persist for arbitrary rational type masses, and how complexity depends on \(m,\tau,L\). The paper’s reduction transferring to that mirror would be a result, not a reason to dismiss the question.
For Theorem 3 / WINNER0, there is no blocking history to aggregate. The same conversion \(\mu_t=n_t/N\) preserves every winner and improving move along every path. Arbitrary rational masses also give a legitimate weighted electorate, and make it possible to ask whether the problem changes with the number or structure of ranking types. The fact that candidate states are finite, or that a direct search has an exponential state-space bound, does not make the continuous question ill-posed.
The best negative pressure is that these mirrors may yield a limited continuization story: the candidate-side dynamics stay discrete, and the basic conversion preserves the original reachability graph. That could make them less promising if the goal were specifically to find a tractable continuous algorithm. But this programme also values Class B results and a formal high-multiplicity bridge. The concern therefore cannot defeat either anchor on the grounds allowed here.
I’d grade the negative case as weak. A large electorate with a relatively small support of ballot types is a sensible regime for both reachability questions, and the paper’s candidate identities and strategic choices do not prevent the voters from forming a continuous population. The exact discrete-to-rational-mass correspondence is the strongest argument against novelty, but it is not an honest argument that no worthwhile mirror exists.
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.