d4-conf-ecai-2012-0131 (d4-conf-ecai-2012-0131)

Given candidates \(C\), a support \(T\) of \(\tau\) complete rankings with positive binary-rational masses \(\lambda_t\) summing to \(1\), committee size \(\kappa\), a nondecreasing misrepresentation function \(g\), and a compatible ordered candidate partition \((C_1,\ldots,C_q)\) of width \(w=\max_i |C_i|-1\), compute a committee \(S\subseteq C\) of size \(\kappa\) minimizing \(\sum_{t\in T}\lambda_t\min_{c\in S} g(r_t(c))\). For fixed \(w\), can this be done in time polynomial in \(m\), \(\tau\), and the input bit length \(L\)?

Let \(C\) contain \(m\geq1\) candidates and let \(1\leq\kappa\leq m\). A society is given by its support: a list \(T\) of \(\tau\) distinct strict complete rankings with positive binary-rational masses \(\lambda_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings.
Let \(r_t(c)\) be the position of \(c\) in ranking \(t\), with position \(1\) best. The input includes a nondecreasing table \(g:\{1,\ldots,m\}\to\mathbb Z_{\geq0}\), encoded in binary.
The input also supplies an ordered partition \((C_1,\ldots,C_q)\) into nonempty clusters. Compatibility means that each cluster is consecutive in every ranking and that contracting each cluster to one alternative yields rankings single-peaked on the axis \((C_1,\ldots,C_q)\); orders within clusters are unrestricted. Its width is \(w=\max_i|C_i|-1\).
The optimization problem is to compute a committee \(S\subseteq C\), \(|S|=\kappa\), minimizing \(\sum_{t\in T}\lambda_t\min_{c\in S}g(r_t(c))\). Any minimizing committee is acceptable. Let \(L\) be the total input bit length.

For every fixed \(w\), is this problem solvable in time polynomial in \(m,\tau,\kappa,L\), or is it NP-hard for some fixed \(w\)?

For finitely many unit-weight voters, this optimization problem with a supplied compatible partition is polynomial-time solvable when the width is bounded. [Cornaz, Galand, and Spanjaard](https://scispace.com/pdf/bounded-single-peaked-width-and-proportional-representation-27m61i6jq2.pdf)
No result explicitly treating this rational-mass input model was located in the literature search.

Result

For every fixed \(w\), the problem is polynomial-time solvable in \(m,\tau,\kappa,L\).

The dynamic program in Section 3 of [Cornaz, Galand, and Spanjaard](https://scispace.com/pdf/bounded-single-peaked-width-and-proportional-representation-27m61i6jq2.pdf) extends to the rational-mass model. Below is a self-contained proof, including the bit-complexity argument. No expansion into individual voters is needed.

1. Exact integer scaling

Write each input mass as \(\lambda_t=a_t/b_t\), where \(a_t,b_t\) are positive integers represented in binary. Define

\(Q=\prod_{t\in T}b_t,\qquad h_t=a_t(Q/b_t).\)

Then \(h_t\) is a positive integer and \(\sum_{t\in T}h_t=Q\). For every nonempty committee \(S\), define its scaled cost by

\(F(S)=\sum_{t\in T}h_t\min_{c\in S}g(r_t(c)).\)

This is exactly \(Q\) times the original objective. Thus both objectives have the same minimizing committees.

For each ranking \(t\), let \(p_t\) be the index of its most preferred cluster. Compatibility implies:

• If \(u<v\leq p_t\), every candidate in \(C_v\) is preferred to every candidate in \(C_u\).
• If \(p_t\leq u<v\), every candidate in \(C_u\) is preferred to every candidate in \(C_v\).

Indeed, the contracted ranking is single-peaked, and each cluster occupies a consecutive block in the original ranking.

For a nonempty candidate set \(A\), write

\(d_t(A)=\min_{c\in A}g(r_t(c)).\)

Because \(g\) is nondecreasing, whenever every candidate in \(A\) is preferred to every candidate in \(B\), we have \(d_t(A)\leq d_t(B)\). This permits ties in the values of \(g\).

2. The key marginal-cost identity

Lemma. Suppose \(j<i\), \(\varnothing\neq B\subseteq C_j\), and \(\varnothing\neq A\subseteq C_i\). Let \(U\) be any committee satisfying

\(U\subseteq C_1\cup\cdots\cup C_j,\qquad U\cap C_j=B.\)

Define

\(\Delta(j,B;i,A)=\sum_{t\in T}h_t\max\{0,d_t(B)-d_t(A)\}.\)

Then

\(F(U\cup A)=F(U)-\Delta(j,B;i,A).\)

In particular, the improvement from adding \(A\) depends only on \(A\) and the selected subset \(B\) of the previous rightmost selected cluster.

Proof. Fix a ranking \(t\). There are two cases.

If \(p_t<j\), then \(p_t<j<i\), so every candidate in \(B\) is preferred to every candidate in \(A\). Consequently,

\(d_t(U)\leq d_t(B)\leq d_t(A).\)

Adding \(A\) leaves this ranking’s cost unchanged. Also, \(\max\{0,d_t(B)-d_t(A)\}=0\).

If \(p_t\geq j\), every candidate in \(C_j\) is preferred to every candidate in a cluster strictly to its left. Since \(U\cap C_j=B\), it follows that

\(d_t(U)=d_t(B).\)

Therefore,

\(d_t(U)-d_t(U\cup A)=d_t(B)-\min\{d_t(B),d_t(A)\}=\max\{0,d_t(B)-d_t(A)\}.\)

The asserted identity follows by multiplying each ranking’s identity by \(h_t\) and summing over \(T\). \(\square\)

3. Dynamic program and correctness

For each cluster \(C_i\), enumerate its nonempty subsets \(A\) with \(|A|\leq\kappa\). For each such subset and each \(1\leq k\leq\kappa\), define

\(Z(i,A,k)=\min\{F(S):S\subseteq C_1\cup\cdots\cup C_i,\ S\cap C_i=A,\ |S|=k\}.\)

An infeasible state has value \(+\infty\).

If \(k=|A|\), the only feasible committee is \(A\), so

\(Z(i,A,|A|)=F(A).\)

States with \(k<|A|\) are infeasible. For \(k>|A|\), use the recurrence

\(\displaystyle Z(i,A,k)=\min_{\substack{1\leq j<i\\ \varnothing\neq B\subseteq C_j\\ |B|\leq\kappa}}\bigl\{Z(j,B,k-|A|)-\Delta(j,B;i,A)\bigr\},\)

where infeasible predecessor states are omitted, and an empty minimum is \(+\infty\).

Proof of the recurrence. Let \(S\) be any feasible committee for \(Z(i,A,k)\), with \(k>|A|\). Then \(U=S\setminus A\) is nonempty. Let \(j<i\) be its rightmost selected cluster, and put \(B=U\cap C_j\). Thus \(U\) is feasible for \(Z(j,B,k-|A|)\).

By the lemma,

\(F(S)=F(U)-\Delta(j,B;i,A)\geq Z(j,B,k-|A|)-\Delta(j,B;i,A).\)

Hence the recurrence’s right-hand side is a lower bound on the optimum defining \(Z(i,A,k)\).

Conversely, take any feasible predecessor state and a committee \(U\) attaining its value. The committee \(U\cup A\) is feasible for \(Z(i,A,k)\). The lemma gives

\(F(U\cup A)=Z(j,B,k-|A|)-\Delta(j,B;i,A).\)

Thus every finite expression in the recurrence is attained by a feasible committee. This proves equality. \(\square\)

Compute states in increasing order of \(i\), since every predecessor has a smaller cluster index. Every committee of size \(\kappa\) has a unique rightmost selected cluster \(C_i\) and a nonempty intersection \(A\) with that cluster. Consequently, the optimum scaled cost is

\(\displaystyle \min_{\substack{1\leq i\leq q\\ \varnothing\neq A\subseteq C_i\\ |A|\leq\kappa}}Z(i,A,\kappa).\)

Store an attaining predecessor for each finite state. Backtracking from an attaining final state reconstructs an optimal committee: successive subsets belong to distinct clusters, and their cardinalities sum to \(\kappa\).

4. Polynomial bit complexity

Let \(b=w+1\), so every cluster has at most \(b\) candidates. Each cluster has at most \(2^b-1\) nonempty subsets. Therefore there are at most

\(q(2^b-1)\kappa\)

states and at most

\(q^2(2^b-1)^2\kappa\)

predecessor evaluations.

First construct all rank positions. Then precompute every \(d_t(A)\). Direct enumeration requires at most

\(\displaystyle O\!\left(\tau\sum_{i=1}^q |C_i|2^{|C_i|}\right)=O(\tau m2^b)\)

operations. Precomputing all \(\Delta(j,B;i,A)\) requires \(O(\tau q^2 2^{2b})\) arithmetic operations. Once these are available, evaluating the recurrence requires \(O(\kappa q^2 2^{2b})\) arithmetic operations. Thus the total is bounded by

\(O\!\left(\tau m2^b+(\tau+\kappa)q^2 2^{2b}\right)\)

arithmetic operations, in addition to polynomial-time input processing and scaling.

It remains to bound the lengths of the integers involved. The binary length of \(Q\) is at most a constant plus the sum of the binary lengths of the input denominators, hence \(O(L)\). Since the positive masses sum to one, each \(h_t\leq Q\).

Let \(G=g(m)\). Nonnegativity and monotonicity give, for every nonempty committee \(S\),

\(0\leq F(S)\leq QG.\)

Likewise,

\(0\leq\Delta(j,B;i,A)\leq QG.\)

The binary length of \(G\) is \(O(L)\), so these values have \(O(L)\) bits. Every finite DP value is a committee cost, by the correctness proof. Intermediate products and partial sums used to compute costs and improvements also remain bounded by \(QG\). The sentinel \(+\infty\) can be stored separately.

Computing \(Q\), the integers \(h_t\), and all subsequent arithmetic therefore takes polynomial time in their encoding lengths. Since \(q\leq m\) and \(b=w+1\) is fixed, the complete algorithm runs in time polynomial in \(m,\tau,\kappa,L\).

5. Conclusion and verification

The rational-mass input model preserves the bounded-width tractability result. The essential reason is that the marginal-cost identity holds separately for each ranking, so arbitrary positive rational weights preserve it.

As an additional check, an implementation of the recurrence matched exhaustive enumeration for all \(4901\) feasible states across \(250\) randomly generated compatible profiles with at most eight candidates. These checks included flat portions of \(g\) and large rational denominators; the proof above establishes correctness for all promised inputs.

⟨structured verdict parsed — rendered above⟩

Assessment: proved. The output resolves the assigned rational-mass problem for every fixed \(w\). The marginal-cost identity, dynamic program, reconstruction, and bit-complexity argument are correct. No mathematical repair is required.

• Scope and assumptions. The proof uses the supplied compatible ordered partition and the given nondecreasing, nonnegative table \(g\). It allows unrestricted orders within clusters and does not replace the support size \(\tau\) by an expanded voter count. Its conclusion matches USER_TASK.

• Exact scaling. Every denominator divides \(Q\), so every \(h_t\) is a positive integer. The normalization of the masses gives \(\sum_t h_t=Q\). Consequently, \(F(S)\) is exactly \(Q\) times the original objective for every nonempty committee. Scaling therefore preserves all minimizing committees, including ties.

• Consequences of compatibility. The two stated cluster-preference implications correctly express monotonicity on either side of the peak of the contracted ranking. Consecutiveness of each cluster transfers these comparisons to every pair of candidates in the respective clusters. Nondecreasing \(g\) transfers strict preference comparisons to weak cost comparisons; strict increase of \(g\) is unnecessary.

• Marginal-cost identity. The two cases are exhaustive and include the boundary \(p_t=j\).

• When \(p_t<j\), all candidates in \(B\) precede all candidates in \(A\). Thus \(d_t(U)\leq d_t(B)\leq d_t(A)\), and both the actual improvement and the proposed improvement are zero.
• When \(p_t\geq j\), every candidate in \(C_j\) precedes every candidate in a cluster to its left. Since the selected candidates in \(C_j\) are exactly \(B\), the equality \(d_t(U)=d_t(B)\) follows. The displayed minimum/maximum identity then gives exactly the improvement from adding \(A\).

Multiplication by \(h_t\) and summation preserve these identities. The lemma therefore justifies retaining only the previous rightmost selected subset in a transition.

• Dynamic-programming states and initialization. The state definition records exactly the committee size and the selected subset of its rightmost cluster. When \(k=|A|\), the only feasible committee is \(A\). States with \(k<|A|\) are correctly declared infeasible. States with insufficient candidates in preceding clusters also become infeasible through the recurrence’s empty-minimum convention.

• Recurrence and correctness. Every feasible committee with \(k>|A|\) has a nonempty remainder and a unique rightmost selected predecessor cluster. Its remainder satisfies the predecessor-state definition, so the lemma supplies the claimed lower bound. Conversely, a committee attaining any finite predecessor value exists because the feasible family is finite. Its union with \(A\) has the required intersection and cardinality, and attains the corresponding transition value. These two directions prove equality. Increasing cluster index is a valid evaluation order.

• Final minimization and reconstruction. Every committee of size \(\kappa\) belongs to one of the final states. At least one such committee exists because \(1\leq\kappa\leq m\). Backtracking strictly decreases the cluster index and removes the recorded subset size at each transition, terminating at a base state. The reconstructed subsets are disjoint and total exactly \(\kappa\) candidates.

• Operation counts. The subset, state, and transition counts are valid upper bounds. The bound for computing all \(d_t(A)\) follows from \(|C_i|\leq b\) and \(\sum_i|C_i|=m\). Computing each improvement requires one sum over the support, giving the stated dependence on \(\tau\). Computing base costs fits within the stated overall bound. For fixed \(b=w+1\), all counts are polynomial in the required parameters.

• Bit complexity. The denominator product has \(O(L)\) bits even though its numerical value may be exponential in \(L\). Normalization gives \(h_t\leq Q\). The bounds \(0\leq F(S)\leq QG\) and \(0\leq\Delta(j,B;i,A)\leq QG\) are correct. Nonnegative summands ensure that intermediate cost and improvement sums obey the same bounds. Every finite transition value is an attained committee cost, so subtraction causes neither negative costs nor larger stored values. Exact arithmetic and scaling therefore take polynomial bit time. The case \(G=0\) presents no exception.

• Boundary cases. The argument covers a single candidate, a single cluster, singleton clusters, \(\kappa=1\), \(\kappa=m\), constant \(g\), and peaks at either endpoint. None requires an additional mathematical argument.

• Citation and experimental claim. Section 3 of the [cited paper](https://scispace.com/pdf/bounded-single-peaked-width-and-proportional-representation-27m61i6jq2.pdf) contains the corresponding subset-state dynamic program, so the attribution is consistent. The submitted proof independently establishes the weighted extension. The reported random-testing totals cannot be independently verified without code and test artifacts; they receive no evidentiary weight in this assessment and are unnecessary for the conclusion.

Actionable feedback: No clarification is needed to verify the mathematical result. If the prover wants the experimental claim independently audited, it should provide the implementation, profile generator, and reproducible test record.

⟨structured verdict parsed — rendered above⟩