d4-conf-sagt-2022-0022 (d4-conf-sagt-2022-0022)

Given candidates \(C\) with fixed gender labels, committee size \(k\), and a distribution \(\mu\) over nonempty approval ballots \(A_t\subseteq C\), decide the following promise problem: either some \(k\)-candidate committee \(W\) satisfies \(U_c(W)<1/k\) for every \(c\in C\) and has gender imbalance \(0\), or every committee satisfying those JR inequalities has gender imbalance at least \(\varepsilon k\), for the constant \(\varepsilon>0\) from Theorem 8. Here \(U_c(W)=\sum_{t:\,c\in A_t,\ A_t\cap W=\varnothing}\mu_t\), and the masses are binary-encoded rationals summing to \(1\).

Input consists of a candidate set \(C=C_M\mathbin{\dot\cup}C_F\) with \(m=|C|\), fixed male/female labels, and an integer \(1\le k\le m\).
A society is given by its support: \(\tau\) distinct nonempty approval sets \(A_t\subseteq C\), each with positive binary-rational mass \(\mu_t\), where \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible approval sets; \(L\) is the total input bit length.
A committee is a subset \(W\subseteq C\) with \(|W|=k\). Define \(U_c(W)=\sum_{t:\,c\in A_t,\ A_t\cap W=\varnothing}\mu_t\); it satisfies JR exactly when \(U_c(W)<1/k\) for every \(c\in C\).
Its gender imbalance is \(g(W)=\bigl||W\cap C_M|-|W\cap C_F|\bigr|\).
Fix a positive absolute constant \(\varepsilon\) witnessing the discrete gap hardness stated below. The input is promised to satisfy either YES: some JR committee has \(g(W)=0\), or NO: every JR committee has \(g(W)\ge\varepsilon k\).

Is distinguishing these two promised cases solvable in polynomial time in \(m,\tau,k,L\), or is it NP-hard?

