d4-conf-ijcai-2018-0283 (d4-conf-ijcai-2018-0283)

Given candidates \(A\), a finite support \(T\) of strict ranking types over \(A\), positive rational masses \(\mu_t\) summing to \(1\), a fixed tie-breaking order, and candidate \(c\), define \(\Delta_\mu(a,b)=\sum_{t\in T}\mu_t(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a])\). Apply the paper’s Ranked Pairs rule to these margins; is \(c\) the resulting winner?

Let \(A\) be a nonempty candidate set, \(m=|A|\), and \(c\in A\). A society is given by its support: a list \(T\) of \(\tau\) distinct strict ranking types over \(A\), each with 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. A fixed linear order \(\prec\) on candidates is supplied; let \(L\) be the total input bit length.
Define \(\Delta_\mu(a,b)=\sum_{t\in T}\mu_t(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a])\).
Ranked Pairs processes all ordered pairs \((a,b)\) with \(a\ne b\) in decreasing order of \(\Delta_\mu(a,b)\), breaking equal-margin ties lexicographically by \(\prec\) on the first and then second coordinate. Starting with an empty directed graph, add each pair unless it creates a directed cycle. Include zero-margin pairs. The winner is the unique candidate with no incoming edge in the final graph.

Is deciding whether \(c\) is this winner solvable in polynomial time in \(m,\tau,L\), or is it \(\mathsf{NP}\)-hard?

