d4-conf-aaai-2017-0355 (d4-conf-aaai-2017-0355)

Given candidates \(C\), a tie-breaking order, a designated candidate \(c^\star\), and a support \(T\subseteq\mathrm{Lin}(C)\) with positive binary-rational masses \(\mu_t\) summing to \(1\), determine whether \(c^\star\) wins STV. In each round, assign each type’s mass to its highest-ranked remaining candidate, eliminate a candidate with minimum assigned mass using the given tie-breaking order, and repeat until one candidate remains.

Let \(C\) be a nonempty candidate set, with \(m=|C|\), and let \(c^\star\in C\). A type is a strict total ranking of all candidates. A society is given by its support: a list \(T\) of \(\tau\) distinct types with positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
A strict total tie-breaking order on \(C\) is also supplied; its earliest candidate among tied candidates is eliminated. In each round, assign each type's entire mass to its highest-ranked remaining candidate and eliminate the candidate with minimum assigned mass, resolving ties by that order. After \(m-1\) rounds, the remaining candidate wins.

Is deciding whether \(c^\star\) wins this rational-mass STV election solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For an explicitly listed finite electorate with strict total rankings and a supplied tie-breaking order, STV winner determination is P-complete. It also admits an \(O(m+\log n)\)-space algorithm, where \(n\) is the number of voters.

Result

The problem is polynomial-time solvable in \(m,\tau,L\). Exact integer arithmetic suffices; no expansion into an explicitly listed electorate is needed.

Exact integer weights

Write each input mass as \(\mu_t=a_t/b_t\), with positive integers \(a_t,b_t\) encoded in binary. This also covers dyadic rationals given as finite binary expansions.

Define \(D=\prod_{t\in T}b_t\) and \(w_t=a_t(D/b_t)\). Each \(w_t\) is a positive integer, and the normalization hypothesis gives
\[ \sum_{t\in T}w_t=D. \]
The binary length of \(D\) is at most \(1+\sum_{t\in T}\log_2 b_t\), hence is \(O(L)\). Since every \(w_t\) is positive and their sum is \(D\), every weight also has \(O(L)\) bits.

For a nonempty set \(R\) of remaining candidates, let \(h_t(R)\) be type \(t\)'s highest-ranked candidate in \(R\). Define the integer tally of candidate \(c\in R\) by
\[ S_R(c)=\sum_{\{t:\ h_t(R)=c\}}w_t. \]
Its rational assigned mass is exactly \(S_R(c)/D\). Consequently, integer tallies preserve both strict comparisons and ties between assigned masses. Every tally lies between \(0\) and \(D\), so it has \(O(L)\) bits.

Simulation and correctness

Store each ranking as an array, maintain the set of remaining candidates, and keep a pointer into each type's ranking. Initially every pointer is at the first position.

In each of the \(m-1\) rounds:

• Initialize every remaining candidate's integer tally to zero.
• For each type, advance its pointer past eliminated candidates and add \(w_t\) to the tally of the candidate at its pointer.
• Eliminate the candidate with smallest integer tally, using the supplied tie-breaking order among tied candidates.

A pointer always stops: at least one candidate remains, and every ranking contains every candidate.

We prove correctness by induction on the rounds. Initially the algorithm and the specified election have the same remaining set, namely \(C\). Suppose their remaining sets agree at the start of a round. A pointer never skips a remaining candidate, and candidates previously skipped remain eliminated. Thus it identifies exactly \(h_t(R)\). The computed tallies are therefore \(S_R(c)\). By the common-denominator argument, their comparisons and ties coincide exactly with those of the rational assigned masses. Applying the supplied tie-breaking order eliminates the same candidate in both procedures. Their remaining sets consequently agree after the round.

After \(m-1\) rounds, the algorithm's surviving candidate is therefore the STV winner. For \(m=1\), the sole candidate wins immediately.

Running time

Using schoolbook integer arithmetic, computing \(D\) and all the weights takes \(O(\tau L^2)\) bit operations: all operands have \(O(L)\) bits, and there are \(O(\tau)\) multiplications and exact divisions.

