d4-conf-atal-2017-0263 (d4-conf-atal-2017-0263)

Given \(m\) candidates, rational ideal points \(q_t\) with positive rational masses \(\mu_t\) summing to \(1\), fixed positions of all candidates except \(c\), a rational interval \(I_c\), a fixed rational positional scoring rule, and \(c\)'s preference order over winners, compute exactly the set \(BR_c=\{x\in I_c: W(x)\succeq_c W(y)\text{ for every }y\in I_c\}\). Each type ranks candidates by distance from \(q_t\), ties are resolved by the fixed lexicographic order, scores are weighted by \(\mu_t\), and election ties are resolved by that same order; represent \(BR_c\) as intervals and individual breakpoint positions.

Let \(C\) contain \(m\geq 1\) candidates, with distinguished candidate \(c\). A society is given by its support: \(\tau\geq 1\) distinct rational ideal points \(q_t\in\mathbb{Q}\), each with positive binary rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
All candidates participate. Each \(d\neq c\) has a fixed rational position; \(c\) may choose any real position in the nonempty closed interval \(I_c=[a,b]\), with rational endpoints \(a\leq b\). Withdrawal is unavailable.
Use a fixed rational positional scoring vector, written from first to last place as \(\alpha_1\geq\cdots\geq\alpha_m=0\); the zero vector is allowed. Each type ranks candidates by increasing distance from its ideal point, breaking equal distances by a supplied strict lexicographic order. Scores are weighted by \(\mu_t\), and the same lexicographic order resolves election ties; denote the winner at position \(x\) by \(W(x)\).
Candidate \(c\) has a supplied strict preference order \(\succ_c\) over \(C\), with \(c\) ranked first; \(\succeq_c\) is its reflexive closure. Define \(BR_c=\{x\in I_c: W(x)\succeq_c W(y)\text{ for every }y\in I_c\}\). Represent this set exactly by finitely many intervals with rational endpoints and explicit endpoint inclusion, together with isolated rational positions. Let \(L\) be the total binary input length, including the scoring vector.

Is exact computation of \(BR_c\) polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?

For a finite electorate of \(n\) voters, lexicographic best-response sets are computable in \(O(nm[T_{n,m}+\log m])\) when the voting rule takes \(T_{n,m}\) time; this gives polynomial time for positional scoring rules. [Source](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p867.pdf)
No result settling exactly the rational-mass problem stated above was located in the literature search.

Exact computation of \(BR_c\) is polynomial-time solvable in \(m,\tau,L\). The proof below gives an exact algorithm, including endpoint inclusion and isolated best-response positions.

The finite-electorate result in [Proposition 1 of Sabato et al.](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p867.pdf) also uses a partition into regions with constant election outcome. Here we prove directly that such a partition has polynomial size and that binary rational masses permit polynomial-time exact score computation.

• Constructing the finite partition.

Write \(p_d\in\mathbb{Q}\) for the fixed position of each candidate \(d\neq c\). For type \(t\), the distance comparison between \(c\) and \(d\) can change only where
\( |x-q_t|=|p_d-q_t|. \)
Because both sides are nonnegative, this equality is equivalent to equality of their squares. Factoring gives
\( (x-q_t)^2-(p_d-q_t)^2=(x-p_d)(x+p_d-2q_t)=0. \)
Thus its only possible solutions are \(p_d\) and \(2q_t-p_d\), possibly coinciding.

Define the rational breakpoint set
\( B=\{a,b\}\cup\bigl(\{p_d,\,2q_t-p_d:1\leq t\leq\tau,\ d\neq c\}\cap[a,b]\bigr). \)
Remove duplicates and sort its elements as \(z_1<\cdots<z_K\). Since both endpoints belong to \(B\), \(z_1=a\) and \(z_K=b\), with \(K=1\) when \(a=b\). Moreover,
\( K\leq 2\tau(m-1)+2. \)

Partition \(I_c\) into the singleton cells \(\{z_i\}\) and the nonempty open interval cells \((z_i,z_{i+1})\). There are \(2K-1\) cells. Choose \(z_i\) as the representative of its singleton cell and \((z_i+z_{i+1})/2\) as the representative of each interval cell.

• Proving constancy on every interval cell.

Fix a type \(t\), a candidate \(d\neq c\), and an interval cell \(J=(z_i,z_{i+1})\). The continuous function
\( f_{t,d}(x)=|x-q_t|-|p_d-q_t| \)
has no zero in \(J\), because all its zeros in \(I_c\) were included in \(B\). It therefore has constant sign on \(J\): otherwise the intermediate value theorem would give a zero between two points with opposite signs.

Consequently, type \(t\)'s ordering of \(c\) and \(d\) is constant throughout \(J\). Every comparison between two candidates other than \(c\) is also constant, since their positions are fixed; any equality is resolved by the supplied fixed lexicographic order.

