Phragmén's Voting Methods and Justified Representation (d4-conf-aaai-2017-0255)

Given candidates \(C\), committee size \(k\), finite approval types \(t\in T\) with rational masses \(\mu_t>0\) summing to \(1\), a rational mass-normalized candidate-load scale \(\beta>0\), and threshold \(\alpha\), decide whether there exist \(y_c\in\{0,1\}\) with \(\sum_c y_c=k\) and mass-weighted loads \(z_{t,c}\) satisfying \(z_{t,c}=0\) for \(c\notin A_t\), \(0\leq z_{t,c}\leq\mu_t y_c\), \(\sum_t z_{t,c}=\beta y_c\), and \(\sum_t\mu_t\ell_t^2<\alpha\), where \(\ell_t=\mu_t^{-1}\sum_c z_{t,c}\).

Given a finite candidate set \(C\), approval types \(T\) with \(A_t\subseteq C\), rational masses \(\mu_t>0\) summing to \(1\), \(k\), \(\beta>0\), and \(\alpha\), select exactly \(k\) candidates via \(y_c\in\{0,1\}\). A selected candidate has aggregate load \(\beta\), distributable only to approving types: \(z_{t,c}=0\) if \(c\notin A_t\), \(0\le z_{t,c}\le\mu_t y_c\), and \(\sum_t z_{t,c}=\beta y_c\). Type \(t\)'s load is \(\ell_t=\mu_t^{-1}\sum_c z_{t,c}\).

Is deciding whether a feasible selection and load distribution satisfies \(\sum_t\mu_t\ell_t^2<\alpha\) NP-hard or in \(\mathrm{P}\)?

For finite individual voters, the corresponding var-Phragmén decision problem is NP-complete, even when each voter approves at most \(2\) candidates and each candidate is approved by at most \(3\) voters.

Conclusion

The problem is NP-hard, using the finite-voter hardness result supplied in the question. The upper bounds \(z_{t,c}\leq \mu_t y_c\) do not obstruct the reduction.

Source problem and construction

Let a finite-voter instance have voter set \(V\), with \(n=|V|>0\), candidate set \(C\), and approval sets \(A_v\). For a committee represented by \(y_c\), write \(x_{v,c}\geq 0\) for the load assigned to voter \(v\) by candidate \(c\). The finite-voter constraints are
\[ x_{v,c}=0\quad\text{if }c\notin A_v, \qquad \sum_{v\in V}x_{v,c}=y_c, \qquad \sum_{c\in C}y_c=k. \]
Define \(L_v=\sum_c x_{v,c}\). The corresponding decision question asks whether
\[ Q:=\sum_{v\in V}L_v^2<B. \]
We use the supplied NP-hardness premise for this finite-voter decision problem. If its objective is expressed as variance instead, the threshold translation is given below.

Nonnegativity and the candidate-load equality imply
\[ 0\leq x_{v,c}\leq y_c. \]

Partition voters into classes \(V_t\) having identical approval sets. Write \(n_t=|V_t|\) and let \(A_t\) be their common approval set. Construct the target instance with the same candidates and committee size, and set
\[ \mu_t=\frac{n_t}{n}, \qquad \beta=\frac1n, \qquad \alpha=\frac Bn. \]
These masses are positive and sum to \(1\). Grouping voters and producing these rational numbers takes polynomial time.

Proof of equivalence

From a finite-voter solution to a type solution

Given a feasible finite-voter solution, retain its committee and define
\[ z_{t,c}=\frac1n\sum_{v\in V_t}x_{v,c}. \]
Approval restrictions are preserved. Moreover,
\[ 0\leq z_{t,c} \leq \frac{n_t}{n}y_c =\mu_t y_c, \qquad \sum_t z_{t,c} =\frac1n\sum_v x_{v,c} =\beta y_c. \]
Thus the target solution is feasible.

Its type loads satisfy
\[ \ell_t =\frac1{\mu_t}\sum_c z_{t,c} =\frac1{n_t}\sum_{v\in V_t}L_v. \]
For each class, the inequality
\[ \left(\sum_{v\in V_t}L_v\right)^2 \leq n_t\sum_{v\in V_t}L_v^2 \]
follows from Cauchy–Schwarz. Consequently,
\[ \sum_t\mu_t\ell_t^2 =\frac1n\sum_t \frac{\left(\sum_{v\in V_t}L_v\right)^2}{n_t} \leq \frac Qn. \]
Hence \(Q<B\) implies \(\sum_t\mu_t\ell_t^2<\alpha\).

From a type solution to a finite-voter solution

