d4-conf-aaai-2026-4688 (d4-conf-aaai-2026-4688)

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.

Let \(C\) contain \(m\geq 1\) candidates, partitioned into \(k\geq 1\) nonempty parties \(P_1,\ldots,P_k\).
A society is given by its support: a list \(T\) of \(\tau\) distinct strict rankings of \(C\), each with a positive binary-rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings.
The rankings are promised to admit a common one-dimensional Euclidean representation; a representation is not supplied, and parties need not occupy contiguous positions.
A nomination tuple \(\mathbf c=(c_1,\ldots,c_k)\) chooses \(c_i\in P_i\). Under Plurality, each type's entire mass votes for its favorite nominee. A nominee's score is its total supporting mass; every nominee attaining the maximum score wins, and its party wins.
A tuple is a pure Nash equilibrium if no currently losing party can replace its nominee with another member of that party and become a winner in the resulting election. Scores are recomputed after a replacement; becoming a tied winner counts as becoming a winner.
Equilibrium Existence asks whether such a tuple exists. Equilibrium President additionally specifies a party \(P^\star\) and requires it to win in the equilibrium. Let \(L\) be the total binary input length; state running times in \(m,\tau,k,L\).

For each of Equilibrium Existence and Equilibrium President on this promised domain, is the rational-mass problem solvable in polynomial time in \(m,\tau,k,L\), or is it NP-hard?

For explicitly listed unit-weight voters, both problems are NP-hard even for one-dimensional Euclidean preferences, and therefore also for single-peaked preferences. Both discrete problems are polynomial-time solvable for party-aligned single-peaked preferences.
The supplied results give no separate classification for this rational-mass input formulation.

Both problems are \(\mathrm{NP}\)-hard. The supplied hardness results transfer by aggregating identical rankings and normalizing voter counts. This preserves every election outcome, including ties and outcomes after deviations.

Here, “binary-rational” means a rational number whose integer numerator and denominator are encoded in binary.

• Polynomial reduction from explicitly listed voters.

Take an instance of either supplied unit-weight problem with \(N\geq 1\) explicitly listed voters. Keep the candidates, parties, and, for Equilibrium President, the designated party unchanged.

Let \(T\) be the set of distinct rankings occurring in the voter list. For each \(t\in T\), let \(n_t\) denote its multiplicity and set \(\mu_t=n_t/N\). Then every mass is positive and \(\sum_{t\in T}\mu_t=1\).

The resulting support size satisfies \(\tau\leq N\). Each mass needs \(O(\log(N+1))\) bits for its numerator and denominator. If the source input has length \(L_0\), the output length is \(O(L_0+\tau\log(N+1))\), hence polynomial in \(L_0\). Sorting the rankings lexicographically and counting repetitions constructs the instance in polynomial time; a direct bit-complexity bound is \(O(L_0+Nm\log(N+1)\log(m+1))\).

The Euclidean promise is preserved. Indeed, take any common one-dimensional Euclidean representation of the source profile. Retain the candidate positions and one representative voter position for each distinct ranking. These positions represent every ranking in \(T\). The construction itself does not need to find that representation.

• Exact preservation of equilibria.

For any nomination tuple \(\mathbf c\), let \(V_i(\mathbf c)\) be the number of source voters whose favorite nominee is \(c_i\), and let \(S_i(\mathbf c)\) be that nominee’s score in the constructed instance. Aggregation gives
\[ S_i(\mathbf c)=\sum_{\substack{t\in T\\c_i\text{ is }t\text{’s favorite nominee}}}\frac{n_t}{N} =\frac{V_i(\mathbf c)}{N}. \]

Consequently, for every pair of parties \(i,j\), the comparison between \(S_i(\mathbf c)\) and \(S_j(\mathbf c)\) is exactly the comparison between \(V_i(\mathbf c)\) and \(V_j(\mathbf c)\). Thus the winning parties, including all tied winners, coincide.

This identity holds for every nomination tuple, so it also holds after every unilateral replacement. A party is currently losing in one instance exactly when it is losing in the other, and its replacement makes it a winner in one exactly when it does so in the other. Therefore the two instances have precisely the same equilibrium tuples and the same winning parties at each equilibrium.

Applying the supplied Euclidean hardness theorem separately to each source problem proves that both rational-mass problems are \(\mathrm{NP}\)-hard.

• Polynomial verification and running times.

A nomination tuple is a certificate of length \(O(k\log(m+1))\). It can be checked exactly in polynomial time without constructing a Euclidean representation.

Write each input mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive binary integers. Set \(D=\prod_{t\in T}b_t\) and \(w_t=a_t(D/b_t)\). Then \(w_t\) is an integer and \(\sum_t w_t=D\). The bit length of \(D\) is \(O(L)\), because the sum of the input denominator lengths is at most \(L\). Every integer election score lies between \(0\) and \(D\), so all comparisons use \(O(L)\)-bit integers.

