An Experimental View on Committees Providing Justified Representation (d4-conf-ijcai-2019-0737)

Given candidates \(C\), committee size \(k\), a rational distribution \(\mu=(\mu_A)_{A\subseteq C}\) over approval types, and a rational threshold \(q\), decide whether there exists \(W\subseteq C\) with \(|W|=k\), \(b_\mu(c,W)<1/k\) for every \(c\in C\), and \(\operatorname{cov}_\mu(W)=\sum_{A:A\cap W\neq\varnothing}\mu_A\ge q\).

Let \(C\) be a candidate set with \(m=|C|\), and let \(1\le k\le m\) be an integer. A society is given by its support: a list of \(\tau\) distinct approval types \(A\subseteq C\), each with positive binary rational mass \(\mu_A\), with \(\sum_A\mu_A=1\). Unlisted types have zero mass; empty approval sets are allowed. Here \(\tau\) is the support size, not the number of possible approval types.
For a committee \(W\subseteq C\), define its blocking mass at candidate \(c\) by \(b_\mu(c,W)=\sum_{A:c\in A,\ A\cap W=\varnothing}\mu_A\), and its coverage by \(\operatorname{cov}_\mu(W)=\sum_{A:A\cap W\ne\varnothing}\mu_A\). A size-\(k\) committee provides justified representation precisely when \(b_\mu(c,W)<1/k\) for every \(c\in C\).
Given this society and a binary rational threshold \(q\in[0,1]\), decide whether there exists \(W\subseteq C\) with \(|W|=k\), justified representation, and \(\operatorname{cov}_\mu(W)\ge q\). Let \(L\) be the total input bit length; state running times in \(m,\tau,k,L\).

Is this decision problem solvable in polynomial time, or is it NP-hard?

