Answer: Polynomial-time solvable: \(O(\tau m k)\) arithmetic operations and \(O(\tau m k L^2)\) bit operations for binary-rational table input.
Theorem 4.4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any polynomial-time computable dissatis- faction function, every positive integer k, and for both util- itarian and egalitarian versions of the Chamberlin-Courant rule, there is a polynomial-time algorithm that given a pro- file P = (P1, . . . , Pn) over a set of alternatives A = {a1, . . . , am}, which is single-crossing with respect to some tree, finds an optimal k-assignment function wopt for P.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(A\), an integer \(k\), distinct ranking types \(T\) with positive binary-rational masses \(\mu_t\) summing to \(1\), a tree \(H\) on \(T\) such that for every candidate pair each preference side is connected in \(H\), and a common polynomial-time-computable rational positional dissatisfaction function \(\rho\), find a committee \(S\subseteq A\) with \(|S|\le k\) and allocations \(x_{t,c}\ge 0\), zero for \(c\notin S\), with \(\sum_{c\in S}x_{t,c}=\mu_t\), minimizing \(\sum_{t\in T}\sum_{c\in S}x_{t,c}\rho(\operatorname{pos}_t(c))\).
Let \(A\) contain \(m\ge1\) candidates and let \(1\le k\le m\) be an input integer. A society is given by its support: a list \(T\) of \(\tau\ge1\) distinct strict rankings, 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 tree \(H\) on \(T\) is supplied. For every distinct \(a,b\in A\), both \(\{t:a\succ_t b\}\) and \(\{t:b\succ_t a\}\) induce connected subtrees when nonempty.
The common positional dissatisfaction function is polynomial-time computable and rational-valued, with \(0=\rho(1)\le\rho(2)\le\cdots\le\rho(m)\); \(\operatorname{pos}_t(c)\) counts positions from the top, starting at \(1\). Its values may be supplied as a binary-rational table.
Find \(S\subseteq A\), \(1\le|S|\le k\), and divisible allocations \(x_{t,c}\in\mathbb R_{\ge0}\), with \(x_{t,c}=0\) for \(c\notin S\) and \(\sum_{c\in S}x_{t,c}=\mu_t\), minimizing \(\sum_{t\in T}\sum_{c\in S}x_{t,c}\rho(\operatorname{pos}_t(c))\). There are no representative capacities; any optimum is acceptable when costs tie.
Let \(L\) be the total binary input length, including dissatisfaction values. State running times in \(m,\tau,k,L\).
Is this continuous utilitarian Chamberlin–Courant optimization problem solvable in time polynomial in \(m,\tau,k,L\), or is it NP-hard?
For discrete voters single-crossing on a tree, polynomial-time winner determination was asserted for both utilitarian and egalitarian dissatisfaction by [Clearwater, Puppe and Slinko (2015)](https://www.ijcai.org/Proceedings/15/Papers/012.pdf).
[Constantinescu and Elkind (2021)](https://cdn.aaai.org/ojs/16667/16667-13-20161-1-2-20210518.pdf) identify an error in that running-time argument and establish an \(O(nmk)\) algorithm for the discrete utilitarian problem with preference-consistent rational costs, counting arithmetic operations at unit cost. Neither cited result explicitly formulates the divisible-mass problem above.
The problem is polynomial-time solvable. With dissatisfaction values supplied as a binary-rational table, a valid bound is \(O(\tau m k L^2)\) bit operations. The underlying winner-determination algorithm uses \(O(\tau m k)\) arithmetic operations.
Write \(d_t(c)=\rho(\operatorname{pos}_t(c))\). Fix any nonempty committee \(S\subseteq A\), and let \(b_S(t)\) be the most preferred member of \(S\) in ranking \(t\). Monotonicity of \(\rho\) implies \(d_t(b_S(t))\le d_t(c)\) for every \(c\in S\).
Consequently, every feasible allocation to \(S\) satisfies
\[ \sum_{c\in S}x_{t,c}d_t(c) \ge d_t(b_S(t))\sum_{c\in S}x_{t,c} =\mu_t d_t(b_S(t)). \]
Equality is attained by assigning all mass \(\mu_t\) to \(b_S(t)\). Thus the optimum for committee \(S\) is exactly
\[ F(S)=\sum_{t\in T}\mu_t\rho(\operatorname{pos}_t(b_S(t))). \]
In particular, an optimum exists: there are finitely many eligible committees, and each committee admits the allocation just described. Cost ties cause no difficulty because choosing the most preferred representative always attains minimum cost.
We use the following established result.
Constantinescu–Elkind theorem. Given \(n\) voters, \(m\) candidates, a supplied tree on which their strict preferences are single-crossing, and rational costs \(q(v,c)\) satisfying \(a\succ_v b\Rightarrow q(v,a)\le q(v,b)\), one can find an assignment \(w\) minimizing \(\sum_v q(v,w(v))\), subject to \(|w(V)|\le k\), in \(O(nmk)\) arithmetic operations. This is Theorem 6, with the cost and assignment definitions from Section 2, of [Constantinescu and Elkind (2021)](https://cdn.aaai.org/ojs/16667/16667-13-20161-1-2-20210518.pdf).
Construct an instance with one voter for each support ranking, and set
\[ q(t,c)=\mu_t\rho(\operatorname{pos}_t(c)). \]
All hypotheses hold:
To verify exact equivalence, let \(U\) be the continuous optimum and \(D_{\mathrm{opt}}\) the discrete optimum.
For any eligible committee \(S\), the assignment \(w(t)=b_S(t)\) uses at most \(k\) candidates and has discrete cost \(F(S)\). Therefore \(D_{\mathrm{opt}}\le U\).
Conversely, any eligible discrete assignment \(w\) gives a feasible continuous solution by taking \(S=w(T)\), assigning \(x_{t,w(t)}=\mu_t\), and setting all other allocations to zero. Its continuous cost equals \(\sum_t q(t,w(t))\). Therefore \(U\le D_{\mathrm{opt}}\).
Thus \(U=D_{\mathrm{opt}}\). The theorem computes the required solution using \(O(\tau m k)\) arithmetic operations, without expanding rational masses into repeated voters.
We now justify that these arithmetic operations have polynomial bit cost.
Write the input rationals as \(\mu_t=p_t/u_t\) and \(\rho(j)=r_j/v_j\), with positive integer denominators. Define
\[ B=\left(\prod_{t\in T}u_t\right)\left(\prod_{j=1}^{m}v_j\right). \]
The binary length of \(B\) is \(O(L)\), since the sum of the binary lengths of its factors is at most \(L\). For every \(t,c\), the scaled cost
\[ Q(t,c)=Bq(t,c) =p_t r_{\operatorname{pos}_t(c)} \frac{B}{u_t v_{\operatorname{pos}_t(c)}} \]
is a nonnegative integer. Multiplication by the common positive factor \(B\) preserves every comparison of objective values and preserves preference consistency.
Using schoolbook integer arithmetic, constructing \(B\) and all scaled costs takes \(O(\tau m L^2)\) bit operations. Inverse ranking tables supply all positions in \(O(\tau m)\) elementary operations.
The cited dynamic program initializes entries with individual costs and computes further entries by additions and minima, merging disjoint vertex sets. Consequently, every finite entry is the cost of assigning one representative to each vertex of some subset \(U\subseteq T\). This follows inductively from its initialization and merging recurrences in [Section 4.1](https://cdn.aaai.org/ojs/16667/16667-13-20161-1-2-20210518.pdf).
Such an entry satisfies
\[ 0\le \sum_{t\in U}Q(t,w(t)) =B\sum_{t\in U}\mu_t\rho(\operatorname{pos}_t(w(t))) \le B\rho(m), \]
because all costs are nonnegative, \(\rho(\operatorname{pos}_t(w(t)))\le\rho(m)\), and \(\sum_{t\in U}\mu_t\le1\).
The integer bound \(B\rho(m)\) has \(O(L)\) bits. Therefore every finite table value has \(O(L)\) bits; infeasibility can be represented by a separate infinity flag. Additions and comparisons each take \(O(L)\) bit operations.
Including preprocessing and assignment reconstruction, the resulting bound is
\[ O(\tau m L^2+\tau m k L) \subseteq O(\tau m k L^2). \]
Recording a minimizing transition at each table entry permits reconstruction of an optimal assignment. Set \(S=w(T)\) and \(x_{t,w(t)}=\mu_t\); this explicitly returns an optimal committee and allocation.
If dissatisfaction values are evaluated by an algorithm instead of supplied as a table, add the time needed to evaluate \(\rho(1),\ldots,\rho(m)\). Under the stated polynomial-time computability assumption, this remains polynomial.
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly. The reduction preserves the optimum, the cited theorem applies to the constructed costs, and the claimed polynomial bit bound is justified for table input. No major or minor mathematical issues were found.
The definition \(d_t(c)=\rho(\operatorname{pos}_t(c))\) is consistent with the task.
For a nonempty committee \(S\), strict rankings ensure that \(b_S(t)\) exists and is unique. Monotonicity of \(\rho\) gives \(d_t(b_S(t))\le d_t(c)\) for every \(c\in S\), even when dissatisfaction values tie.
The displayed allocation inequality is valid: each allocation is nonnegative, and its total at ranking \(t\) is exactly \(\mu_t\). Assigning the entire mass to \(b_S(t)\) attains the lower bound and satisfies every allocation constraint. Thus the formula for \(F(S)\) is exact.
The existence argument also holds. There are finitely many nonempty committees of size at most \(k\), and each has an attained minimum. No compactness argument or assumption about rational optimal allocations is needed.
The theorem attribution was checked against the linked paper. Section 2 permits voter-specific rational misrepresentation costs satisfying weak preference consistency, defines assignments with at most \(k\) representatives, and assumes unit-cost arithmetic. Theorem 6 establishes the stated tree algorithm bound. Section 4.1 also explicitly provides for solution recovery. The prover’s formulation is therefore a faithful combination of the theorem and its definitions. [Constantinescu and Elkind (2021)](https://cdn.aaai.org/ojs/16667/16667-13-20161-1-2-20210518.pdf)
All required hypotheses are verified:
The theorem does not require the constructed costs to remain a common positional function. Its permission for voter-specific costs is essential here and is correctly stated.
Both inequalities are valid.
For each continuous committee \(S\), the assignment \(w(t)=b_S(t)\) uses at most \(k\) representatives and has cost \(F(S)\). Together with Section 1, this establishes \(D_{\mathrm{opt}}\le U\).
Conversely, any eligible discrete assignment produces the continuous solution specified in the write-up, with identical objective value. Since \(T\) is nonempty, \(w(T)\) is nonempty; hence the resulting committee satisfies the lower size bound as well as the upper bound. This establishes \(U\le D_{\mathrm{opt}}\).
Consequently, the equality of optima and the proposed output reconstruction follow. There is no expansion of masses into repeated voters.
The denominator product \(B\) is positive and has \(O(L)\) bits. Its definition includes the denominator factors needed for every product \(\mu_t\rho(j)\), so \(B/(u_tv_j)\) is an integer. This remains true when different denominators share factors or have equal numerical values.
The formula for \(Q(t,c)\) is therefore an exact nonnegative integer scaling. Scaling by \(B>0\) preserves objective comparisons and preference consistency.
The numerator factors and the denominator product each have \(O(L)\) bits. Schoolbook multiplication and exact division consequently justify the stated preprocessing bound \(O(\tau mL^2)\). Inverse ranking construction fits within that bound.
The cited recurrence was checked. Its initial values are individual costs, its merges add costs on disjoint vertex sets, and its remaining operations take minima or copy entries. Thus the prover’s induction that every finite value is an assignment cost on a subset of vertices is valid. Reconstruction uses stored minimizing transitions. [Section 4.1 of the cited paper](https://cdn.aaai.org/ojs/16667/16667-13-20161-1-2-20210518.pdf)
The bound
\(0\le\sum_{t\in U}Q(t,w(t))\le B\rho(m)\)
correctly uses nonnegativity, positional monotonicity, and \(\sum_{t\in U}\mu_t\le1\). It applies to finite merge candidates as well as stored minima.
Because \(B\rho(m)\) has \(O(L)\) bits, additions and comparisons cost \(O(L)\) bit operations. A separate infinity flag avoids any arithmetic ambiguity.
Combining preprocessing and the dynamic program gives the claimed
\(O(\tau mL^2+\tau mkL)\), hence \(O(\tau mkL^2)\), bound. Assignment recovery and writing the requested allocation fit within it.
The argument covers \(m=1\), \(\tau=1\), \(k=1\), \(k=m\), and identically zero dissatisfaction. Tied costs do not invalidate either the reduction or the theorem application.
The explicit bit bound is appropriately restricted to table input. For algorithmically evaluated dissatisfaction, the output separately includes evaluation time and claims polynomiality under the task’s polynomial-time computability assumption.
No additional clarification is needed to verify the mathematical conclusion.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.