Dynamic Proportional Rankings (d4-conf-ijcai-2021-0486)

Given a finite candidate set \(C\), a finite support \(T\subseteq 2^C\) of approval types, rational masses \(\mu_t\geq 0\) with \(\sum_{t\in T}\mu_t=1\), a sequence \(X\) of implemented candidates, and a fixed tie-breaking order, define \(H_q=\sum_{j=1}^{q}1/j\) and \(F_\mu(S)=\sum_{t\in T}\mu_tH_{|t\cap S|}\). Compute the complete ranking \(r\) of \(C\setminus X\) such that each \(r_k\) is the tie-broken maximizer of \(F_\mu(X\cup r_{<k}\cup\{c\})-F_\mu(X\cup r_{<k})\) over all remaining candidates.

Let \(C\) be a finite candidate set with \(m=|C|\). A society is given by its support: an explicit list \(T\subseteq 2^C\) of \(\tau=|T|\) approval types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible approval types; let \(L\) be the total input bit length.
The input also contains a possibly empty sequence \(X\) of distinct implemented candidates from \(C\), treated as a set in scoring, and a strict priority order on \(C\) for breaking ties. Empty approval sets and candidates with no supporters are allowed.
Define \(H_0=0\), \(H_q=\sum_{j=1}^{q}1/j\) for positive integers \(q\), and \(F_\mu(S)=\sum_{t\in T}\mu_t H_{|t\cap S|}\) for \(S\subseteq C\).
The required output is the complete ranking \(r\) of \(C\setminus X\): at each position \(k\), writing \(r_{<k}=\{r_1,\ldots,r_{k-1}\}\), choose the highest-priority maximizer of \(F_\mu(X\cup r_{<k}\cup\{c\})-F_\mu(X\cup r_{<k})\) among remaining candidates.

Is computing this ranking solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For an explicitly listed electorate of \(n\) voters, dynamic sequential PAV computes the corresponding ranking in \(\mathcal{O}(m^3n)\) time.

Result

Computing the complete ranking is polynomial-time solvable in \(m,\tau,L\). The explicitly listed support permits direct calculation of every marginal score, and exact rational comparisons require only polynomially many bits.

Marginal scores

For an already selected set \(S\subseteq C\), define \(q_t=|t\cap S|\). If \(c\notin S\), adding \(c\) increases the harmonic term for type \(t\) precisely when \(c\in t\). Since \(H_{q+1}-H_q=1/(q+1)\), the marginal score is

\[ \Delta(c\mid S)=F_\mu(S\cup\{c\})-F_\mu(S) =\sum_{\substack{t\in T\\c\in t}}\frac{\mu_t}{q_t+1}. \]

Thus calculating a score requires examining only the \(\tau\) listed types.

Exact integer comparisons

Assume first that \(m\geq 1\). Write each input mass as \(\mu_t=a_t/b_t\), with positive integers \(a_t,b_t\) encoded in binary. Define

\[ D=\prod_{t\in T}b_t,\qquad W_t=a_t(D/b_t),\qquad P=m!. \]

Each \(W_t\) is an integer, and normalization gives \(\sum_{t\in T}W_t=D\).

Whenever \(c\notin S\) and \(c\in t\), we have \(q_t\leq m-1\). Hence \(1\leq q_t+1\leq m\), so \(q_t+1\) divides \(P\). Consequently,

\[ A(c\mid S)= \sum_{\substack{t\in T\\c\in t}} W_t\frac{P}{q_t+1} \]

is an integer satisfying \(\Delta(c\mid S)=A(c\mid S)/(DP)\). The denominator \(DP\) is common to every candidate and every stage. Comparing these integer numerators therefore compares marginal scores exactly, including ties.

Moreover, every summand is nonnegative and \(P/(q_t+1)\leq P\), so

\[ 0\leq A(c\mid S)\leq P\sum_{t\in T}W_t=DP. \]

The binary length of \(D\) is at most \(1+L\), because the sum of the encoded denominator lengths is at most \(L\). Also, \(P=m!\leq m^m\). Thus all score numerators have \(O(L+m\log(m+1))\) bits.

Algorithm and correctness

Initialize \(S=X\) and \(q_t=|t\cap X|\) for every listed type. Precompute the integers \(P/j\) and \(W_t(P/j)\) for \(1\leq j\leq m\).

Repeat until no candidates remain:

• For each \(c\in C\setminus S\), compute \(A(c\mid S)\) using the current counts.
• Choose a candidate with maximum numerator, breaking ties by the supplied strict priority order.
• Append that candidate to the ranking, add it to \(S\), and increment \(q_t\) for exactly those types containing it.