A strict ranking is determined by its pairwise comparisons. Hence every type's entire ranking is constant on \(J\). The masses and scoring vector are fixed, so every candidate's weighted score, and thus the lexicographically selected winner, is constant on \(J\).

Singleton cells are evaluated separately using the supplied tie-breaking rules. This covers simultaneous distance equalities, coincident candidate positions, and score ties without assuming that a breakpoint has the same winner as either neighboring interval.

• Computing winners with polynomial-size integer arithmetic.

At any representative position \(r\), sort the candidates for each type by distance, breaking equal distances lexicographically. Let \(\operatorname{rank}_{t,r}(d)\) be the resulting rank of candidate \(d\). Its score is
\( S_d(r)=\sum_{t=1}^{\tau}\mu_t\alpha_{\operatorname{rank}_{t,r}(d)}. \)

To compute these scores exactly, write the input rationals with positive denominators as
\( \mu_t=u_t/v_t,\qquad \alpha_j=h_j/g_j. \)
Set
\( D_\mu=\prod_{t=1}^{\tau}v_t,\qquad D_\alpha=\prod_{j=1}^{m}g_j, \)
and define the integers
\( U_t=u_t(D_\mu/v_t),\qquad H_j=h_j(D_\alpha/g_j). \)
Then
\( S_d(r)=\frac{N_d(r)}{D_\mu D_\alpha}, \qquad N_d(r)=\sum_{t=1}^{\tau}U_tH_{\operatorname{rank}_{t,r}(d)}. \)
The denominator is common and positive, so comparing scores is exactly equivalent to comparing the integer numerators \(N_d(r)\). Among candidates attaining the largest numerator, select the first in the supplied lexicographic order.

These calculations have polynomial bit complexity. Indeed, the sum of the input numerator and denominator bit lengths is at most \(L\). A product of input denominators therefore has \(O(L)\) bits. Each \(U_t\) and \(H_j\) also has \(O(L)\) bits, and each score numerator has \(O(L+\log(\tau+1))\) bits.

Breakpoints and representatives likewise have \(O(L)\)-bit rational representations: they are obtained from a constant number of input rationals by addition, subtraction, and division by two. Distances and their comparisons consequently use integers of \(O(L)\) bits. Standard exact integer arithmetic makes every operation above polynomial-time in the input length.

In particular, this algorithm never expands a rational mass into repeated voters.

• Selecting and representing exactly the best-response set.

Evaluate the winner at every cell representative. By the constancy proved above, this gives the winner \(w(E)\) on every cell \(E\).

Let \(w^\star\) be the most preferred candidate, according to \(\succ_c\), among these finitely many winners. It exists because \(I_c\) is nonempty, and it is unique because \(\succ_c\) is strict.

We claim that
\( BR_c=\bigcup_{\{E:\,w(E)=w^\star\}}E. \)
If \(x\) belongs to a selected cell, its winner is \(w^\star\), which is at least as preferred as every attainable winner. Thus \(x\in BR_c\). Conversely, if its cell has another winner, a representative of a cell with winner \(w^\star\) gives a strictly preferred outcome, so \(x\notin BR_c\). This proves the equality.

To produce the requested representation, scan the cells in their natural alternating order:
\( \{z_1\},\ (z_1,z_2),\ \{z_2\},\ldots,\ (z_{K-1},z_K),\ \{z_K\}. \)
Merge each maximal consecutive run of selected cells. A run containing an interval cell is an interval with rational endpoints; include its left or right endpoint exactly when the corresponding singleton cell belongs to the run. A run containing only a singleton produces an isolated rational position. Such a point is isolated in \(BR_c\) because each existing adjacent interval cell is unselected.

This scan therefore records all endpoint inclusions exactly, including cases where an excluded breakpoint separates two selected intervals.

For completeness, sorting the breakpoints takes \(O(K\log(K+1))\) rational comparisons. Each cell evaluation takes \(O(\tau m\log(m+1))\) distance comparisons and \(O(\tau m)\) score operations. Including integer preprocessing, the number of arithmetic operations is
\( O\bigl(m+\tau+K\log(K+1)+K\tau m\log(m+1)\bigr). \)
Since \(K=O(\tau m)\) and every operation has polynomial bit complexity, the total running time is polynomial in \(m,\tau,L\). The output contains at most \(2K-1\) pieces, each with polynomial-size rational endpoints.

The same construction covers \(m=1\), \(a=b\), and the zero scoring vector. In particular, no nondegeneracy assumption is needed.

⟨structured verdict parsed — rendered above⟩

Verification report

The prover fully resolves the stated task. The argument establishes a polynomial-time algorithm for computing the entire best-response set exactly, with rational endpoints, correct endpoint inclusion, and isolated positions. No major or minor mathematical issues were found.

1. Finite partition

