Multiwinner Elections With Diversity Constraints (d4-conf-aaai-2018-0163)

Given a finite candidate set \(C\) partitioned into \(A\) and \(B\), an even committee size \(k=2k'\), a finite set \(T\) of complete rankings, and a rational distribution \(\mu\) over \(T\), find a committee \(W\) with \(|W\cap A|=|W\cap B|=k'\) maximizing \(F_\mu(W)=\sum_{t\in T}\mu_t\bigl(m-\min_{c\in W}\operatorname{pos}_t(c)\bigr)\), or obtain a stated \((1-\varepsilon)\)-approximation.

Let \(C=A\sqcup B\) be an explicitly listed candidate set with \(m=|C|\), and let \(k=2k'\), where \(1\leq k'\leq\min\{|A|,|B|\}\).
A society is given by its support: a list \(T\) of \(\tau\) distinct strict complete rankings of \(C\), each with positive binary rational mass \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length.
A feasible committee is a set \(W\subseteq C\) with \(|W\cap A|=|W\cap B|=k'\). Its Borda Chamberlin–Courant value is \(F_\mu(W)=\sum_{t\in T}\mu_t\bigl(m-\min_{c\in W}\operatorname{pos}_t(c)\bigr)\), where positions start at \(1\). Let \(\mathrm{OPT}\) be the maximum feasible value; any feasible committee meeting the required value is acceptable.

Does this problem admit a PTAS: for every fixed rational \(\varepsilon\in(0,1)\), can a feasible \(W\) with \(F_\mu(W)\geq(1-\varepsilon)\mathrm{OPT}\) be found in time polynomial in \(m,\tau,k,L\), or is achieving this guarantee NP-hard for some fixed \(\varepsilon\)? State running-time dependence on \(\varepsilon\).

For explicitly listed, equally weighted voters, balanced Borda Chamberlin–Courant maximization admits a PTAS. [Bredereck et al.](https://arxiv.org/pdf/1711.06527)
No result settling the same approximation question for binary rational support masses was verified in the literature search.

Result

The problem admits a deterministic PTAS for binary rational support masses. For every fixed rational \(\varepsilon\in(0,1)\), its running time is
\(m^{O(1/\varepsilon)}\operatorname{poly}(\tau,k,L)\).

The proof below is self-contained. The equally weighted PTAS in [Bredereck et al., Theorem 22](https://arxiv.org/pdf/1711.06527) provides background; no extension of that theorem to weighted voters is assumed.

Write \(r=k'\). The assumptions imply \(m\geq 2r\geq 2\). Because the masses sum to \(1\), every feasible committee satisfies \(F_\mu(W)\leq m-1\), so \(\mathrm{OPT}\leq m-1\).

1. Every set of \(r\) candidates can be completed feasibly

Let \(S\subseteq C\) have size \(r\). Put \(a=|S\cap A|\) and \(b=|S\cap B|\), so \(a+b=r\).

Add \(r-a\) candidates from \(A\setminus S\) and \(r-b\) candidates from \(B\setminus S\). These additions are possible because \(|A|\geq r\) and \(|B|\geq r\). The resulting committee \(W\supseteq S\) is feasible.

For each ranking, enlarging a nonempty committee cannot worsen its highest-ranked representative. Since all masses are positive, \(F_\mu(W)\geq F_\mu(S)\).

Thus it suffices to find a high-value set of \(r\) candidates, without imposing balance during its selection.

2. A uniformly random set has high expected value

Let \(S\) be uniformly distributed over all \(r\)-element subsets of \(C\). For a ranking \(t\), define \(X_t=\min_{c\in S}\operatorname{pos}_t(c)\).

For every integer \(j\) with \(0\leq j\leq m-1\), the event \(X_t>j\) means that all selected candidates lie outside the first \(j\) positions. Hence
\(\Pr(X_t>j)=\binom{m-j}{r}/\binom{m}{r}\), with a binomial coefficient interpreted as zero when its upper argument is smaller than \(r\).

For any integer-valued \(X_t\in\{1,\ldots,m\}\), the pointwise identity
\(X_t=\sum_{j=0}^{m-1}\mathbf{1}_{\{X_t>j\}}\)
gives
\(\mathbb{E}X_t=\sum_{j=0}^{m-1}\Pr(X_t>j)\).

Consequently,
\(\mathbb{E}X_t=\binom{m}{r}^{-1}\sum_{u=1}^{m}\binom{u}{r} =\binom{m+1}{r+1}/\binom{m}{r} =(m+1)/(r+1)\).

Here the summation identity follows by telescoping Pascal’s identity
\(\binom{u}{r}=\binom{u+1}{r+1}-\binom{u}{r+1}\); its lower boundary term is zero because \(r\geq1\).

Linearity of expectation and \(\sum_t\mu_t=1\) now imply
\(\mathbb{E}F_\mu(S)=m-(m+1)/(r+1)\).

Rewriting this expression gives
\(\mathbb{E}F_\mu(S)=(m-1)-(m-r)/(r+1)\).

Since \(r\geq1\), we have \(m-r\leq m-1\). Therefore
\(\mathbb{E}F_\mu(S)\geq(1-1/(r+1))(m-1)\).

This calculation holds for the given rational masses exactly.

3. Deterministic selection by conditional expectations

We next prove that a set attaining at least this expectation can be found in polynomial time.

Suppose a set \(S\) of \(s\leq r\) candidates has already been selected. Let \(R=C\setminus S\), \(n=m-s\), and \(q=r-s\). Define
\(\Phi(S)=\mathbb{E}[F_\mu(S\cup U)]\),
where \(U\) is a uniformly random \(q\)-element subset of \(R\).

When \(s=r\), this definition gives \(\Phi(S)=F_\mu(S)\).

Exact evaluation

Let \(H_t(j)=\{c:\operatorname{pos}_t(c)\leq j\}\) and \(a_t(j)=|R\cap H_t(j)|\).

If \(S\cap H_t(j)\neq\varnothing\), the completed set certainly has a representative among the first \(j\) positions. Otherwise it avoids those positions precisely when \(U\) avoids the \(a_t(j)\) remaining candidates there. Thus the same tail-sum identity gives
\[ \]
Using only the requested inline delimiters, the resulting formula is:

\(\displaystyle \Phi(S)=m-\sum_{t\in T}\mu_t \sum_{j=0}^{m-1} \mathbf{1}_{\{S\cap H_t(j)=\varnothing\}} \frac{\binom{n-a_t(j)}{q}}{\binom{n}{q}}. \)

The denominator is positive because \(0\leq q\leq n\). This formula also applies when \(q=0\).

For each ranking, scanning its candidates in order computes all prefix counts in linear time. Therefore one evaluation of \(\Phi(S)\) uses \(O(\tau m)\) arithmetic operations after binomial coefficients have been precomputed.

Choosing the next candidate

When \(s<r\), we have
\(\Phi(S)=\frac{1}{n}\sum_{x\in R}\Phi(S\cup\{x\})\).

To justify this identity, first select \(x\) uniformly from \(R\), then select \(q-1\) candidates uniformly from \(R\setminus\{x\}\). Any particular \(q\)-element subset arises with probability
\(q/[n\binom{n-1}{q-1}]=1/\binom{n}{q}\).
Thus the resulting completion has exactly the distribution defining \(\Phi(S)\).

At least one candidate consequently satisfies
\(\Phi(S\cup\{x\})\geq\Phi(S)\).
Evaluate every possible next candidate and choose one maximizing this quantity. Starting with \(S=\varnothing\) and repeating \(r\) times produces a deterministic set \(S_*\) satisfying
\(F_\mu(S_*)\geq\Phi(\varnothing)=m-(m+1)/(r+1)\).

Completing \(S_*\) as in Section 1 yields a feasible committee \(W\) with
\(F_\mu(W)\geq(1-1/(r+1))(m-1)\).

Binary rational arithmetic

Write \(\mu_t=p_t/d_t\) and let \(Q=\prod_{t\in T}d_t\). The binary length of \(Q\) is \(O(L)\), since the denominators are explicitly encoded in the input. Each mass can be represented using this common denominator.

Every binomial coefficient used above is at most \(2^m\). At a state with parameters \(n,q\), the formula for \(\Phi(S)\) therefore has common denominator \(Q\binom{n}{q}\), of binary length \(O(L+m)\). Its numerator has polynomial binary length as well. All evaluations and comparisons can consequently be performed exactly in polynomial bit time.

There are at most \(rm\) evaluations of possible next candidates, giving \(O(r\tau m^2)\) arithmetic operations, plus \(O(m^2)\) operations to precompute binomial coefficients. Their bit lengths are polynomial in \(L+m\).

4. The PTAS and its dependence on \(\varepsilon\)

Fix \(\varepsilon\in(0,1)\) and set \(h=\lceil1/\varepsilon\rceil\).

If \(r<h\), enumerate every feasible committee and return an optimum. There are
\(\binom{|A|}{r}\binom{|B|}{r}\leq m^{2r}\leq m^{2h-2}\)
such committees. Each value can be computed exactly in polynomial time.

If \(r\geq h\), use the deterministic construction of Section 3. Since \(1/(r+1)\leq\varepsilon\), its output satisfies
\(F_\mu(W)\geq(1-\varepsilon)(m-1)\geq(1-\varepsilon)\mathrm{OPT}\).

Combining the two branches gives the explicit running-time bound
\(\bigl(m^{2\lceil1/\varepsilon\rceil-2}+1\bigr)\operatorname{poly}(m,\tau,k,L)\),
where the polynomial factor can be chosen independently of \(\varepsilon\).

This proves the required guarantee for every fixed rational \(\varepsilon\), including arbitrarily small positive support masses encoded in binary.

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated task. The argument establishes a deterministic PTAS for binary rational support masses, with running time \(m^{O(1/\varepsilon)}\operatorname{poly}(\tau,k,L)\). No substantive mathematical gaps or incorrect steps were found.

1. Feasible completion

The completion argument is correct.

For an \(r\)-element set \(S\), its category counts satisfy \(a+b=r\), so neither count exceeds \(r\). The available candidates satisfy
\[ |A\setminus S|=|A|-a\geq r-a,\qquad |B\setminus S|=|B|-b\geq r-b. \]
Thus the specified additions produce exactly \(r\) candidates from each category.

Because \(r\geq1\), the initial set is nonempty and its best representative is defined. Adding candidates cannot increase the minimum position in any ranking. Consequently, completion cannot decrease the weighted objective.

The preliminary bound \(\mathrm{OPT}\leq m-1\) is also correct: every representative has position at least \(1\), and the masses sum to \(1\).

2. Expected value of a uniform subset

The probability formula is correct for every stated index \(0\leq j\leq m-1\). Avoiding the first \(j\) positions leaves precisely \(m-j\) available candidates, giving
\[ \Pr(X_t>j)=\frac{\binom{m-j}{r}}{\binom{m}{r}}. \]

The tail-sum identity uses the correct endpoints for a positive integer-valued variable bounded by \(m\). The subsequent change of index and telescoping calculation are valid. In particular, the lower boundary vanishes because \(r\geq1\). Therefore
\[ \mathbb{E}X_t=\frac{m+1}{r+1} \]
is correct.

The calculation is independent of the ranking. Linearity of expectation and normalization of the masses therefore give the stated weighted expectation exactly.

Both the algebraic rewriting and the inequality
\[ \mathbb{E}F_\mu(S)\geq \left(1-\frac{1}{r+1}\right)(m-1) \]
are correct. No lower bound on individual masses is used.

3. Conditional expectations

The potential is well-defined throughout the construction: every completed set has exactly \(r\geq1\) candidates.

The evaluation formula correctly distinguishes whether the selected set already intersects a ranking prefix. When it does not, the numerator counts completions avoiding that prefix. The denominator is positive because \(0\leq q\leq n\).

The boundary case \(q=0\) is handled correctly. All relevant binomial coefficients with lower argument zero equal \(1\), and the remaining indicators recover the tail sum for the minimum position of the selected set.

The averaging identity for choosing the next candidate is justified correctly. When \(s<r\), one has \(q\geq1\); each particular completion arises through exactly \(q\) possible first choices. Its stated probability is therefore correct.

Selecting a maximizing next candidate preserves or increases the potential. At termination, the potential equals the actual objective. This establishes the claimed deterministic guarantee, and feasible completion preserves it.

4. Exact arithmetic and running time

The bit-complexity argument is sufficient.

The product of the explicitly encoded mass denominators has binary length \(O(L)\). The relevant binomial coefficients have \(O(m)\) bits. Hence the proposed common denominators, numerators, and comparison operands have polynomial bit length.

There is no expansion into a population whose size depends on the numerical denominators or inverse masses.

The operation counts are valid: at most \(rm\) candidate evaluations, each requiring \(O(\tau m)\) arithmetic operations, and \(O(m^2)\) operations for binomial precomputation. Exact integer and rational arithmetic therefore yields polynomial bit time for this branch.

5. Approximation branches and dependence on \(\varepsilon\)

For \(h=\lceil1/\varepsilon\rceil\), the small-\(r\) branch enumerates all feasible committees. Its count satisfies the stated bound because integer \(r<h\) implies \(r\leq h-1\). Exact optimization in this branch meets the requested guarantee.

For \(r\geq h\), the inequality \(1/(r+1)\leq\varepsilon\) holds. Since \(1-\varepsilon>0\) and \(\mathrm{OPT}\leq m-1\), the final comparison has the correct direction:
\[ F_\mu(W)\geq(1-\varepsilon)(m-1) \geq(1-\varepsilon)\mathrm{OPT}. \]

The combined running-time bound is polynomial in the stated input parameters for every fixed rational \(\varepsilon\), with exponent \(O(1/\varepsilon)\).

The cited equally weighted result is expressly background and is not used in any inference. No external theorem application requires verification.

No mathematical repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