Discrete Ranked Pairs winner determination with fixed tie-breaking is \(\mathsf{P}\)-complete, including with strict-ranking profiles; its weighted-majority-graph formulation is explicitly in \(\mathsf{P}\). [Source](https://arxiv.org/html/2505.12976v2)
No separate classification for the specified rational-support representation was located.

Result

The decision problem is solvable in deterministic polynomial time in \(m,\tau,L\), hence belongs to \(\mathsf{P}\). Binary rational masses permit exact computation of all margins with polynomially many bits.

The cited paper establishes polynomial-time membership for the weighted-majority-graph formulation. The proof below explicitly handles the rational-support input and the specified processing of all ordered pairs. [Csar, Lackner, and Pichler, Section 3](https://arxiv.org/html/2505.12976v2)

1. Compute exact integer margins

Write each encoded mass as \(\mu_t=p_t/q_t\), where \(p_t,q_t\) are positive integers represented in binary. Define
\[ D=\prod_{t\in T}q_t, \qquad w_t=p_t(D/q_t). \]
Each division is exact. Since the masses sum to one,
\[ \sum_{t\in T}w_t=D. \]

Although the numerical value of \(D\) can be exponential in the input length, its binary length is polynomial: indeed,
\[ \log_2 D=\sum_{t\in T}\log_2 q_t\leq L. \]
Thus \(D\) has at most \(L+1\) bits. Positivity and normalization imply \(0<w_t\leq D\), so every \(w_t\) also has at most \(L+1\) bits. Standard integer multiplication and exact division therefore compute these integers in polynomial time.

For each ranking type \(t\), record the position of every candidate. For every ordered pair of distinct candidates, compute
\[ S(a,b)=\sum_{t\in T}w_t \bigl(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a]\bigr). \]
By construction,
\[ S(a,b)=D\,\Delta_\mu(a,b). \]
Because \(D>0\), comparing two margins is equivalent to comparing their integer scores, including equality:
\[ \Delta_\mu(a,b)>\Delta_\mu(x,y) \quad\Longleftrightarrow\quad S(a,b)>S(x,y). \]

Moreover,
\[ |S(a,b)|\leq\sum_{t\in T}w_t=D. \]
Every intermediate partial sum has absolute value at most \(D\) for the same reason. All arithmetic therefore uses integers with \(O(L+1)\) bits. Computing the scores requires \(O(\tau m^2)\) additions once ranking positions are available.

2. Construct the prescribed processing order

Assign each candidate its position in the supplied order \(\prec\). Sort all \(m(m-1)\) ordered pairs by:

• decreasing integer score \(S(a,b)\);
• increasing position of the first coordinate in \(\prec\);
• increasing position of the second coordinate in \(\prec\).

The preceding scaling identity proves that this is exactly the processing order required by the question. Zero and negative scores are included.

Comparison sorting uses \(O(m^2\log(m+1))\) comparisons. Each comparison examines integers with \(O(L+1)\) bits and candidate positions with \(O(\log(m+1))\) bits, so sorting takes polynomial time.

3. Simulate locking exactly

Maintain a directed graph \(G\), initially empty. When processing \((a,b)\), search \(G\) for a directed path from \(b\) to \(a\). Reject the pair if such a path exists; otherwise add the edge \(a\to b\).

This test is correct because \(G\) remains acyclic:

• If a path from \(b\) to \(a\) exists, adding \(a\to b\) completes a directed cycle.
• Conversely, any cycle created by adding \(a\to b\) must contain that new edge, since \(G\) was acyclic. Removing the new edge from the cycle leaves a path from \(b\) to \(a\) in \(G\).

Thus, by induction over the sorted list, this algorithm constructs exactly the graph specified in the question.

With an adjacency matrix, each reachability search takes \(O(m^2)\) elementary graph operations. There are \(m(m-1)\) searches, so locking takes \(O(m^4)\) elementary graph operations and polynomial bit time.

4. Prove that the final winner is unique

Let \(G_{\mathrm{final}}\) denote the final graph. It is acyclic by the locking rule.

For any two distinct candidates \(a,b\), consider the first processed pair among \((a,b)\) and \((b,a)\). If it is accepted, its edge gives a path between the candidates. If it is rejected, the rejection test already supplies a path in the opposite direction. Edges are never removed, so in \(G_{\mathrm{final}}\) there is a directed path between every two distinct candidates in one direction.

Every finite nonempty acyclic directed graph has a vertex with no incoming edge: otherwise, repeatedly following an incoming edge backwards would eventually repeat a vertex, producing a directed cycle.

There cannot be two such vertices in \(G_{\mathrm{final}}\). If \(u\) and \(v\) were distinct vertices with no incoming edge, the established comparability would give a path from one to the other. The last edge of that path would be an incoming edge at its endpoint, a contradiction.

Consequently, \(G_{\mathrm{final}}\) has exactly one vertex with no incoming edge, including when \(m=1\).

5. Classification

After constructing \(G_{\mathrm{final}}\), inspect whether \(c\) has an incoming edge. Accept exactly when it has none.

Every stage has polynomial bit complexity in \(m,\tau,L\). This proves that the specified rational-support winner problem belongs to \(\mathsf{P}\). Under polynomial-time many-one reductions, it could also be \(\mathsf{NP}\)-hard only if \(\mathsf{P}=\mathsf{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover fully resolves the task. Its algorithm correctly implements the prescribed rule, and its bit complexity is polynomial in \(m,\tau,L\). No major or minor mathematical issues were found.

• Exact integer scaling is valid. Each denominator \(q_t\) is positive, so \(D=\prod_{t\in T}q_t>0\), and each quotient \(D/q_t\) is an integer. The identities \(w_t=D\mu_t\) and \(\sum_{t\in T}w_t=D\) follow directly from the input normalization. Reduced fractions are unnecessary.

The bound \(\log_2 D\leq L\) is justified because the denominator encodings are included in the total input length. Thus \(D\) has at most \(L+1\) binary digits. Positivity and normalization give \(0<w_t\leq D\). The successive products, exact divisions, and weight computations all involve polynomially many bits and polynomially many operations.

• Margin computation and its bounds are correct. Strict rankings ensure that every summand has coefficient either \(1\) or \(-1\). Consequently, \(S(a,b)=D\Delta_\mu(a,b)\). The positive common factor preserves both strict comparisons and equality.

The bound \(|S(a,b)|\leq D\) is correct. It also holds for every intermediate partial sum, since the sum of the weights in any subset of the support is at most \(D\). The stated \(O(\tau m^2)\) addition count is valid after recording ranking positions. Constructing those position records also takes polynomial time.

• The processing order matches the task exactly. Sorting by decreasing integer score and then by the two candidate positions implements the specified lexicographic tie-breaking. Every ordered pair of distinct candidates is included, including pairs with zero or negative margin. The comparison count and operand lengths yield polynomial bit complexity. For \(m=1\), the list is empty and requires no comparisons.

• The locking simulation is correct. The graph starts acyclic. In an acyclic graph, adding \(a\to b\) creates a cycle exactly when a path from \(b\) to \(a\) already exists. The prover establishes both directions and correctly uses this equivalence to justify induction over the processing list.

An adjacency-matrix reachability search takes \(O(m^2)\) graph operations. There are \(m(m-1)\) processed pairs, so the stated \(O(m^4)\) graph-operation bound is valid. Accounting for indices and graph storage preserves polynomial bit complexity.

• Uniqueness of the winner is established. For each pair of distinct candidates, the first processed orientation either supplies an accepted edge or is rejected because an opposite directed path already exists. Since edges are never removed, the final graph has a directed path in one direction between every two distinct candidates.

The final graph is finite, nonempty, and acyclic, so the backward-edge argument establishes the existence of a vertex with no incoming edge. Two such vertices would contradict the established path comparability. The singleton case is also covered: its graph has one vertex and no edges.

• The decision procedure and classification follow. Inspecting whether \(c\) has an incoming edge therefore decides whether it is the unique winner. Every stage has polynomial bit complexity. The conclusion concerning possible \(\mathsf{NP}\)-hardness under polynomial-time many-one reductions is correctly qualified by \(\mathsf{P}=\mathsf{NP}\).

• The source claim is accurate and supplementary. Section 3 of the cited paper defines winner determination on weighted majority graphs, states Ranked Pairs winner determination to be \(\mathsf{P}\)-complete, and explicitly asserts polynomial-time membership. The prover independently verifies the rational-support representation and prescribed processing rule, so its conclusion does not require transferring an unstated representation-equivalence theorem. [Csar, Lackner, and Pichler, Section 3](https://arxiv.org/html/2505.12976v2)

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