Answer: Both objectives are \(\mathrm{NP}\)-hard for every fixed rule pair in \(\{\mathrm{SAV},\mathrm{MSAV}\}^2\). Their rational-threshold decision versions are \(\mathrm{NP}\)-complete.
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateESWO/NSWO-WA-(f1, f2) where f1, f2 ∈ {SAV, MSAV} are NP-hard. This holds even when the two elections in the given double election are both VI and CI. Envy-Free Winners Allocations This section is devoted to the computation of envy-free win- ners allocations. The following corollary is a consequence of Theorems 1 and 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidate sets \(C_1,C_2\), committee sizes \(k_1,k_2\), community shares \(\alpha_1,\alpha_2\), and binary-rational distributions \(\mu_i\) over approval sets \(S\subseteq C_i\), choose disjoint committees \(w_i\subseteq C_i\) of sizes \(k_i\) maximizing either \(\min\{U_1(w_1),U_2(w_2)\}\) or \(U_1(w_1)U_2(w_2)\), where \(U_i(w_i)=\alpha_i\sum_S\mu_i(S)q_{f_i}(S,w_i)\) and \(f_i\in\{\mathrm{SAV},\mathrm{MSAV}\}\). What is the computational complexity of finding such an allocation as a function of the candidate counts, support sizes, and input bit length?
Let \(C_1,C_2\) be finite, possibly overlapping candidate sets, and write \(m=|C_1\cup C_2|\). Let \(k_1,k_2\) be nonnegative integers satisfying \(k_i\le |C_i|\) and \(k_1+k_2\le m\).
A society is given by its support: the list of the \(\tau_i\) approval types \(S\subseteq C_i\) with positive mass, each mass \(\mu_i(S)\) a binary rational, with \(\sum_S\mu_i(S)=1\). The support size \(\tau_i\) counts listed types, not all possible approval sets; put \(\tau=\tau_1+\tau_2\).
Community shares \(\alpha_1,\alpha_2\) are nonnegative binary rationals with \(\alpha_1+\alpha_2=1\). Each community uses a specified rule \(f_i\in\{\mathrm{SAV},\mathrm{MSAV}\}\).
Define \(q_{\mathrm{SAV}}(S,w)=|S\cap w|/|S|\) and \(q_{\mathrm{MSAV}}(S,w)=|S\cap w|/\min\{|S|,|w|\}\), taking either expression to be zero whenever its denominator is zero. Set \(U_i(w)=\alpha_i\sum_S\mu_i(S)q_{f_i}(S,w)\).
An allocation consists of ordinary, indivisible committees \(w_i\subseteq C_i\) with \(|w_i|=k_i\) and \(w_1\cap w_2=\varnothing\); candidates may remain unallocated. Any maximizing allocation is acceptable when there are ties.
For each fixed rule pair \((f_1,f_2)\), is finding an allocation maximizing \(\min\{U_1(w_1),U_2(w_2)\}\) polynomial-time solvable or NP-hard, and is finding one maximizing \(U_1(w_1)U_2(w_2)\) polynomial-time solvable or NP-hard? State running times in \(m,\tau,L,k_1,k_2\), where \(L\) is the total input bit length.
For explicit finite electorates, both optimization problems are NP-hard for every rule pair in \(\{\mathrm{SAV},\mathrm{MSAV}\}^2\). For weakly additive utilities, the discrete problems are fixed-parameter tractable in \(|C_1\cap C_2|\) and also in \(k_1+k_2\).
Both optimization problems are \(\mathrm{NP}\)-hard for every fixed rule pair. Their rational-threshold decision versions are \(\mathrm{NP}\)-complete.
| Rule pair | Maximize \(\min\{U_1,U_2\}\) | Maximize \(U_1U_2\) |
|---|---|---|
| \((\mathrm{SAV},\mathrm{SAV})\) | \(\mathrm{NP}\)-hard | \(\mathrm{NP}\)-hard |
| \((\mathrm{SAV},\mathrm{MSAV})\) | \(\mathrm{NP}\)-hard | \(\mathrm{NP}\)-hard |
| \((\mathrm{MSAV},\mathrm{SAV})\) | \(\mathrm{NP}\)-hard | \(\mathrm{NP}\)-hard |
| \((\mathrm{MSAV},\mathrm{MSAV})\) | \(\mathrm{NP}\)-hard | \(\mathrm{NP}\)-hard |
The hardness holds with identical candidate sets and societies, equal committee sizes and shares, and only singleton or empty approval types. All masses in the reduction are dyadic rationals.
There are also exact algorithms with running times exponential in either the overlap size or the total committee size, as proved below.
Write \(\displaystyle T=C_1\cap C_2,\quad t=|T|,\quad P_i=C_i\setminus T,\quad K=k_1+k_2.\)
The stated cardinality assumptions guarantee a feasible allocation. Indeed, community \(i\) needs at least \(\displaystyle x_i=\max\{0,k_i-|P_i|\}\) shared candidates.
We have \(x_i\le t\), because \(k_i\le |P_i|+t\). Also \(x_1+x_2\le t\): when both are positive, this follows from
\(\displaystyle x_1+x_2=K-|P_1|-|P_2|\le t\);
when at most one is positive, it follows from \(x_i\le t\).
Thus we can choose disjoint shared subsets of sizes \(x_1,x_2\), and fill each committee with \(k_i-x_i\) private candidates.
If either \(k_i=0\) or \(\alpha_i=0\), then \(U_i\) is identically zero on feasible allocations. Both objectives are consequently zero, and the preceding construction gives an optimum in polynomial time. The hardness proof concerns instances with positive committee sizes and shares.
Assume first that \(k_i>0\). For each listed approval type, define
\(\displaystyle d_i(S)=
\begin{cases}
|S|,&f_i=\mathrm{SAV},\\
\min\{|S|,k_i\},&f_i=\mathrm{MSAV}.
\end{cases}\)
For \(c\in C_i\), put
\(\displaystyle a_i(c)=\alpha_i\sum_{\substack{S\ni c\\d_i(S)>0}}\frac{\mu_i(S)}{d_i(S)}.\)
If \(k_i=0\), instead set every \(a_i(c)=0\).
For every committee of the required size, exchanging the finite sums gives
\(\displaystyle
U_i(w_i)
=\alpha_i\sum_{\substack{S\\d_i(S)>0}}
\frac{\mu_i(S)}{d_i(S)}
\sum_{c\in w_i}\mathbf{1}_{c\in S}
=\sum_{c\in w_i}a_i(c).
\)
For \(k_i=0\), both sides are zero, so the equality still holds. All candidate weights are nonnegative.
Both objectives are nondecreasing in each utility on the nonnegative quadrant. Therefore, any replacement that increases one community’s additive utility while leaving the other unchanged cannot worsen either objective. This observation will justify both exact algorithms.
Define
\(\displaystyle B=2+L+\tau\left\lceil\log_2(m+1)\right\rceil.\)
There is a common positive integer denominator \(D\) of bit length at most \(B\) for all candidate weights. To construct one, multiply:
The first two groups contribute at most \(L\) bits, and the last contributes at most \(\tau\lceil\log_2(m+1)\rceil\) bits.
Consequently,
\(\displaystyle A_i(c)=Da_i(c)\)
is a nonnegative integer. We can compare objectives exactly using
\(\displaystyle \min\left\{\sum_{c\in w_1}A_1(c),\sum_{c\in w_2}A_2(c)\right\}\)
or
\(\displaystyle
\left(\sum_{c\in w_1}A_1(c)\right)
\left(\sum_{c\in w_2}A_2(c)\right).
\)
For a feasible committee, \(U_i(w_i)\le1\), since every approval satisfaction lies between zero and one. Hence feasible scaled utility sums are at most \(D\), and their products are at most \(D^2\). Even sums over all candidates are at most \(mD\), so all arithmetic uses \(O(B)\)-bit integers.
Using ordinary quadratic-time integer arithmetic, computing the weights, sorting candidates by weight, and preparing prefix sums takes
\(\displaystyle O\!\left((m+1)(\tau+\log_2(m+2))B^2\right)\)
bit operations. There are at most \(m\tau\) candidate–type incidences to process.
We reduce from the standard \(\mathrm{NP}\)-complete problem PARTITION: given positive binary integers \(a_1,\ldots,a_n\), decide whether some subset has sum half their total. This classical hardness result appears in [Karp’s *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Let
\(\displaystyle A=\sum_{j=1}^n a_j.\)
Construct \(2n\) candidates with positive integer weights
\(\displaystyle b_j=1+a_j\quad(1\le j\le n),\qquad b_{n+j}=1\quad(1\le j\le n).\)
Their total weight is
\(\displaystyle W=\sum_{j=1}^{2n}b_j=A+2n.\)
A subset of exactly \(n\) candidates corresponds to a subset \(I\subseteq\{1,\ldots,n\}\) of the original candidates, together with \(n-|I|\) dummy candidates. Its weight is therefore
\(\displaystyle n+\sum_{j\in I}a_j.\)
Conversely, every original subset \(I\) can be completed in this way, because there are \(n\) dummy candidates. Thus
\(\displaystyle
\text{some $n\)-candidate subset has weight \(W/2\)}
\quad\Longleftrightarrow\quad
\text{the PARTITION instance is a yes-instance}.
\)
Let \(D\) be the smallest power of two strictly greater than \(W\). Set
\(\displaystyle C_1=C_2=\{c_1,\ldots,c_{2n}\},\qquad k_1=k_2=n,\qquad \alpha_1=\alpha_2=\frac12.\)
Use identical societies:
\(\displaystyle
\mu_i(\{c_j\})=\frac{b_j}{D}\quad(1\le j\le2n),
\qquad
\mu_i(\varnothing)=\frac{D-W}{D}.
\)
Every listed mass is positive, and their sum is
\(\displaystyle \frac{W}{D}+\frac{D-W}{D}=1.\)
All masses are dyadic rationals. Each society has \(2n+1\) listed types, so
\(\displaystyle m=2n,\qquad \tau=4n+2.\)
Because \(D\le2W\), the binary descriptions of these masses and of the thresholds below have polynomial length in the original input length. Thus this is a polynomial-time reduction in the required support representation.
For a singleton approval type and a committee of positive size, both rules give
\(\displaystyle
q_{\mathrm{SAV}}(\{c_j\},w)
=q_{\mathrm{MSAV}}(\{c_j\},w)
=\mathbf{1}_{c_j\in w}.
\)
The empty approval type contributes zero under both rules. Therefore, independently of the chosen rule pair,
\(\displaystyle U_i(w_i)=\frac{1}{2D}\sum_{c_j\in w_i}b_j.\)
The committees are disjoint and their sizes sum to \(2n\), so they exhaust the candidate set. If
\(\displaystyle s=\sum_{c_j\in w_1}b_j,\)
then
\(\displaystyle U_1=\frac{s}{2D},\qquad U_2=\frac{W-s}{2D}.\)
For every feasible allocation,
\(\displaystyle
\min\{U_1,U_2\}
=\frac{W}{4D}-\frac{|s-W/2|}{2D}
\le\frac{W}{4D}.
\)
Equality holds exactly when \(s=W/2\). By the cardinality argument above, this happens exactly for yes-instances of PARTITION.
Hence deciding whether an allocation has minimum utility at least \(W/(4D)\) is \(\mathrm{NP}\)-hard for every rule pair.
Likewise,
\(\displaystyle
U_1U_2
=\frac{s(W-s)}{4D^2}
=\frac{W^2}{16D^2}-\frac{(s-W/2)^2}{4D^2}
\le\frac{W^2}{16D^2}.
\)
Equality again holds exactly when \(s=W/2\). Thus deciding whether an allocation has product at least \(W^2/(16D^2)\) is \(\mathrm{NP}\)-hard for every rule pair.
An exact maximizing-allocation algorithm would solve either threshold problem by returning an allocation whose objective can be evaluated exactly. Therefore both optimization problems are \(\mathrm{NP}\)-hard.
Finally, an allocation is a polynomial-size certificate. Its eligibility, cardinalities, disjointness, and objective threshold can all be checked with polynomial-bit arithmetic. Both threshold decision versions are therefore \(\mathrm{NP}\)-complete.
Let
\(\displaystyle
r=\min\{k_1,k_2\},
\qquad
Q=(m+1)(\tau+\log_2(m+2)).
\)
The following bounds apply to both objectives and every rule pair.
For community \(i\), let \(H_i\) contain its \(\min\{K,|C_i|\}\) highest-weight candidates, resolving ties by any fixed ordering.
Claim. Some optimum has \(w_i\subseteq H_i\) for both communities.
To prove this, start from an optimum. Suppose \(c\in w_i\setminus H_i\). Then \(|H_i|=K\); otherwise \(H_i=C_i\), contradicting the choice of \(c\).
Exactly \(K\) candidates are allocated in total, including \(c\notin H_i\). Thus at most \(K-1\) members of \(H_i\) are allocated, and some \(d\in H_i\) is unused. Replacing \(c\) by \(d\) preserves feasibility and cannot decrease \(U_i\). It leaves the other utility unchanged.
The replacement also decreases \(|w_i\setminus H_i|\). Repeating these replacements for both communities terminates after at most \(K\) steps. The resulting allocation remains optimal, proving the claim.
Now choose a community \(i\) with \(k_i=r\). Enumerate every \(r\)-element subset \(W\subseteq H_i\). For each \(W\), give the other community its highest-weight \(k_j\) candidates in \(C_j\setminus W\), rejecting \(W\) if fewer than \(k_j\) are available.
This completion maximizes the other utility for fixed \(W\), so it also maximizes either objective for that \(W\). The claim guarantees that one enumerated \(W\) belongs to an optimum.
It suffices to scan \(H_j\) for each completion. If \(|C_j|\le K\), this is the entire candidate set. Otherwise, \(H_j\) has \(K\) candidates and at most \(r\) are blocked, leaving at least \(K-r=k_j\) available.
There are at most \(\binom{K}{r}\) enumerated subsets, and each evaluation takes \(O((K+1)B^2)\) bit operations. The total running time is
\(\displaystyle
O\!\left(\left[Q+(K+1)\binom{K}{r}\right]B^2\right).
\)
Since \(\binom{K}{r}\le2^K\), this proves fixed-parameter tractability in \(K=k_1+k_2\).
Enumerate every assignment of the \(t\) shared candidates to three states: community one, community two, or unallocated. There are \(3^t\) assignments.
For each assignment:
For a fixed shared assignment, the private choices are independent between communities. Choosing the highest-weight private candidates maximizes both utilities simultaneously, and hence maximizes either objective for that assignment. Every feasible allocation has one of the enumerated shared assignments, proving correctness.
After sorting private candidates and preparing prefix sums, an assignment can be evaluated in \(O((t+1)B^2)\) bit operations. The total running time is
\(\displaystyle
O\!\left(\left[Q+(t+1)3^t\right]B^2\right).
\)
This proves fixed-parameter tractability in \(t=|C_1\cap C_2|\). In particular, disjoint candidate sets give a polynomial-time case.
Choosing the smaller of the two enumeration bounds yields
\(\displaystyle
O\!\left(
\left[
Q+\min\left\{(K+1)\binom{K}{r},(t+1)3^t\right\}
\right]B^2
\right).
\)
These algorithms use the listed support directly; their polynomial factors depend on \(\tau\) and \(L\), without expanding rational masses into an explicit electorate.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned task correctly. Both objectives are NP-hard for every fixed rule pair in the stated support representation; the threshold versions are NP-complete. The two exact algorithms and their stated parameterized running times are also justified. I found no major or minor mathematical issues requiring repair.
The feasibility argument correctly accounts for overlapping candidate sets. The required shared counts \(x_i=\max\{0,k_i-|P_i|\}\) satisfy \(x_i\le t\) and \(x_1+x_2\le t\). The separate treatment of the case where at most one count is positive is necessary and correct. Filling the remaining positions from the private sets then produces a feasible allocation.
If either community has zero committee size or zero share, its utility is identically zero. Since all utilities are nonnegative, both objectives are identically zero on feasible allocations. The claimed polynomial-time handling of these cases is valid.
The denominators used for MSAV are constant over committees of the prescribed size: \(\min\{|S|,|w_i|\}=\min\{|S|,k_i\}\). Thus exchanging the finite sums gives the stated additive representation exactly.
Empty approval sets contribute zero and are correctly excluded from divisions. The separate definition for \(k_i=0\) also agrees with the specified zero-denominator convention.
Nonnegativity of the weights and coordinatewise monotonicity of both objectives hold under the stated assumptions. Consequently, the replacement and completion arguments may use increases in one utility while holding the other fixed.
The proposed denominator product is divisible by the denominator of every individual contribution \(\alpha_i\mu_i(S)/d_i(S)\). Its bit length is bounded by the stated \(B\), so every scaled candidate weight is an integer.
The bound \(U_i(w_i)\le1\) is valid for both rules. Feasible scaled utility sums are therefore at most \(D\), and products are at most \(D^2\). The weaker bound \(mD\) for sums over all candidates also suffices for the claimed \(O(B)\)-bit arithmetic, since the explicit input encoding bounds \(\log_2(m+1)\) by its input length.
The preprocessing estimate accounts for denominator construction, at most \(m\tau\) incidences, sorting, and prefix sums. Quadratic-time integer arithmetic gives the asserted conservative bit-operation bound.
The invoked theorem is the NP-completeness of PARTITION with positive integers encoded in binary. This is the standard source problem recorded in the cited [Karp paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf), and the reduction uses precisely that encoding.
An \(n\)-candidate subset containing original candidates indexed by \(I\) has weight \(n+\sum_{j\in I}a_j\). There are enough dummy candidates to complete every original subset to cardinality \(n\). Since \(W=A+2n\), equality with \(W/2\) is equivalent to \(\sum_{j\in I}a_j=A/2\).
This equivalence also handles odd \(A\): neither equality can then hold.
Every singleton mass is positive. The empty-set mass is positive because \(D>W\), and the masses sum exactly to one.
The constructed candidate sets, committee sizes, and shares satisfy all task constraints. The support counts \(m=2n\) and \(\tau=4n+2\) are correct. Since \(D\le2W\), all masses and thresholds have polynomial binary description length.
The proof therefore establishes hardness directly for the required support representation, without relying on expansion into an explicit electorate.
For positive committee size, SAV and MSAV coincide on singleton approval types. Empty types contribute zero under either rule. Hence the same construction applies to all four fixed rule pairs.
Disjoint committees of size \(n\) exhaust the \(2n\) candidates, giving the stated complementary utilities. Both objective identities are algebraically correct:
\[ \min\{U_1,U_2\} =\frac{W}{4D}-\frac{|s-W/2|}{2D}, \]
\[ U_1U_2 =\frac{W^2}{16D^2}-\frac{(s-W/2)^2}{4D^2}. \]
Each threshold is attained exactly when the original PARTITION instance is a yes-instance. This proves the claimed NP-hardness.
Feasible allocations have polynomial-size certificates, and the objectives and rational thresholds can be compared exactly in polynomial time. The NP-completeness claims are therefore justified. An algorithm returning an exact maximizing allocation would also decide the corresponding threshold problem.
The restriction to \(H_i\) is justified. If an allocated candidate lies outside \(H_i\), then \(H_i\) has size \(K\). Because only \(K\) candidates are allocated and one lies outside \(H_i\), some member of \(H_i\) is unused.
Replacing the outside candidate preserves feasibility and cannot decrease the objective. Each replacement reduces the number of committee members outside the corresponding \(H_i\), so the process terminates with an optimum satisfying both restrictions.
Enumerating the smaller committee therefore includes a committee from an optimum. For each enumeration, selecting the other community’s highest-weight available candidates is valid for both objectives. Scanning \(H_j\) suffices because at most \(r\) of its \(K\) candidates are blocked.
The resulting bound
\[
O\!\left(\left[Q+(K+1)\binom{K}{r}\right]B^2\right)
\]
and fixed-parameter tractability in \(K\) follow.
The three-state assignments cover every possible allocation of shared candidates. For each assignment, the private choices are independent, and highest-weight private completions maximize both utilities simultaneously.
The rejection conditions correctly detect infeasible assignments. Prefix sums support the stated evaluation cost, yielding
\[
O\!\left(\left[Q+(t+1)3^t\right]B^2\right).
\]
The combined minimum bound is valid, and both algorithms operate directly on the listed support. These bounds address the requested dependence on \(m,\tau,L,k_1,k_2\), with \(t\) additionally identifying the overlap parameter.
No additional clarification or repair is needed. The hardness established is ordinary NP-hardness; the output does not claim strong NP-hardness.
⟨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.