For explicitly listed, equally weighted voters, this distinction is NP-hard for some absolute \(\varepsilon>0\), even when the number of voters equals \(k\). [Discrete gap hardness](https://arxiv.org/pdf/2108.12949)
No separate result for exactly this rational-mass promise problem was located in the literature search.

Result and encoding convention

The promised distinction is \(\mathrm{NP}\)-hard, for the same constant \(\varepsilon\) as in the stated discrete hardness result.

Here, “binary-rational” means an exact rational represented by a numerator and denominator written in binary. The reduction combines identical ballots and preserves every committee’s JR status and gender imbalance.

Known hardness premise

Theorem 8 of Elkind et al., [*Justifying Groups in Multiwinner Approval Voting*](https://arxiv.org/pdf/2108.12949), establishes the supplied premise: for some absolute constant \(\varepsilon>0\), the following distinction is \(\mathrm{NP}\)-hard for explicitly listed voters, even when their number \(n\) equals the committee size \(k\):

• YES: A gender-balanced JR committee exists.
• NO: Every JR committee has imbalance at least \(\varepsilon k\).

The paper’s model requires nonempty approval ballots, matching the target problem. We apply this theorem with the fixed constant stipulated in the question.

Polynomial reduction to distinct support

Let a discrete instance have ballots \(B_1,\ldots,B_n\), candidate set \(C=C_M\mathbin{\dot\cup}C_F\), and committee size \(k\), where \(n=k\).

List the distinct ballots as \(A_1,\ldots,A_\tau\). For each \(t\), define

\[ r_t=\bigl|\{i:B_i=A_t\}\bigr|, \qquad \mu_t=\frac{r_t}{n}. \]

Retain the candidates, gender labels, and committee size.

Each \(A_t\) is nonempty, the support sets are pairwise distinct, and \(r_t\ge1\). Thus every mass is positive and

\[ \sum_{t=1}^{\tau}\mu_t =\frac{\sum_{t=1}^{\tau}r_t}{n} =1. \]

This is a valid target instance.

To construct it, represent each ballot by its incidence vector over \(C\), group equal vectors, and count their multiplicities. This takes polynomial time in the explicit input size. Moreover, \(\tau\le n=k\), and each fraction \(r_t/n\) requires \(O(\log(n+1))\) bits for its numerator and denominator. Consequently, the entire output has polynomial bit length.

Exact preservation of JR and the gap

Fix any committee \(W\subseteq C\) with \(|W|=k\). For each candidate \(c\), let

\[ q_c(W) = \bigl|\{i:c\in B_i,\ B_i\cap W=\varnothing\}\bigr|. \]

In the discrete instance, JR holds exactly when \(q_c(W)<n/k\) for every \(c\). Indeed:

• If \(q_c(W)\ge n/k\), those voters form an unrepresented group of the required size sharing candidate \(c\), so JR fails.
• Conversely, any unrepresented cohesive group witnessing failure of JR shares some candidate \(c\). All its voters are counted in \(q_c(W)\), so \(q_c(W)\ge n/k\).

In the constructed instance, grouping identical ballots gives the exact identity

\[ U_c(W) = \sum_{\substack{t:c\in A_t\\A_t\cap W=\varnothing}}\frac{r_t}{n} = \frac{q_c(W)}{n}. \]

Because \(n>0\),

\[ U_c(W)<\frac1k \quad\Longleftrightarrow\quad q_c(W)<\frac nk. \]

Therefore, a committee satisfies JR before the reduction if and only if it satisfies JR afterwards. In particular, when \(n=k\), an uncovered voter already contributes at least \(1/k\) to some candidate’s uncovered mass; the strict inequality is preserved exactly.

The candidate set, gender labels, and \(k\) are unchanged. Hence \(g(W)\) is also unchanged for every committee. It follows that:

• A source YES instance maps to a target YES instance.
• A source NO instance maps to a target NO instance, with the same bound \(\varepsilon k\).

Thus the transformation is a polynomial-time reduction preserving both promised cases. A polynomial-time algorithm in \(m,\tau,k,L\) for the rational-mass problem would solve the discrete hard distinction in polynomial time. The requested distinction is therefore \(\mathrm{NP}\)-hard, and admits no such polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verification report

Verdict: proved. The output establishes the requested promise distinction is \(\mathrm{NP}\)-hard under its explicitly stated encoding convention. No mathematical gaps or false steps were found.

1. Hardness premise and hypotheses

The cited Theorem 8 states precisely the required discrete gap hardness: for an absolute constant \(\varepsilon>0\), distinguishing existence of a gender-balanced JR committee from imbalance at least \(\varepsilon k\) for every JR committee is \(\mathrm{NP}\)-hard, even when \(n=k\).

The paper’s preliminaries require nonempty ballots and \(1\le k\le m\). Its gender imbalance definition agrees with the target definition, and gender balance means imbalance zero. Consequently, the theorem’s model and hypotheses match the source instances used in the reduction. These facts are verified in [the cited paper, Sections 2 and 5](https://arxiv.org/pdf/2108.12949).

The output appropriately invokes the supplied hardness theorem; it need not reproduce that theorem’s proof.

2. Rational encoding

The output explicitly interprets “binary-rational” as an exact rational whose numerator and denominator are encoded in binary. This is a natural interpretation of the task’s rational-mass input model.

Under this convention, every proposed mass \(\mu_t=r_t/n\) is representable. The proof does not assume that these fractions have terminating binary expansions. There is no unstated encoding assumption within the write-up.

3. Construction and validity

Grouping equal ballots produces pairwise distinct support sets. Because every source ballot is nonempty, every resulting support set is nonempty.

Each multiplicity satisfies \(1\le r_t\le n\), so every mass is positive. Every source voter belongs to exactly one multiplicity class, giving
\[ \sum_{t=1}^{\tau}r_t=n \]
and hence total mass one.

Retaining the candidate set and committee size preserves \(1\le k\le m\). Retaining gender labels preserves the required candidate partition. Thus the construction satisfies every target input restriction.

4. Polynomial resource bounds

Incidence-vector grouping and multiplicity counting take polynomial time in the explicit source input size. Both integers in each fraction \(r_t/n\) require \(O(\log(n+1))\) bits.

The inequalities \(\tau\le n=k\) are correct. Together with the retained candidate data and explicitly represented support sets, they establish polynomial output length.

The final running-time implication is also justified: all target parameters \(m,\tau,k,L\) are polynomially bounded in the explicit source input size. In particular, \(k=n\), and the source lists its voters explicitly.

5. Exact JR preservation

The discrete characterization is correct in both directions.

If \(q_c(W)\ge n/k\), the voters counted by \(q_c(W)\) form a cohesive group sharing \(c\), and none approves any committee member. They therefore witness failure of JR.

Conversely, a group witnessing failure of JR has a common approved candidate \(c\), and all its members have ballots disjoint from \(W\). Its members are counted by \(q_c(W)\), so \(q_c(W)\ge n/k\).

Grouping ballots then gives exactly
\[ U_c(W)=\frac{q_c(W)}{n}. \]
Since \(n=k\ge1\), multiplication by \(n\) preserves the strict inequality:
\[ U_c(W)<\frac1k \quad\Longleftrightarrow\quad q_c(W)<\frac nk. \]

The equality boundary is handled correctly: equality violates JR in both models. The preservation holds for every candidate and every size-\(k\) committee, including candidates approved by no voters.

6. Gender gap and conclusion

The committee domain, gender labels, and committee size are unchanged. Therefore every committee has exactly the same imbalance before and after the reduction.

Combined with exact JR preservation, this proves both promised-case implications with the same fixed constant \(\varepsilon\). The argument establishes hardness for the target problem, already on instances with \(\tau\le k\).

The conclusion excluding a polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\) follows from the supplied discrete hardness premise and the polynomial promise-preserving reduction.

Repair feedback: None required.

⟨structured verdict parsed — rendered above⟩