| paper | d4-conf-aaai-2015-0570 |
| 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}\text{-complete}\), even with positive dyadic rational masses · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), target \(c\in C\), and binary-rational distribution \(\mu\) over a finite support of complete voter rankings, with strict pairwise majorities, let \(R_\mu^M\) be the induced majority relation. Is there a narcissistic candidate preference profile, an agenda, and a candidate entry-equilibrium strategy profile such that voters use the paper's sophisticated VSE refinement of \(R_\mu^M\) and the resulting outcome is \(c\)?
The society is a distribution \(\mu\) over complete voter-ranking types. It induces the strict majority relation \(R_\mu^M\); candidate decisions determine the running set, and the decision asks whether some candidate preferences, agenda, and entry equilibrium yield target \(c\) under sophisticated VSE voting. There is no optimization objective.
In a literal nonatomic game, individual voters cannot pivot, so sophisticated behavior is imposed as a refinement of the mass-induced majority relation rather than selected by individual incentives; the proponent identifies this interpretive limit.
fatal: False
Covers Theorem 3's candidate-stable-set membership problem; it leaves the single-peaked results in Theorem 1, Theorem 2, and Corollary 1 outside this mirror.
The strongest mirror is the paper’s hardness result for strategic candidacy under voting by successive elimination (VSE). A plausible high-multiplicity setting is a large membership organization choosing an endorsement from a small slate of candidates through sequential pairwise votes. Many members may share the same complete ranking, so the society is naturally described by voter types \(t\in L(C)\) and rational masses \(\mu_t\), with \(\tau\ll n\). Candidates remain finitely many strategic entrants. The agenda and possible candidate withdrawals are part of the process being studied.
The anchor is Theorem 3, proved in this paper: “Computing the candidate stable set is NP-complete.” In its explicit decision form, the result says that, given a voter preference profile \(R\) and candidate \(c\), deciding whether \(c\in CS(R_M)\) is NP-complete. Here \(R_M\) is the voters’ strict majority relation, and \(CS(R_M)\) is the set of candidates that can be sophisticated outcomes for some candidate preferences and some elimination order, in an entry equilibrium. The paper’s proof adapts a construction used for Banks-set hardness.
Continuous candidate-stable-set membership. An instance consists of a finite candidate set \(C\), a target \(c\in C\), and a binary-encoded rational distribution \(\mu\) over voter rankings, given by its \(\tau\) positive-mass types. Require strict pairwise majorities: for every distinct \(a,b\in C\),
\[
\sum_{t:\,a\succ_t b}\mu_t\ne \tfrac12.
\]
Define \(a\succ_\mu^M b\) when that sum is greater than \(\tfrac12\). For each narcissistic candidate preference profile, elimination order, and candidate run/not-run profile, use VSE with voters following the paper’s sophisticated, backward-induction behavior. The run profile is an entry equilibrium when no candidate can improve their outcome by changing their own decision to run. The question is whether some such preferences, order, and entry equilibrium yield outcome \(c\). A yes-instance has those choices as its witness; the decision is membership in the resulting continuous candidate-stable set. There is no cost-minimization objective in the paper’s problem.
This is a close analogue of the paper’s question: it retains strategic candidacy, successive elimination, sophisticated voting, and the existential equilibrium-outcome set. The society itself is now the distribution over complete voter types. The majority relation is computed exactly from masses, so each pairwise contest is well-defined without assigning any particular voter special status.
I expect hardness to transfer. A discrete profile with \(n_t\) voters of ranking \(t\) maps to \(\mu_t=n_t/n\), preserving every pairwise majority and hence the candidate stable set. Thus the paper’s reduction supplies hard continuous instances too; the combinatorics lie in the majority relation, candidate entry, and elimination orders, rather than in the number of individual voters. In the sparse encoding, the instance is described by \(m\), \(\tau\), and the bit lengths of the masses; this argument establishes NP-hardness for that encoding, without claiming hardness for every restriction on \(\tau\). Natural next questions include whether bounded candidate counts or restricted majority relations make membership tractable, and whether the full set can be computed efficiently under such restrictions.
This case covers Theorem 3’s VSE candidate-stable-set problem; it does not claim a continuous mirror for the paper’s separate single-peaked results. Its weakest point is the interpretation of sophisticated voting in a literal nonatomic society: an individual voter has zero influence on a majority outcome. The mirror therefore takes sophisticated behavior as the same backward-induction refinement applied to the majority outcomes induced by \(\mu\), with members of each type following the resulting type-contingent ballot strategy. That preserves the paper’s aggregate outcome question, but makes the refinement—not Nash incentives of individual infinitesimal voters—the part authors and a referee would need to accept.
Theorem 3 is the anchor I cannot honestly defeat. For any odd finite electorate, group voters by ranking and replace each count \(n_t\) with mass \(\mu_t=n_t/n\). This preserves every strict pairwise majority, hence the majority relation \(R_M\) and the candidate stable set. The paper’s hardness reduction therefore gives NP-hard instances in the rational-mass encoding too. And because the candidate stable set depends only on \(R_M\), the distribution is a legitimate population input even though its details beyond those pairwise comparisons are discarded.
The strongest objection is about meaning: in a nonatomic society, no individual voter can change a pairwise majority, so individual strategic incentives do not select the paper’s sophisticated behavior. A better-defined mirror can still ask for membership in the candidate stable set induced by \(\mu\)’s strict majority relation, using the paper’s characterization. That is an aggregate refinement of the tournament, rather than a Nash outcome derived from infinitesimal voters’ incentives. But the paper itself defines its result through the majority relation, so this looks like a question its authors could recognize. The missing individual incentive does not make the computational question ill-posed.
The mirror may offer little new machinery: it factors through a finite majority relation, and its hardness appears to transfer directly. Under the programme’s stated standard, though, that is not enough to reject it. A continuous input whose computational properties are already determined by a compact aggregate can still be a worthwhile mirror. My negative case is therefore weak; Theorem 3 survives.
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.