Precompute each ranking’s candidate positions. For any tuple, scan its \(k\) nominees for each of the \(\tau\) types, identify that type’s favorite, and add \(w_t\) to its score. This takes \(O(\tau k+k)\) arithmetic operations.

First compute the current winning parties. For every currently losing party, check every alternative nominee by recomputing the election and testing whether that party’s score attains the new maximum. There are at most \(m\) such replacements. Accept exactly when none succeeds; for Equilibrium President, also require that \(P^\star\) wins initially.

Using elementary integer arithmetic, a conservative bound for this verifier is \(O((m\tau k+\tau+m+k)L^2)\) bit operations. Thus both problems have polynomial-time certificate verification on the promised domain. Exhaustively checking all tuples gives the deterministic bound \(O(m^k(m\tau k+\tau+m+k)L^2)\).

Hence the requested classification is \(\mathrm{NP}\)-hard for both problems. A polynomial-time algorithm in \(m,\tau,k,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The output resolves both assigned problems correctly: Equilibrium Existence and Equilibrium President are \(\mathrm{NP}\)-hard on the promised Euclidean domain. The reduction preserves every nomination tuple’s winning parties and every permitted deviation. No major or minor defects were found.

1. Input interpretation

The prover explicitly interprets “binary-rational” as a rational represented by a binary numerator and denominator. This is consistent with the task’s rational-mass formulation. The verification below uses that interpretation; a restriction to dyadic masses would be a different input specification.

2. Construction and encoding size

For each distinct source ranking \(t\), its multiplicity satisfies \(1\leq n_t\leq N\). Consequently, \(\mu_t=n_t/N\) is positive, has a binary encoding of length \(O(\log(N+1))\), and the masses sum to one.

The construction produces distinct support rankings and satisfies \(\tau\leq N\), as required. Because voters are explicitly listed in the source instance, \(N\) is bounded polynomially by the source input length. The claimed output-size bound is therefore polynomial.

The construction-time bound is also valid under an ordinary binary encoding of candidate identifiers: lexicographically comparing two rankings takes \(O(m\log(m+1))\) bit operations, and sorting takes \(O(N\log(N+1))\) comparisons. Reading the input and maintaining multiplicities fit within the stated bound.

3. Euclidean promise

The promise-preservation argument is sufficient. A common Euclidean representation of the original profile also represents the retained ranking types when one source voter position is retained for each distinct ranking.

The reduction does not need to compute those positions. It only needs to produce an instance satisfying the promise, which the existence argument establishes. No assumption about contiguous parties is introduced.

4. Election outcomes and deviations

For every nomination tuple and party \(i\), aggregation yields exactly
\[ S_i(\mathbf c)=V_i(\mathbf c)/N. \]
Since \(N>0\), this preserves all score inequalities and equalities. In particular, it preserves the entire set of maximum-score nominees, including tied winners.

The universal quantifier over nomination tuples is crucial and is correctly used: the same identity applies to every tuple obtained after a unilateral replacement. Thus both the condition of currently losing and the condition of becoming a winner are preserved.

It follows that equilibrium tuples coincide in the two instances. Their winning parties also coincide, so the designated-party requirement for Equilibrium President is preserved.

5. Hardness conclusion

The supplied unit-weight hardness results are the premises used here. The construction is a polynomial-time reduction from each supplied problem to its corresponding rational-mass problem, preserves the Euclidean promise, and preserves its yes/no answer.

Accordingly, both hardness conclusions follow. The prover does not need an additional hardness theorem beyond those supplied in the task.

6. Exact verification and running times

The integer conversion is valid: every denominator divides \(D=\prod_t b_t\), so every \(w_t=a_t(D/b_t)\) is an integer. Normalization gives \(\sum_t w_t=D\). The bit length of \(D\) is \(O(L)\), and all scores lie between zero and \(D\).

The election computation correctly scans the nominees in each strict ranking. The deviation verifier checks all alternatives of every currently losing party; there are at most \(m\) such alternatives. Testing whether the deviating party attains the recomputed maximum correctly includes tied victories.

The conservative bit-complexity bound covers preprocessing, integer arithmetic, election recomputation, and certificate checks. Precomputing ranking positions is also absorbed by that bound because the rankings are explicitly included in the input of length \(L\).

Finally, the number of nomination tuples is \(\prod_i |P_i|\leq m^k\), so the exhaustive-search bound is valid. The verification claim is appropriately limited to the promised domain and does not claim recognition of Euclidean profiles.

No repair or additional clarification is needed under the stated rational encoding.

⟨structured verdict parsed — rendered above⟩