For correctness, initially \(q_t=|t\cap S|\). If this identity holds before selecting \(c\), the update increases both sides by one exactly when \(c\in t\). It therefore remains true after selection.

Inductively, at every stage \(S=X\cup r_{<k}\), and the calculated integers represent exactly the required marginal scores with their common positive denominator. Maximizing the integers and applying the given priority order selects exactly the candidate required by the definition. This proves correctness of the complete ranking.

Bit complexity and boundary cases

There are at most \(m\) stages, each evaluating at most \(m\) candidates and examining at most \(\tau\) types per candidate. Thus score evaluation uses \(O(m^2\tau)\) integer additions. There are also \(O(m^2)\) comparisons and \(O(m\tau)\) count updates.

Let \(B=O(L+m\log(m+1)+1)\) bound the integer lengths. Constructing the common denominators and precomputed summands requires \(O(\tau+m+\tau m)\) integer multiplications or exact divisions. Using elementary \(O(B^2)\)-time arithmetic gives, conservatively, total bit time

\[ O\!\left(L+(\tau+m+\tau m)B^2+m^2(\tau+1)B\right), \]

which is polynomial in the requested parameters. Membership tables for the listed types require only polynomial preprocessing and space.

Empty approval types contribute zero. Candidates without supporters have score zero, so the same algorithm ranks them according to the required comparisons and tie rule. If \(C\setminus X\) is empty, including when \(m=0\), the output is the empty ranking.

No unlisted approval types need to be enumerated.

⟨structured verdict parsed — rendered above⟩

The prover resolves the task correctly: computing the complete ranking is polynomial-time solvable in \(m,\tau,L\). The argument supplies an exact algorithm, proves that it follows the prescribed selection rule, and bounds its bit complexity. No major or minor mathematical issues were found.

• Marginal-score formula. For \(c\notin S\), the intersection size for a type increases by one precisely when \(c\in t\). The identity \(H_{q+1}-H_q=1/(q+1)\) applies for every integer \(q\geq0\), including \(q=0\). Therefore the displayed formula for \(\Delta(c\mid S)\) is correct. It examines only the explicitly listed types, as required.

• Common denominator and integer scores. Each positive input denominator \(b_t\) divides \(D\), so \(W_t=a_t(D/b_t)\) is a positive integer. The normalization assumption indeed yields \(\sum_t W_t=D\). For every summand actually used, \(c\in t\) and \(c\notin S\) imply \(q_t\leq m-1\). Thus \(q_t+1\) belongs to \(\{1,\ldots,m\}\) and divides \(m!\). Consequently, \(A(c\mid S)\) is an integer and satisfies the claimed equality \(\Delta(c\mid S)=A(c\mid S)/(DP)\). The common denominator is positive, so integer comparisons preserve both strict comparisons and ties.

• Integer-size bounds. Nonnegativity and normalization justify \(0\leq A(c\mid S)\leq DP\). The product defining \(D\) has binary length at most one plus the sum of the input denominator lengths, hence at most \(1+L\). The bound \(m!\leq m^m\) is valid for \(m\geq1\), giving the stated polynomial bit bound. The precomputed summands also have this bound: normalization implies \(W_t\leq D\), and \(P/j\leq P\). Intermediate products during construction of \(D\) and \(P\) do not exceed their final products.

• Algorithm and correctness. The initialization establishes \(q_t=|t\cap S|\), with the sequence \(X\) correctly treated as a set. Updating exactly the types containing the chosen candidate preserves this invariant. Every iteration considers precisely the remaining candidates, computes their exact marginal scores, and applies the supplied strict priority order. The induction therefore establishes the required ranking at every position. Termination after \(|C\setminus X|\) iterations gives the complete output.

• Bit complexity. There are at most \(m^2\tau\) type examinations for score evaluation, at most \(O(m^2)\) score comparisons, and at most \(O(m\tau)\) count updates. The stated preprocessing operation count covers construction of the integer weights, factorial, quotients, and summands. Elementary arithmetic on the bounded integers supports the displayed conservative polynomial running time. Membership-table construction and access can also be accommodated within that bound: constructing a table uses polynomial space and at most \(O(L+m\tau)\) preprocessing time.

• Boundary cases and scope. Empty approval types never contribute a summand. Unsupported candidates receive score zero, and the prescribed priority order resolves their ties whenever applicable. If all candidates are already implemented, the output is empty. The case \(m=0\) is correctly handled separately, avoiding the construction intended for \(m\geq1\). The proof never assumes that all possible approval types are listed and does not confuse support size with electorate size.

No additional clarification is needed to make the argument verifiable. The result establishes the polynomial-time side of the question; it does not require a separate hardness analysis.

⟨structured verdict parsed — rendered above⟩