| paper | d4-conf-ijcai-2015-0576 |
| 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: All six decision problems are \(\mathrm{NP}\)-complete, invoking the published finite-list hardness theorems. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), candidate preference orders, a priority order, and a finite support of voter rankings with binary-rational masses summing to \(1\), decide whether there is an active set \(A\subseteq C\) that is a pure Nash equilibrium under plurality by mass, the paper’s tie-breaking rule, and its laziness preference; in the winner-constrained variant, also require a specified candidate to win. For the dynamics variants, decide whether a legal sequence of joins from the empty set or withdrawals from \(C\) terminates at a specified active set or with a specified winner.
A finite set of strategic candidates faces a nonatomic electorate represented by a distribution \(\mu\) over complete rankings. For each active set, plurality scores are the masses of voters whose highest-ranked available candidate is each candidate; candidates retain their ordinal preferences and the paper’s laziness rule.
The mirror covers Theorems 1 and 2: equilibrium existence and the stated dynamics reachability problems. It leaves the structural propositions, normative comparisons, and proposed frequency analysis of random profiles outside its scope.
This paper has a particularly direct continuous-population mirror: keep the strategic candidates and their choices exactly as modeled, and replace the finite list of voters by a distribution over voter rankings. That makes the electorate continuous while preserving the game the candidates play.
A plausible regime is a large election with many voters but comparatively few distinct ballot types: for example, \(N\) voters whose complete rankings fall into \(\tau\) recurring categories, with \(N\) much larger than \(\tau\). A type is a ranking \(\rho\in L(C)\); its mass \(\mu_\rho\) is the fraction of the electorate with that ranking. Here ranking is a complete type description: voters vote sincerely, and the model gives them no other individual attributes. Candidates remain the finite strategic players, with the preferences and run-or-abstain choices from the paper.
For an active candidate set \(A\), define the plurality score by
\[
S_\mu(c,A)=\sum_{\rho:\,c\text{ is top-ranked in }\rho\text{ among }A}\mu_\rho.
\]
The winner is the candidate with the largest score, using the same fixed priority order \(\triangleleft\); when \(A=\varnothing\), the winner is \(c_\triangleleft\). Candidates keep their ordinal preferences over winners and the paper’s laziness rule: if their participation does not change the winner, they prefer to abstain. Thus the mirror changes the voters’ representation, while retaining the paper’s outcome rule and strategic question.
My lead anchor is Theorem 1, proved in this paper by a reduction from a restricted Exact 3-Cover problem. It says that both LAZY∃NE—whether a lazy strategic candidacy game has a pure Nash equilibrium—and LAZY∃WNE—whether it has a pure Nash equilibrium with a specified candidate as winner—are NP-complete, even when all candidates have self-supporting preferences.
The corresponding continuous problem, Continuous Lazy Equilibrium Existence, takes a finite candidate set \(C\), candidate preference orders, a priority order, and a finite support of rankings with nonnegative binary-rational masses summing to \(1\). It asks whether there is an active set \(A\subseteq C\) such that no candidate can profit by toggling their run-or-abstain action under the continuous game. Its winner-constrained version also takes a candidate \(c\) and asks whether such an \(A\) exists with \(w_\mu(A)=c\). An active set is a solution; in the constrained version its winner must be \(c\).
I expect both continuous variants to be NP-complete, with hardness transferring. If a discrete profile has \(n_\rho\) voters of ranking \(\rho\) among \(N\) voters, set \(\mu_\rho=n_\rho/N\). Then \(S_\mu(c,A)\) is the discrete plurality score divided by \(N\), so winners, ties, profitable deviations, and equilibria are identical. The discrete instances therefore embed exactly, with polynomial-size rational masses; a guessed active set can also be checked in polynomial time by computing each candidate’s possible deviation. The hard combinatorics in this result live in the candidate and ballot structure, rather than in a need to distinguish individual voters.
A second anchor is Theorem 2, also a result of this paper; its proof is omitted there and described as a modification of the construction for Theorem 1. It says that each of four decision problems is NP-complete: whether J-dynamics can converge to a specified state; whether W-dynamics can converge to a specified state; whether J-dynamics can converge to a state with a specified winner; and whether W-dynamics can converge to a state with a specified winner.
The matching Continuous Lazy Dynamics Reachability problem uses the same continuous-game input. J-dynamics starts with no candidates active; W-dynamics starts with all candidates active. At each step a candidate makes a beneficial join or withdrawal, respectively, and cannot reverse that move. The question is whether some legal sequence terminates at a specified active set, or— in the winner-constrained variant—at a state whose winner is a specified candidate. The path is the witness. Again I expect hardness to transfer: every discrete voter profile gives the same continuous game after normalization. A path has length at most \(m\), so it can be checked in polynomial time along with the terminal condition. This is a second Class B mirror: it asks about reachability under the paper’s dynamics, not merely the existence of an equilibrium.
Theorem 1 is the stronger anchor: it is the paper’s headline complexity result and includes its full reduction. Theorem 2 shows that the same population mirror covers a separate computational question about the paper’s two dynamics. Together, these mirrors cover the paper’s NP-completeness claims about equilibrium existence and dynamic reachability; they do not attempt to continuize every structural proposition. In particular, the paper’s suggested study of how often random preference profiles admit equilibria concerns a probability distribution over profiles, not a continuous population, so it is outside these questions.
The obvious follow-up questions are whether the continuous problems admit useful algorithms under restrictions on \(m\) or on the ranking support, and whether support structure yields tractability beyond simply enumerating the \(2^m\) candidate sets. For dynamics, one could also ask whether restrictions on the support make reachability easier. The paper’s results do not answer these continuous variants, although their discrete hardness transfers give a firm baseline.
My weakest point is that this is a clean mirror, but not a case where continuity is expected to dissolve the hardness. It inherits hard discrete instances exactly, and the strategic choices still belong to finitely many candidates. The case rests instead on a plausible high-multiplicity electorate and on the fact that the paper’s questions depend on voter rankings only through their aggregate plurality shares. The authors should recognize that as the continuous-population form of their problem, even though the expected answer is that these two questions remain hard.
The strongest objection is that both anchors leave the population’s role almost entirely as an input encoding. For any rational ballot distribution \(\mu\), choose a common denominator \(D\) and give the finite electorate \(D\mu_\rho\) voters of each ranking \(\rho\). For every active candidate set, each plurality score is then multiplied by \(D\). Winners, ties, profitable deviations, and equilibria are unchanged. The same holds for the transition graph in Theorem 2: the distribution determines which candidate moves are beneficial, but the states and moves are still finite candidate sets.
So the proposed versions of Theorem 1 and Theorem 2 do not introduce fractional voter actions or a new continuous strategic process. They ask the same questions about the same game, represented by rational ballot weights instead of a list of voters. Theorems 1 and 2 are genuine computational results, but their mirrors appear to be weighted or succinct-input variants of those results. That makes their fit to ChoCo’s continuous-optimization motivation thin: there is no mass-transfer decision or continuous optimization problem for the usual toolbox to act on.
This objection has a limit that matters. A common denominator for binary-rational masses can be exponentially large in the input bit length. Thus the weighted input can be substantially more concise than its finite-electorate expansion, and studying the resulting high-multiplicity complexity is a real computational question. The programme explicitly treats high-multiplicity work as support for a mirror, not a collision; I cannot turn the exact finite expansion into a valid objection merely by calling it equivalence.
Nor can I rule out a plausible regime: many voters with relatively few recurring complete rankings is sensible here, and voter rankings fully describe everything the model uses about voters. The fact that the strategic players are finitely many candidates does not erase that population. The case against both anchors is therefore a case about limited conceptual novelty and a narrower-than-usual computational payoff. It does not establish that either mirror is unworthy. A decisive negative verdict would overstate what the paper supports.
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.