| paper | d4-conf-aaai-2026-4688 |
| 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: Equilibrium Existence and Equilibrium President are both \(\mathrm{NP}\)-hard, with polynomial-time certificate verification on the promised domain. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5 (⋆)
statement extracted from the paper’s text layer
Given candidates partitioned into parties and a finite support \(T\) of strict rankings with positive binary-rational masses \(\mu_t\) summing to \(1\), promised to admit a common 1-D Euclidean representation, is there a tuple choosing one nominee per party such that each type’s mass votes for its favorite nominee under Plurality and no party can improve from losing to winning by switching nominees? For the target-party version, also require a designated party to win in that equilibrium; ties count as winning, as in the paper.
The finite strategic players remain the parties, with the same nominee choices and winner-based utilities. The voter population is a distribution \(\mu\) over ranking types; each type’s mass votes as one bloc for its favorite nominee, producing rational Plurality scores. The decision variable is a nomination tuple, and the question is existence of a pure Nash equilibrium, optionally with a designated winner. This preserves the paper’s solution concept rather than replacing it with a nonatomic-player equilibrium.
Covers Theorem 5’s NP-hardness results for EQUILIBRIUM EXISTENCE and EQUILIBRIUM PRESIDENT on 1-D Euclidean profiles. It leaves the paper’s recognition, existence-guarantee, and polynomial-time results aside.
The strongest mirror is the parties’ nomination game itself, with voter counts replaced by voter mass. Mass-Weighted Euclidean Equilibrium Nomination (MWEN) has as input a finite candidate set \(C\), partitioned into parties, and a finite support \(T\) of strict rankings of all candidates. Each type \(t\) has a positive binary rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). The input is promised to be \(1\)-D Euclidean: there are common candidate positions \(x(c)\) and, for each type, an ideal point \(z_t\) such that \(a\succ_t b\) exactly when \(|z_t-x(a)|<|z_t-x(b)|\). The support size is \(\tau=|T|\).
Each party chooses one of its candidates. A type casts its mass for its favorite nominee, so a nominee’s Plurality score is the sum of the masses voting for it. Tied top scorers are winners, just as in the paper. The question is whether there is a nomination tuple that is a pure Nash equilibrium under the paper’s utilities: a party gets utility \(1\) if its nominee wins and \(0\) otherwise, and no party can switch nominees and improve its utility. An optional target-party input asks whether such an equilibrium exists with that party winning. A yes-instance can be certified by the nomination tuple; the scores and every unilateral deviation can be checked using exact rational arithmetic. This is a decision problem, not an optimization problem.
The regime is a large election in which parties choose among a modest slate of nominees and voters’ rankings are induced by positions on a shared ideological line. Millions of voters can be grouped by ranking, so the population size \(N\) can greatly exceed \(\tau\). With fixed candidate positions, voter rankings can change only at pairwise distance-equality points, giving at most \(\binom{|C|}{2}+1\) strict ranking regions. Thus many voters can share relatively few types. The type is exactly the information this game uses: the complete ranking. The parties’ actions, Plurality rule, winner-based utility, and equilibrium notion stay intact; only the society is represented by its distribution over types. That is a plausible high-multiplicity version of the authors’ problem, not a different strategic question.
My anchor is Theorem 5 (⋆). It states that EQUILIBRIUM EXISTENCE and EQUILIBRIUM PRESIDENT are NP-hard for \(1\)-D Euclidean preferences, and therefore also for single-peaked preferences. This is the authors’ result, but its proof is deferred in this paper to their cited 2025 full version; it is not attributed here to earlier work. MWEN’s no-target and target-party modes mirror those two problems. My lead is the no-target equilibrium-existence question.
I expect MWEN to be Class B: hardness transfers. Given a finite electorate with \(n_t\) voters of each ranking type, set \(\mu_t=n_t/n\). Every candidate’s mass score is its original vote count divided by \(n\), so winners, ties, and every party’s possible profitable deviation are unchanged. The Euclidean promise is preserved as well. Thus the discrete hard instances embed directly in the mass problem; on promised inputs, a nomination tuple is a polynomial-size witness, so the decision version is also in NP. This gives a clean hardness result for the continuous formulation, though it does not by itself show hardness when \(\tau\) is fixed or very small.
My weakest point is precisely that limitation: Theorem 5 does not tell us whether its hard instances have a small number of distinct types relative to the candidate set, or whether the continuous problem becomes tractable in a low-support regime. The paper’s Theorem 6 raises a related follow-up rather than a second anchor: it gives polynomial-time algorithms for EQUILIBRIUM EXISTENCE and EQUILIBRIUM PRESIDENT on party-aligned single-peaked profiles, but its dynamic program ranges over integer vote scores. Does that tractability extend to binary rational masses in time polynomial in \(m,\tau,L\), or does exact weighted scoring change the complexity? My case covers Theorem 5’s Euclidean hardness results; it does not claim to mirror the paper’s equilibrium-existence guarantees, recognition result, or all of its tractability results.
The strongest negative case is that Theorem 5’s hardness may be carried by the parties’ finite nomination choices, with the electorate serving only to supply vote totals. In a mass model, a ranking type casts all its mass for the same nominee, so each score and every deviation can be checked by summing rational masses. The continuum adds no new strategic actors or actions.
But that does not defeat the mirror. It identifies a natural weighted version of the same electorate, and the paper’s discrete hard instances embed directly: replace each ballot type’s count \(n_t\) among \(n\) voters with mass \(n_t/n\). This preserves scores up to a common scale, hence winners and profitable deviations. That makes the equilibrium-existence mirror a credible Class B question, even if the hardness is not caused by population multiplicity. The paper states Theorem 5’s Euclidean hardness and defines equilibrium by winner status under unilateral nomination changes. [Paper text](https://wrap.warwick.ac.uk/id/eprint/194732/1/Possible_President_SP_and_Equilibria-2.pdf)
A stronger formulation would put a probability distribution directly over voters’ ideal points on the line. Since nominations depend only on rankings, one can aggregate the mass of each ranking region into a type mass; with rational masses, equilibrium and deviations remain exactly checkable. The possibility that this formulation yields the same answer as the finite case is not a reason to reject it under ChoCo’s standard. Nor do adjacent continuous spatial models settle the issue: they study candidate location choices and equilibrium structure, rather than complexity for mass-weighted electorates with finite nominee slates. [Hotelling–Downs framework](https://ora.ox.ac.uk/objects/uuid%3Af04c1912-1199-486c-b5ff-9439fc4697b5)
I therefore cannot honestly defeat the proponent’s anchor. The only material limitation is that Theorem 5, as presented here, does not establish how complexity behaves at fixed or very small support size. That is a worthwhile parameterized follow-up, not a reason the mirror lacks value. The case against 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.