Each type's pointer advances at most \(m-1\) times over the entire simulation. Each round performs \(\tau\) additions and \(O(m)\) tally initializations and comparisons, all involving \(O(L)\)-bit integers. Pointer operations also fit within this bound.

Thus a valid total running-time bound is
\[ O\!\left(\tau L^2+m(\tau+m)L\right), \]
which is polynomial in the requested parameters.

The supplied P-completeness result for explicitly listed electorates is compatible with this conclusion: P-complete problems are polynomial-time solvable. Here the potentially enormous common denominator matters only through its \(O(L)\) binary length. Under polynomial-time many-one reductions, NP-hardness of this problem would therefore imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verification verdict

The output resolves the task correctly. It establishes an exact polynomial-time algorithm in \(m,\tau,L\), without expanding the rational masses into individual voters. No major or minor mathematical issues were found.

Step-by-step audit

1. Representation and integer conversion

Writing each positive binary-rational mass as \(\mu_t=a_t/b_t\) is valid. For finite binary expansions, the corresponding numerator and power-of-two denominator have bit lengths bounded by the input length.

The definitions \(D=\prod_{t\in T}b_t\) and \(w_t=a_t(D/b_t)\) produce positive integers because every \(b_t\) divides \(D\). Moreover,
\[ \sum_{t\in T}w_t=D\sum_{t\in T}\mu_t=D. \]
Thus the normalization identity is correct.

The bit-length bound is also correct: the binary length of \(D\) is at most \(1+\sum_t\log_2 b_t\), which is \(O(L)\). Positivity and normalization imply \(w_t\leq D\), so every weight has \(O(L)\) bits.

2. Preservation of election decisions

For every nonempty remaining set \(R\), strict total rankings make \(h_t(R)\) uniquely defined. The assigned mass of each remaining candidate is exactly \(S_R(c)/D\).

Since \(D>0\) is common to all candidates, integer tallies preserve every strict comparison and equality. This includes zero-tally candidates. Therefore the supplied tie-breaking order yields the same elimination under integer and rational arithmetic.

Every tally is a sum of a subset of the positive weights, hence lies between zero and \(D\). The claimed \(O(L)\)-bit bound follows.

3. Pointer simulation

The pointer invariant is justified. A pointer advances only past eliminated candidates, and eliminated candidates never return. Consequently, all ranking positions preceding a pointer contain eliminated candidates. Advancing past any newly eliminated candidates therefore identifies precisely the highest-ranked remaining candidate.

The stopping argument is valid: each ranking contains every candidate, and a round begins with a nonempty remaining set.

The round-by-round induction correctly establishes identical remaining sets in the simulation and the specified election. It then establishes the same final survivor. The case \(m=1\) is explicitly and correctly handled.

4. Running time

The preprocessing bound \(O(\tau L^2)\) is valid with schoolbook arithmetic. There are \(O(\tau)\) multiplications and exact divisions, and their operands and intermediate products have \(O(L)\) bits.

During the simulation:

• Each type’s pointer advances at most \(m-1\) times in total.
• Each round makes \(\tau\) additions of \(O(L)\)-bit integers.
• Initializing tallies and selecting the candidate to eliminate require \(O(m)\) operations per round, each bounded by \(O(L)\) bit operations.

Reading and storing the explicit rankings, representing candidate indices, and consulting the supplied tie-breaking order fit within the stated bound. Thus
\[ O\!\left(\tau L^2+m(\tau+m)L\right) \]
is a valid polynomial upper bound.

5. Complexity conclusion

The polynomial-time conclusion follows from the established algorithm and bit-complexity analysis.

The discussion of the supplied P-completeness result is consistent: P-completeness does not contradict polynomial-time solvability. The final statement about NP-hardness is appropriately conditional; under polynomial-time many-one reductions, NP-hardness together with this algorithm would imply \(\mathrm{P}=\mathrm{NP}\).

Required clarification

None. The argument is verifiable as written.

⟨structured verdict parsed — rendered above⟩