For explicitly listed finite voters, the corresponding maximum-coverage JR decision problem is NP-hard and W[1]-hard parameterized by \(k\). [Verified discrete result](https://www.ijcai.org/proceedings/2019/0016.pdf)
No result settling this exact support-encoded rational-mass problem was verified in the literature search.

Result

The problem is \(\mathrm{NP}\)-complete. It is also \(\mathrm{W}[1]\)-hard parameterized by \(k\).

The hardness applies to the stated encoding with only \(\tau\) distinct positive-mass approval types. No enumeration of all possible approval types is needed.

1. Exact verification and membership in \(\mathrm{NP}\)

A certificate is a committee \(W\subseteq C\) of size \(k\). We show that its coverage and JR conditions can be checked in polynomial time using exact integer arithmetic.

Write each listed mass as \(\mu_A=p_A/d_A\), and write \(q=s/t\), with positive denominators. Define
\[ D=t\prod_A d_A,\qquad u_A=p_A(D/d_A),\qquad Q=s(D/t). \]
Here and below, these expressions denote integers. The bit length of \(D\) is \(O(L)\), because the sum of the bit lengths of its factors is at most \(L\). All the \(u_A\) and \(Q\) also have \(O(L)\) bits.

For the proposed committee, compute
\[ U(W)=\sum_{A:A\cap W\ne\varnothing}u_A, \qquad B(c,W)=\sum_{A:c\in A,\ A\cap W=\varnothing}u_A. \]
Then \(\operatorname{cov}_\mu(W)=U(W)/D\) and \(b_\mu(c,W)=B(c,W)/D\). Consequently, the required conditions are exactly
\[ U(W)\ge Q \quad\text{and}\quad kB(c,W)<D\quad\text{for every }c\in C. \]
In particular, the strict inequality is preserved exactly.

Using schoolbook integer arithmetic, preprocessing the common denominator and integer weights takes \(O(L^3)\) bit operations. One can also precompute
\[ R=\left\lfloor\frac{D-1}{k}\right\rfloor, \]
so that each JR check becomes \(B(c,W)\le R\). Scanning the listed types and accumulating their contributions takes \(O(m\tau L)\) bit operations. Thus verification takes
\[ O(L^3+m\tau L). \]
The problem therefore belongs to \(\mathrm{NP}\).

2. A direct polynomial reduction from Set Cover

We use the standard \(\mathrm{NP}\)-complete Set Cover problem: given a nonempty universe \(U\), subsets \(S_1,\ldots,S_r\subseteq U\), and a budget \(h\), decide whether at most \(h\) of the subsets cover \(U\). We may restrict to \(1\le h\le r\); the excluded cases are directly decidable.

Let \(n=|U|\). Construct candidates
\[ C=\{c_1,\ldots,c_r\}, \qquad k=h. \]
For each element \(x\in U\), define its approval type
\[ A_x=\{c_i:x\in S_i\}. \]
Merge equal approval types. For every distinct resulting type \(A\), let
\[ t_A=|\{x\in U:A_x=A\}|, \qquad \mu_A=\frac{t_A}{n}. \]
Finally, set \(q=1\).

This is a valid instance:

• Every listed mass is positive, and their sum is \(1\).
• The types are distinct after merging, and \(\tau\le n\).
• An element belonging to no subset produces the allowed empty approval type.
• Each numerator and denominator has \(O(\log(n+1))\) bits. Constructing and grouping the approval types takes polynomial time in the Set Cover input length.

For any committee \(W\), its coverage is exactly
\[ \operatorname{cov}_\mu(W) = \frac{\left|\bigcup_{i:c_i\in W}S_i\right|}{n}. \]
Indeed, the type associated with \(x\) intersects \(W\) precisely when a selected subset contains \(x\); merging equal types preserves the number of such elements.

If the Set Cover instance has a cover using at most \(h\) subsets, enlarge its index set to exactly \(h\) indices. This is possible because \(h\le r\), and enlargement preserves coverage. The corresponding committee has coverage \(1\). Every positive-mass type is represented, so
\[ b_\mu(c,W)=0<1/h \quad\text{for every }c\in C. \]
It therefore satisfies JR.

Conversely, any feasible committee in the constructed instance has coverage at least \(q=1\), hence coverage exactly \(1\). The displayed coverage identity implies that its \(h\) selected subsets cover \(U\).

Thus the constructed instance is a yes-instance exactly when the Set Cover instance is a yes-instance. This proves \(\mathrm{NP}\)-hardness and, together with Section 1, \(\mathrm{NP}\)-completeness.

3. JR does not reduce the optimal coverage

The reduction above uses full coverage. The following statement explains why JR also leaves the optimal coverage unchanged for arbitrary rational-mass societies.

Proposition. Every size-\(k\) committee maximizing coverage satisfies JR.

Proof. Let \(W\) maximize coverage. If \(\operatorname{cov}_\mu(W)=1\), every blocking mass is zero, so JR holds.

Suppose instead that \(\operatorname{cov}_\mu(W)<1\). For each \(w\in W\), define its exclusive represented mass by
\[ e_w=\sum_{A:A\cap W=\{w\}}\mu_A. \]
The types counted for different committee members are disjoint, and all are represented. Therefore
\[ \sum_{w\in W}e_w\le\operatorname{cov}_\mu(W). \]
Some \(w\in W\) consequently satisfies
\[ e_w\le\frac{\operatorname{cov}_\mu(W)}{k}<\frac1k. \]

If JR fails, some candidate \(c\) has \(b_\mu(c,W)\ge1/k\). Such a candidate cannot belong to \(W\), because a selected candidate has blocking mass zero.

Replace the chosen \(w\) by \(c\), obtaining \(W'=(W\setminus\{w\})\cup\{c\}\). This represents previously unrepresented mass exactly \(b_\mu(c,W)\). Any previously represented type that becomes unrepresented must have intersected \(W\) only in \(w\); hence the lost mass is at most \(e_w\). Thus
\[ \operatorname{cov}_\mu(W')-\operatorname{cov}_\mu(W) \ge b_\mu(c,W)-e_w >0. \]
This contradicts maximality. Therefore \(W\) satisfies JR. \(\square\)

Since there are finitely many size-\(k\) committees, a coverage maximizer exists. The proposition implies that, for every threshold \(q\), existence of a committee meeting the coverage threshold is equivalent to existence of a JR committee meeting it.

4. Transfer of the discrete parameterized hardness

Theorem 5 of the [cited IJCAI paper](https://www.ijcai.org/proceedings/2019/0016.pdf) establishes \(\mathrm{W}[1]\)-hardness for maximum-coverage JR with explicitly listed voters, parameterized by committee size.

That theorem transfers directly. Given \(n\) explicitly listed voters, merge equal ballots and assign each resulting type mass \(t_A/n\), where \(t_A\) is its multiplicity. Replace the integer coverage threshold \(x\) by \(q=x/n\). For every committee \(W\),
\[ b_\mu(c,W) = \frac{\#\{i:c\in A_i,\ A_i\cap W=\varnothing\}}{n}, \]
and
\[ \operatorname{cov}_\mu(W) = \frac{\#\{i:A_i\cap W\ne\varnothing\}}{n}. \]
Hence both the discrete JR condition and the coverage threshold are preserved exactly. The output has \(\tau\le n\), polynomial encoding length, and unchanged \(k\). This proves the claimed parameterized hardness.

5. Running time

Preprocess the rational weights once, then enumerate all size-\(k\) committees and verify each as in Section 1. This gives an exact deterministic algorithm using
\[ O\!\left(L^3+\binom{m}{k}m\tau L\right) \]
bit operations.

For every fixed \(k\), this is polynomial time, with bound \(O(L^3+m^{k+1}\tau L)\). When \(k\) is part of the input, the decision problem is \(\mathrm{NP}\)-complete, so a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verdict

The output settles the requested problem: the support-encoded rational-mass decision problem is \(\mathrm{NP}\)-complete. The direct Set Cover reduction and exact verification argument are correct. The coverage-maximizer proposition is also correct.

The additional \(\mathrm{W}[1]\)-hardness claim is supported by the cited theorem and the ballot-compression transformation. That transformation has one minor domain omission: the source coverage threshold must be restricted to \(0\le x\le n\) so that the produced threshold satisfies \(q\in[0,1]\).

No major error or missing mathematical lemma was found.

1. Exact verification and membership in \(\mathrm{NP}\)

Common denominator. The integer \(D=t\prod_A d_A\) is divisible by every mass denominator and by the threshold denominator. Thus \(u_A\) and \(Q\) are integers, and the displayed identities for coverage and blocking mass hold exactly. Reduced fractions are unnecessary.

Bit lengths. The bit length of a product is bounded by the sum of the factor bit lengths, up to a constant. Consequently, \(D\), each \(u_A\), and \(Q\) have \(O(L)\) bits. Moreover, normalization gives \(\sum_A u_A=D\), so every accumulated coverage or blocking sum is at most \(D\).

Comparisons. Since \(D>0\), the coverage condition is exactly \(U(W)\ge Q\). Since \(k>0\), JR is exactly \(kB(c,W)<D\). For integer \(B(c,W)\), the latter is equivalent to
\(B(c,W)\le\lfloor(D-1)/k\rfloor\).
The strict boundary is handled correctly.

Running time. There are \(O(L)\) encoded rational components. Using schoolbook arithmetic on \(O(L)\)-bit integers, the stated \(O(L^3)\) preprocessing bound is valid. Scanning candidate incidences and adding \(O(L)\)-bit weights fits within \(O(m\tau L)\). Checking certificate cardinality and distinctness is routine and fits within the stated bounds.

Therefore, membership in \(\mathrm{NP}\) is established.

2. Set Cover reduction

Source problem and restrictions. The stated decision version of Set Cover is standard. Restricting to a nonempty universe and \(1\le h\le r\) removes directly decidable cases and does not invalidate its use as a hardness source.

Output validity. The construction has \(m=r\) and \(k=h\), so \(1\le k\le m\). Every merged type has positive multiplicity; its mass is positive; and the masses sum to one. Equal ballots are merged, giving precisely the required distinct-type representation. Empty approval types are permitted by the target problem.

Encoding size. There are at most \(n\) types, each described using at most \(r\) candidate incidences. Multiplicities and denominators have \(O(\log(n+1))\) bits. Thus the output size and construction time are polynomial in the explicit Set Cover input length.

Coverage identity. An element is covered by the selected subsets exactly when its approval type intersects the corresponding committee. Weighting merged types by their multiplicities preserves this count. The displayed coverage identity is correct.

Forward implication. A cover using at most \(h\) indices can be extended to exactly \(h\) distinct indices because \(h\le r\). Full coverage makes every blocking mass zero, which satisfies the strict JR inequality.

Reverse implication. With \(q=1\), feasibility forces full coverage because normalized coverage cannot exceed one. The coverage identity then forces the selected subsets to cover the entire universe.

The reduction proves \(\mathrm{NP}\)-hardness independently of the cited voting result. Combined with Section 1, it proves \(\mathrm{NP}\)-completeness.

3. Coverage-maximizer proposition

Every step of the exchange argument is valid:

• Full coverage implies zero blocking mass.
• Exclusive-mass classes for distinct committee members are disjoint and contained in the represented types.
• Their total mass is therefore at most coverage.
• When coverage is below one, some member has exclusive mass strictly below \(1/k\).
• A candidate witnessing JR failure cannot already belong to the committee.
• The replacement therefore preserves committee cardinality.
• Previously unrepresented types become represented exactly when they approve the added candidate, giving gain \(b_\mu(c,W)\).
• Any lost type must previously have intersected the committee only in the removed member, so its total mass is at most \(e_w\).
• The resulting coverage increase is strictly positive, contradicting maximality.

The argument covers empty approval types, \(k=1\), and \(k=m\). In the last case, the asserted external candidate cannot exist, consistently ruling out JR failure.

Finiteness guarantees a coverage maximizer. The claimed equivalence of threshold feasibility with and without JR follows from the proposition. No gap was found.

4. Parameterized hardness transfer

The cited paper defines the maximum-coverage JR decision problem in Definition 5 and states its \(\mathrm{W}[1]\)-hardness parameterized by committee size in Theorem 5. Its JR definition agrees with the blocking-count condition used by the prover. [IJCAI paper, Definitions 1 and 5 and Theorem 5](https://www.ijcai.org/proceedings/2019/0016.pdf)

The transformation preserves blocking counts and coverage counts after division by \(n\). In particular, the discrete strict inequality against \(n/k\) becomes precisely the target strict inequality against \(1/k\). Merging ballots preserves positive masses and produces polynomial output size. Since \(k\) is unchanged, the transformation has the required parameter preservation.

Minor issue: threshold domain. The write-up says to replace an integer threshold \(x\) by \(q=x/n\), without stating \(0\le x\le n\). Outside that range, the output violates the target input restriction. This is an omitted routine domain restriction, not a failure of the hardness argument.

Minimum clarification: explicitly restrict the source instances used in this transfer to \(0\le x\le n\), and state that thresholds outside the attainable coverage range are directly decidable. No additional hardness construction is needed.

5. Enumeration algorithm and final claims

Preprocessing once and checking all \(\binom{m}{k}\) committees gives the stated bound
\(O(L^3+\binom{m}{k}m\tau L)\).
Committee generation overhead is absorbed by the verification term.

For fixed \(k\), the inequality \(\binom{m}{k}\le m^k\) gives the claimed polynomial bound. This is consistent with parameterized hardness: polynomial time for each fixed parameter value does not establish fixed-parameter tractability.

The conclusion that a polynomial-time algorithm for unrestricted \(k\) would imply \(\mathrm{P}=\mathrm{NP}\) is justified.

⟨structured verdict parsed — rendered above⟩