The equality identifying possible ranking changes is correct:
\( |x-q_t|=|p_d-q_t| \) is equivalent to equality of squares because both distances are nonnegative. The factorization
\( (x-q_t)^2-(p_d-q_t)^2=(x-p_d)(x+p_d-2q_t) \)
is correct. Its roots are precisely \(p_d\) and \(2q_t-p_d\), including the case where they coincide.

The breakpoint set includes every such root within the feasible interval and includes both endpoints. Duplicate removal correctly handles coincident roots, candidate positions, and endpoints.

The bound \(K\leq 2\tau(m-1)+2\) is valid. There are exactly \(K\) singleton cells and \(K-1\) open interval cells, hence \(2K-1\) cells. When \(a=b\), there is one singleton and no interval cell.

Every representative belongs to its cell. In particular, the midpoint of two distinct consecutive breakpoints lies strictly between them.

Assessment: Correct and complete.

2. Constancy within interval cells

The function \(f_{t,d}\) is continuous. Every zero in the feasible interval belongs to the breakpoint set, so an open interval cell contains no zero.

The invoked intermediate value theorem applies: a continuous function on the segment between two points with opposite signs must vanish somewhere between them. That segment lies within the interval cell. Consequently, the function has constant sign there.

This establishes every comparison involving \(c\). Comparisons between fixed candidates remain constant, including their lexicographic resolution when distances coincide. These comparisons determine each type’s strict ranking.

Fixed rankings, masses, and scoring coefficients imply fixed candidate scores. The fixed election tie-breaking order then implies a fixed winner.

Evaluating singleton cells independently correctly covers simultaneous equalities and discontinuities at breakpoints.

Assessment: Correct and complete; the theorem’s hypotheses are satisfied.

3. Exact scores and bit complexity

The common-denominator construction is valid. Each quotient \(D_\mu/v_t\) and \(D_\alpha/g_j\) is an integer, and both common denominators are positive. Substitution gives exactly
\(S_d(r)=N_d(r)/(D_\mu D_\alpha)\).
Thus comparing integer numerators preserves score comparisons and score ties.

The bit-length bounds are sound:

• The bit length of a product of input denominators is bounded by the sum of their bit lengths, up to a constant.
• Each scaled numerator \(U_t\) and \(H_j\) has \(O(L)\) bits.
• Each product \(U_tH_j\) has \(O(L)\) bits, and summing \(\tau\) such terms requires at most an additional \(O(\log(\tau+1))\) bits.
• Each breakpoint and midpoint uses only a constant number of arithmetic operations on input rationals, giving \(O(L)\)-bit representations.
• Distance computations and rational comparisons therefore also involve integers of polynomially bounded bit length.

Standard exact integer arithmetic suffices for all these operations in polynomial time. The argument does not rely on expanding masses into a potentially enormous finite electorate.

Assessment: Correct and sufficient for polynomial bit complexity.

4. Identification of the best-response set

The cells cover every feasible real position, and every attainable winner appears at a cell representative. Therefore, choosing the most preferred representative winner also chooses the most preferred attainable winner.

Existence follows from the nonempty feasible interval and finite nonempty collection of cells. Uniqueness follows from the supplied strict preference order.

Both directions of the claimed equality are justified:

• Every selected cell has the most preferred attainable winner, so every position in it satisfies the defining universal comparison.
• Every unselected cell has a strictly less preferred winner, and a representative attaining the preferred winner witnesses failure of that comparison.

This checks the quantification over all real feasible positions, including irrational positions.

Assessment: Correct and complete.

5. Exact output representation

Merging maximal consecutive selected cells is valid. A run containing an interval cell forms an interval; its endpoint inclusion is determined exactly by whether the corresponding singleton is selected.

An unselected singleton prevents two neighboring selected intervals from being merged, preserving a missing breakpoint correctly.

A run consisting solely of a singleton gives an isolated point: every existing adjacent interval cell is unselected. This also covers a singleton feasible domain.

All output endpoints and isolated positions are rational, and merging cannot increase the number of pieces beyond \(2K-1\).

Assessment: Correct and satisfies the requested representation.

6. Running time, edge cases, and citation

The stated arithmetic-operation bound accounts for breakpoint sorting, preprocessing, rankings, and score evaluation. Winner selection and the final scan fit within that bound. Since \(K=O(\tau m)\) and all operands have polynomial bit length, the resulting bit running time is polynomial in \(m,\tau,L\).

The asserted edge cases are covered:

• For \(m=1\), the sole candidate wins throughout the interval.
• For \(a=b\), the single position is evaluated directly.
• For the zero scoring vector, all scores tie and the supplied election order determines the same winner everywhere.
• Coincident candidate positions and simultaneous breakpoints are handled by duplicate removal and separate singleton evaluation.

The introductory attribution is accurate: [Proposition 1 and its accompanying discussion](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p867.pdf) describe a polynomial partition into regions with constant election outcome. The present proof establishes the rational-mass result independently, so no extension of that proposition is assumed.

Repair feedback: None required.

⟨structured verdict parsed — rendered above⟩