Conversely, given a feasible target solution, retain its committee and assign every voter \(v\in V_t\) the load
\[ x_{v,c}=\frac{z_{t,c}}{\mu_t}. \]
These loads are nonnegative and respect approvals. For every candidate,
\[ \sum_{v\in V}x_{v,c} =\sum_t\frac{n_t}{\mu_t}z_{t,c} =n\sum_t z_{t,c} =n\beta y_c =y_c. \]
Therefore they form a feasible finite-voter distribution.

Every voter in class \(V_t\) has load \(L_v=\ell_t\), so
\[ Q=\sum_t n_t\ell_t^2 =n\sum_t\mu_t\ell_t^2. \]
Thus \(\sum_t\mu_t\ell_t^2<\alpha\) implies \(Q<B\).

Both directions preserve the strict decision threshold, proving the required polynomial-time reduction.

Variance normalization and inherited restrictions

If the finite-voter objective is population variance, the total voter load is \(k\), and therefore
\[ \frac1n\sum_v\left(L_v-\frac kn\right)^2 =\frac Qn-\left(\frac kn\right)^2. \]
A strict variance threshold \(b\) is consequently handled by choosing
\[ \alpha=b+\left(\frac kn\right)^2. \]
This is a rational, polynomial-time threshold transformation.

Finally, grouping identical voters preserves the supplied sparsity restrictions: every type approves at most \(2\) candidates, and every candidate is approved by at most \(3\) types. Thus NP-hardness holds even under these restrictions, with \(\beta=1/n\).

⟨structured verdict parsed — rendered above⟩

The output is correct and rigorous under the finite-voter hardness premise supplied in USER_TASK. It gives a polynomial-time many-one reduction and verifies both directions, including the per-type capacity bounds and strict threshold. No major or minor issues were found.

• Source problem. The prover uses the supplied hardness of the corresponding finite-voter decision problem, with unit aggregate load per selected candidate. Nonnegativity and \(\sum_v x_{v,c}=y_c\) indeed imply \(0\leq x_{v,c}\leq y_c\). Thus the bound used later does not add an assumption to the source problem.

• Construction and encoding. Each class contains at least one voter, so \(n_t>0\). Consequently, \(\mu_t=n_t/n>0\), \(\sum_t\mu_t=1\), and \(\beta=1/n>0\). The construction preserves the candidate set and committee size. Grouping explicitly represented voters takes polynomial time, and all constructed rational numbers have polynomial encoding length.

• Forward feasibility. The definition \(z_{t,c}=n^{-1}\sum_{v\in V_t}x_{v,c}\) preserves approval restrictions because all voters in a class have identical approvals. Summing the source bounds gives \(z_{t,c}\leq(n_t/n)y_c=\mu_t y_c\). Summing over types gives \(\sum_t z_{t,c}=y_c/n=\beta y_c\). All target feasibility constraints are satisfied.

• Forward objective bound. The identity \(\ell_t=n_t^{-1}\sum_{v\in V_t}L_v\) follows directly from the definitions. Cauchy–Schwarz applies to the finite vectors of loads and ones in each nonempty class, giving exactly the stated inequality. Therefore the target objective is at most \(Q/n\). Since \(n>0\), \(Q<B\) yields a target objective strictly below \(B/n=\alpha\). Averaging within classes does not compromise this implication.

• Reverse feasibility. Division by \(\mu_t\) is valid because every mass is positive. Identical approvals ensure that \(x_{v,c}=z_{t,c}/\mu_t\) respects each individual voter's approvals. The calculation \(n_t/\mu_t=n\) establishes \(\sum_v x_{v,c}=n\beta y_c=y_c\). Nonnegativity and the committee constraint are also preserved.

• Reverse objective equality. Every reconstructed voter in class \(V_t\) has total load \(\ell_t\). Hence \(Q=\sum_t n_t\ell_t^2=n\sum_t\mu_t\ell_t^2\). The strict target threshold therefore implies \(Q<B\). Together with the forward implication, this proves equivalence of the decision instances.

• Variance normalization. Summing the candidate-load equalities gives total voter load \(k\). Expanding population variance therefore gives \(Q/n-(k/n)^2\), exactly as stated. The proposed threshold \(\alpha=b+(k/n)^2\) is correct and polynomial-time computable for a rational source threshold.

• Restrictions and scope. Grouping preserves the bound of two approved candidates per type. A candidate approved by at most three individual voters belongs to at most three nonempty approval classes, so the claimed bound of three approving types also holds. Establishing hardness on instances with \(\beta=1/n\) suffices because \(\beta\) is part of the target input. The prover claims NP-hardness, so a separate proof of membership in NP is unnecessary.

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