d4-conf-aaai-2021-0057 (d4-conf-aaai-2021-0057)

Given candidates \(C\), a committee limit \(k\), and an ordered support of \(\tau\) complete types, where type \(t_i\) has a strict ranking of \(C\), consistent rational misrepresentation costs \(\rho_i(c)\), and rational mass \(\mu_i>0\) with \(\sum_{i=1}^{\tau}\mu_i=1\), assume the rankings are single-crossing in support order. Find a committee \(W\subseteq C\), \(|W|\le k\), and representatives \(a_i\in W\) minimizing \(\sum_{i=1}^{\tau}\mu_i\rho_i(a_i)\).

A society is given by its ordered support: the list of the \(\tau\geq1\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types, and \(\sum_{i=1}^{\tau}\mu_i=1\).
There are \(m\geq1\) candidates \(C\) and an integer committee limit \(1\leq k\leq m\). Each type \(t_i\) specifies a strict ranking \(\succ_i\) and binary-rational costs \(\rho_i(c)\in\mathbb Q\), possibly negative, satisfying \(c\succ_i d\Rightarrow\rho_i(c)\leq\rho_i(d)\); cost ties are allowed.
The rankings are single-crossing in the supplied support order. Choose a nonempty committee \(W\subseteq C\), \(|W|\leq k\), and one representative \(a_i\in W\) for each entire type, minimizing \(\sum_{i=1}^{\tau}\mu_i\rho_i(a_i)\). Any minimizing solution is acceptable.
Let \(L\) be the total binary input length, including a rational threshold \(B\) when considering the decision version; state running times in \(m,\tau,k,L\).

Is this optimization problem solvable in time polynomial in \(m,\tau,k,L\), or is deciding whether its minimum is at most a supplied \(B\in\mathbb Q\) NP-hard?

For an unweighted finite society with \(n\) voters and single-crossing rankings, an optimal Chamberlin–Courant assignment can be computed in \(O(nmk)\) time.
That discrete bound assumes unit-cost arithmetic on rational misrepresentation values.

Result

The problem is polynomial-time solvable. An exact algorithm uses \(O(m\tau L^2+(m+k)\tau^2L)\) bit operations under standard binary encoding of rational numerators and denominators.

The proof uses contiguous blocks of support types. It does not expand rational masses into individual voters.

1. An optimal assignment has contiguous blocks

For distinct candidates \(c,d\), single-crossing in the supplied order means that the preference between \(c\) and \(d\) changes at most once. Consequently, the set \(\{i:c\succ_i d\}\) is a prefix or a suffix of the support order, possibly empty or the entire order.

Fix any nonempty committee \(W\). Let \(t_W(i)\) be its highest-ranked member according to type \(i\). Strict rankings make this member unique. Cost monotonicity gives

\(\rho_i(t_W(i))\leq\rho_i(c)\quad\text{for every }c\in W.\)

Because every mass is positive, replacing each representative by \(t_W(i)\) cannot increase the objective. Thus this assignment minimizes cost for the fixed committee.

For each \(c\in W\), its assigned types form the set

\(I_c=\{i:t_W(i)=c\}=\bigcap_{d\in W\setminus\{c\}}\{i:c\succ_i d\}.\)

Every set in the intersection is a prefix or suffix. Their intersection is an interval, possibly empty. When \(W=\{c\}\), the intersection is the entire support order.

The nonempty sets \(I_c\) partition the support into at most \(|W|\) contiguous blocks, with one representative per block. Since the feasible set is finite and nonempty, an optimum exists. Applying this replacement to an optimal solution proves:

Contiguous-block lemma. There is an optimal solution consisting of at most \(k\) nonempty contiguous blocks, each assigned to one candidate.

Conversely, any partition into at most \(k\) nonempty contiguous blocks, with one candidate assigned to each block, is feasible: take the committee to be the union of these candidates. Repeated candidates only decrease its size.

Therefore, minimizing over such block assignments gives exactly the original optimum.

2. Exact integer scaling

Write the input rationals as

\(\mu_i=p_i/q_i,\qquad \rho_i(c)=a_{ic}/b_{ic},\)

with positive denominators and signed cost numerators. For the decision version, also write \(B=h/g\), with \(g>0\).

Choose the positive integer

\(D=\left(\prod_{i=1}^{\tau}q_i\right)\left(\prod_{i=1}^{\tau}\prod_{c\in C}b_{ic}\right),\)

including an additional factor \(g\) for the decision version. Define

\(w_i(c)=D\mu_i\rho_i(c)=\dfrac{D}{q_i b_{ic}}p_i a_{ic}.\)

These are integers because \(q_i b_{ic}\) divides \(D\). Multiplication by \(D>0\) preserves every comparison between objective values.

The sum of the binary lengths of the denominator factors is at most \(L\), so \(D\) has \(O(L)\) bits. Each \(w_i(c)\) also has \(O(L)\) bits. Any sum containing at most \(\tau\) such weights has \(O(L+\log\tau)=O(L)\) bits, since the explicit input has \(L\geq\tau\).

Negative costs cause no difficulty: all comparisons and additions use signed integers.

3. Dynamic program

For each interval \(1\leq\ell\leq j\leq\tau\), define its minimum scaled assignment cost by

\(H(\ell,j)=\min_{c\in C}\sum_{i=\ell}^{j}w_i(c).\)

Store a candidate attaining this minimum. Compute prefix sums

\(P_c(0)=0,\qquad P_c(j)=\sum_{i=1}^{j}w_i(c),\)

so that every candidate’s interval cost is \(P_c(j)-P_c(\ell-1)\). All interval minima therefore require \(O(m\tau^2)\) integer operations.

Let \(R=\min(k,\tau)\). Define \(F(j,r)\) as the minimum scaled cost of partitioning the first \(j\) types into exactly \(r\) nonempty contiguous blocks, assigning one candidate to each block.

Set \(F(0,0)=0\), \(F(j,0)=+\infty\) for \(j>0\), and \(F(j,r)=+\infty\) when \(j<r\). For \(1\leq r\leq\min(R,j)\), use

\(F(j,r)=\min_{r-1\leq s<j}\bigl(F(s,r-1)+H(s+1,j)\bigr).\)

Here \(+\infty\) is an infeasibility marker.

To justify the recurrence, consider any partition counted by \(F(j,r)\). Its last block has the form \(\{s+1,\ldots,j\}\), and the preceding \(s\) types form exactly \(r-1\) nonempty blocks. Their costs are at least \(F(s,r-1)\) and \(H(s+1,j)\), respectively. Conversely, any finite term in the recurrence combines an attaining prefix partition with an attaining representative for the last block. Hence the recurrence is exact.

The optimum scaled value is

\(V=\min_{1\leq r\leq R}F(\tau,r).\)

Store minimizing split points and backtrack to recover the blocks and their representatives. Their union is a nonempty committee of size at most \(k\).

4. Correctness and running time

Let \(\mathrm{OPT}\) denote the original optimum.

By the contiguous-block lemma, an optimal original solution occurs among the block assignments optimized by the dynamic program. Thus \(V\leq D\,\mathrm{OPT}\).

Conversely, every block assignment considered by the dynamic program gives a feasible original solution, with objective equal to its scaled cost divided by \(D\). Thus \(D\,\mathrm{OPT}\leq V\).

Together these imply \(V=D\,\mathrm{OPT}\), proving that the reconstructed solution is optimal.

For bit complexity, use elementary integer arithmetic:

• Constructing \(D\) costs \(O(L^2)\) bit operations: the aggregate binary length of its factors is \(O(L)\), and successive schoolbook multiplications have total cost \(O(L^2)\).
• Computing all \(w_i(c)\) costs \(O(m\tau L^2)\), using multiplication and exact division on \(O(L)\)-bit integers.
• Prefix sums and interval minima cost \(O(m\tau^2L)\).
• The dynamic program costs \(O(R\tau^2L)\), hence \(O(k\tau^2L)\).

All finite dynamic-program values and candidate sums have \(O(L)\) bits: each is the cost of an assignment of at most \(\tau\) types.

The total running time is therefore \(O(m\tau L^2+(m+k)\tau^2L)\) bit operations. Storing the prefix sums, interval minima, dynamic-program values, and reconstruction choices requires \(O((m\tau+\tau^2+k\tau)L)\) bits.

For the decision version, \(DB=Dh/g\) is an integer. Comparing \(V\) with \(DB\) decides whether the optimum is at most \(B\), within the same running-time bound.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The argument establishes an exact polynomial-time algorithm for the stated input model, including positive rational masses, negative costs, cost ties, and a rational decision threshold. I found no major or minor issues.

• Contiguous-block argument.

For each distinct pair of candidates, single-crossing in the supplied order means that their relative preference changes at most once. Thus the types preferring one candidate to the other form a prefix or suffix, including the empty and full sets.

For a fixed nonempty committee \(W\), strict rankings give each type a unique highest-ranked committee member \(t_W(i)\). The stated cost monotonicity implies
\[ \rho_i(t_W(i))\leq \rho_i(c) \]
for every \(c\in W\). Multiplication by the positive mass \(\mu_i\) preserves this inequality, so the simultaneous replacements cannot increase total cost. Cost ties do not invalidate this choice.

The expression for \(I_c\) is correct: a candidate is highest-ranked within \(W\) exactly when it is preferred to every other committee member. An intersection of prefixes and suffixes is an interval or is empty. The singleton-committee case is explicitly covered.

Consequently, the nonempty \(I_c\) form a partition into at most \(|W|\) contiguous blocks. Existence of an optimum follows from the finite, nonempty feasible set. Replacing representatives in an optimum therefore establishes the claimed contiguous-block lemma.

The converse is also valid. Any block assignment with at most \(k\) blocks yields a feasible committee by taking the union of the assigned candidates. Repeated candidates are permitted and cannot increase committee size. Hence optimizing over these block assignments gives exactly the original optimum.

• Integer scaling and bit lengths.

The product defining \(D\) contains both denominator factors for every product \(\mu_i\rho_i(c)\). Therefore \(q_i b_{ic}\) divides \(D\), even when denominators share factors, and every \(w_i(c)\) is an integer. Including \(g\) makes \(DB\) integral as well.

The bit-length assertions are valid. The aggregate input length bounds the sum of denominator lengths, giving \(D\) at most \(O(L)\) bits. Multiplying by the relevant input numerators still gives \(O(L)\)-bit weights. Summing at most \(\tau\) such weights adds at most \(O(\log\tau)\) bits, which is absorbed into \(O(L)\) because the input explicitly lists all support types.

Signed numerators and negative costs cause no problem: scaling uses a positive integer and preserves objective comparisons.

• Dynamic program and boundary cases.

Prefix-sum subtraction correctly computes each candidate’s cost on an interval, and taking its minimum computes \(H(\ell,j)\). A minimizing candidate exists because \(m\geq1\).

The states and initialization correctly describe partitions into exactly \(r\) nonempty blocks. In particular, \(F(0,r)\) is infeasible for positive \(r\) under the rule \(j<r\). For \(r=1\), only the term with \(s=0\) has a feasible zero-block prefix.

Every partition has a unique final block beginning after some split \(s\) in the specified range. Its prefix and last-block costs satisfy the stated lower bounds. Conversely, a finite recurrence term combines attaining choices into a valid partition. No requirement that block representatives be distinct is needed.

Taking the minimum over \(1\leq r\leq\min(k,\tau)\) handles the nonempty-committee requirement, \(\tau=1\), \(k=1\), and \(k>\tau\). Backtracking returns a feasible committee and representatives.

• Correctness, running time, and decision version.

Both inequalities comparing \(V\) with \(D\,\mathrm{OPT}\) follow from the established equivalence of feasible block assignments and the existence of an optimal block assignment. Thus \(V=D\,\mathrm{OPT}\).

The claimed schoolbook-arithmetic bounds are justified. Constructing \(D\) costs \(O(L^2)\); computing the weights costs \(O(m\tau L^2)\); interval preprocessing costs \(O(m\tau^2L)\); and the dynamic program costs \(O(k\tau^2L)\). All finite values manipulated have \(O(L)\) bits. The stated storage bound also accommodates reconstruction indices.

Comparing \(V\) with the integer \(DB\) correctly decides the threshold question within the same time bound. No expansion into individual voters or reliance on unit-cost rational arithmetic occurs.

Repair feedback: None required. The write-up resolves the assigned optimization and decision questions.

⟨structured verdict parsed — rendered above⟩