d4-conf-aaai-2021-1873 (d4-conf-aaai-2021-1873)

Given \(m\) unit-cost projects, an integer budget \(b\), and districts \(i\in[k]\) with approval-type masses \(\mu_{i,A}\in\mathbb{Q}_{\ge 0}\) summing to \(1\), let \(\alpha_i=\sum_A\mu_{i,A}\), \(v_i(W)=\sum_A\mu_{i,A}|A\cap W|\), and \(f_i=\max_{Q\subseteq P,\ |Q|\le\lfloor\alpha_i b\rfloor}v_i(Q)\). Given a rational threshold \(q\), decide whether there is a funded set \(W\subseteq P\) with \(|W|\le b\), \(v_i(W)\ge f_i\) for every district, and \(\sum_i v_i(W)\ge q\).

Let \(P\) be a set of \(m\ge1\) indivisible unit-cost projects, with \(k\ge1\) districts, an integer budget \(b\ge1\), and a threshold \(q\in\mathbb Q\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. A type is a pair \((i,A)\), where \(i\in\{1,\ldots,k\}\) and \(A\subseteq P\) is its approval set; omitted types have zero mass and \(\sum_{i,A}\mu_{i,A}=1\). Thus \(\tau\) is the support size, not the number of possible approval sets.
Define \(\alpha_i=\sum_A\mu_{i,A}\) and \(v_i(W)=\sum_A\mu_{i,A}|A\cap W|\). District \(i\) receives budget share \(\alpha_i b\) and has fairness benchmark \(f_i=\max_{Q\subseteq P,\ |Q|\le\lfloor\alpha_i b\rfloor}v_i(Q)\).
The decision problem asks whether some set \(W\subseteq P\) satisfies \(|W|\le b\), \(v_i(W)\ge f_i\) for every district, and \(\sum_i v_i(W)\ge q\). Let \(L\) be the total binary input length; state running times in \(m,\tau,k,L\).

Is this rational-mass district-fair welfare decision problem solvable in polynomial time, or is it NP-hard?

For finite voters, district-fair welfare threshold decision is NP-complete, even with unit-cost projects, one approval voter per district, and budgets proportional to district populations. [Source](https://arxiv.org/abs/2102.06115v1).

Result

The problem is \(\mathrm{NP}\)-complete, even when \(\tau=k\) and every district has exactly one supported type, of mass \(1/k\). Thus a polynomial-time algorithm exists only if \(\mathrm{P}=\mathrm{NP}\).

1. Fairness benchmarks and certificates are computable in polynomial time

For each district \(i\) and project \(p\), define its approval weight by
\(a_{i,p}=\sum_{A:p\in A}\mu_{i,A}\).
Interchanging the finite sums gives
\(v_i(W)=\sum_{p\in W}a_{i,p}\).

Let \(t_i=\min\{m,\lfloor\alpha_i b\rfloor\}\), and order the project weights as
\(a_{i,(1)}\ge\cdots\ge a_{i,(m)}\).
All weights are nonnegative, so
\(f_i=\sum_{j=1}^{t_i}a_{i,(j)}\).
Indeed, any selection of at most \(t_i\) projects has weight at most this sum, and selecting the first \(t_i\) projects attains it.

Here is an exact implementation with polynomial bit complexity. Write each mass as \(\mu_s=u_s/d_s\), and write \(q=c/e\), with positive denominators. Set
\(D=e\prod_{s=1}^{\tau}d_s\).
Its bit length is \(\mathrm{O}(L)\), because the denominator bit lengths are included in \(L\). Define the integer mass
\(M_s=u_sD/d_s\).
Then compute
\(C_i=\sum_{s:i_s=i}M_s\) and
\(S_{i,p}=\sum_{s:i_s=i,\ p\in A_s}M_s\).

These integers satisfy \(\alpha_i=C_i/D\) and \(a_{i,p}=S_{i,p}/D\). Consequently, compute
\(t_i=\min\{m,\lfloor bC_i/D\rfloor\}\), sort the integer project weights, and obtain \(F_i=Df_i\) by summing the largest \(t_i\).

Given a certificate \(W\subseteq P\), check its cardinality and the integer inequalities
\(\sum_{p\in W}S_{i,p}\ge F_i\) for each district, together with
\(\sum_i\sum_{p\in W}S_{i,p}\ge cD/e\).
These checks are exactly equivalent to the required rational inequalities.

Only districts occurring in the support need processing: every other district has \(\alpha_i=f_i=v_i(W)=0\). Put \(r\le\min\{k,\tau\}\) for the number of supported districts. Using elementary integer arithmetic, preprocessing and certificate verification take
\(\mathrm{O}\bigl((L+m\tau+rm\log(m+1))(L+\log(m+1))^2\bigr)\)
bit operations. In particular, the computation does not iterate up to the binary-encoded budget \(b\).

The explicitly listed project set gives a polynomial-size certificate. Therefore the decision problem belongs to \(\mathrm{NP}\).

2. A polynomial reduction from the finite-voter problem

We use the following known result: finite-voter district-fair welfare threshold decision is \(\mathrm{NP}\)-hard with unit-cost projects, one approval voter per district, and budget shares proportional to district populations. This is the restricted hardness statement of [Theorem 1 in Hershkowitz, Kahng, Peters, and Procaccia](https://arxiv.org/pdf/2102.06115v1).

Take an instance of that restricted problem. Write \(A_i\) for the approval set of the sole voter in district \(i\), and \(T\) for its welfare threshold. Its unnormalized district utility is
\(u_i(W)=|A_i\cap W|\).
Since all \(k\) districts have equal population, each district’s budget share is \(b/k\), and its benchmark is
\(g_i=\max_{|Q|\le\lfloor b/k\rfloor}|A_i\cap Q|\).

Construct the rational-mass instance by retaining the projects and budget, assigning
\(\mu_{i,A_i}=1/k\) for every district, omitting all other types, and setting \(q=T/k\).

All \(k\) masses are positive and sum to one. Thus \(\tau=k\), and
\(\alpha_i=1/k\),
\(v_i(W)=u_i(W)/k\), and
\(f_i=g_i/k\).
The last equality follows because both benchmark maximizations use exactly the same feasible subsets, and their objectives differ by the positive factor \(1/k\).

Consequently, for every \(W\),
\(v_i(W)\ge f_i\) if and only if \(u_i(W)\ge g_i\), and
\(\sum_i v_i(W)\ge q\) if and only if \(\sum_i u_i(W)\ge T\).
The budget condition is unchanged. The two instances therefore have identical yes/no answers.

The construction is polynomial: each mass \(1/k\) requires \(\mathrm{O}(\log(k+1))\) bits, the approval sets are copied, and encoding \(T/k\) adds only \(\mathrm{O}(\log(k+1))\) bits to the threshold representation. With approval bit vectors, the output length is
\(\mathrm{O}(mk+k\log(k+1)+\operatorname{bits}(b)+\operatorname{bits}(T))\).

This proves \(\mathrm{NP}\)-hardness under precisely the support encoding in the question.

3. Conclusion

Polynomial-time certificate verification and the answer-preserving reduction establish \(\mathrm{NP}\)-completeness. The hardness already holds for uniform rational masses and one supported approval type per district.

⟨structured verdict parsed — rendered above⟩

The prover’s argument establishes \(\mathrm{NP}\)-completeness for the decision problem in USER_TASK. Both the certificate verification and the reduction are sound. I found no major or minor mathematical issues.

• Additive project weights. The identity

\[ v_i(W)=\sum_{p\in W}a_{i,p} \]
follows by interchanging finite sums. The definition of \(a_{i,p}\) includes precisely the supported types in district \(i\) that approve \(p\); omitted types contribute zero.

• Fairness benchmarks. Because projects have unit cost, the benchmark permits at most \(\lfloor\alpha_i b\rfloor\) projects. Capping this number at \(m\) is correct. Nonnegativity of all project weights justifies taking the \(t_i\) largest weights, including when \(t_i=0\), weights tie, or some weights vanish. Thus the stated formula for \(f_i\) is exact.

• Exact integer implementation. The common denominator \(D\) is divisible by every mass denominator and the threshold denominator. Therefore \(M_s\), \(C_i\), \(S_{i,p}\), \(F_i\), and \(cD/e\) are integers with the claimed interpretations. Multiplication of each rational inequality by the positive integer \(D\) preserves its direction and makes the certificate checks exactly equivalent to the original constraints. A negative threshold causes no difficulty.

• Bit complexity and certificate size. The denominator product has bit length \(\mathrm{O}(L)\). Normalization bounds \(C_i\) and \(S_{i,p}\) by \(D\), while sums over projects require only an additional \(\mathrm{O}(\log(m+1))\) bits. Computing \(bC_i\) remains polynomial because the binary representation of \(b\) is included in \(L\). The displayed running-time bound is a valid conservative bound for elementary arithmetic, weight accumulation, sorting, and verification. Processing only the \(r\le\min\{k,\tau\}\) supported districts is justified: all other district constraints are identically satisfied. A project-set certificate has polynomial size under the explicit project encoding used in the write-up. Consequently, membership in \(\mathrm{NP}\) is established.

• Cited hardness theorem. Theorem 1 of the cited paper establishes hardness for the welfare-threshold decision problem with approval votes, proportional district budgets, one voter per district, and unit-cost projects. Its fairness benchmark is the utility achievable within each district’s budget share, matching the benchmark used in the reduction. Thus the source supplies the restriction the prover invokes. [Hershkowitz, Kahng, Peters, and Procaccia, Theorem 1](https://arxiv.org/pdf/2102.06115v1).

• Reduction and equivalence. With one voter in every district, proportional shares are \(b/k\). Assigning mass \(1/k\) to each district’s sole type produces a valid normalized support with \(\tau=k\), even if different districts share approval sets: their types remain distinct because the district index is part of the type. The identities

\[ \alpha_i=1/k,\qquad v_i(W)=u_i(W)/k,\qquad f_i=g_i/k \]
are correct. In particular, the benchmark domains coincide, including the floor operation. Scaling the threshold to \(T/k\) preserves the welfare inequality, and the budget constraint is unchanged. The equivalence holds for every \(W\), establishing both directions of the reduction.

• Polynomial construction and conclusion. Encoding the uniform masses and scaled threshold requires only polynomially many additional bits; copying approval sets is polynomial as well. The stated output-size estimate is valid for approval bit vectors. The reduction proves hardness under the required support encoding. Together with membership in \(\mathrm{NP}\), it establishes the claimed \(\mathrm{NP}\)-completeness.

No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