Multi-Attribute Proportional Representation (d4-conf-aaai-2016-0389)

Given a finite candidate database \(C\) with attribute domains \(D_1,\ldots,D_p\), an integer \(k\), and a rational population distribution \(\mu\) over voter types \(T=\prod_i D_i\), decide whether there exists an integral committee \(A\subseteq C\) with \(|A|=k\) such that, for every attribute \(i\) and value \(a\), \(\frac{|\{c\in A:X_i(c)=a\}|}{k}=\sum_{t:t_i=a}\mu_t\).

Given explicitly listed nonempty finite domains \(D_1,\ldots,D_p\), with \(p\geq 1\), let \(T=\prod_{i=1}^{p}D_i\). The candidate database \(C\) contains \(m\geq 1\) distinct candidates, each with a specified vector \((X_1(c),\ldots,X_p(c))\in T\); different candidates may have identical vectors. The integer committee size satisfies \(1\leq k\leq m\).
A society is given by its support \(S\subseteq T\): the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t\in S}\mu_t=1\). Unlisted types have zero mass. Here \(\tau=|S|\) is the support size, not the number of possible types.
A perfect committee is an integral subset \(A\subseteq C\) satisfying \(|A|=k\) and, for every \(i\in\{1,\ldots,p\}\) and \(a\in D_i\), \(\frac{|\{c\in A:X_i(c)=a\}|}{k}=\sum_{t\in S:t_i=a}\mu_t\). No divisibility promise is imposed on these marginal masses.
Let \(L\) be the total binary input length; state running times in \(m,\tau,L,p,k\) and the domain sizes \(|D_i|\).

Is deciding whether a perfect committee exists for this support-encoded rational society in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

Known results: perfect-committee existence with directly supplied target marginals is \(\mathrm{NP}\)-complete, even for binary attributes and marginals whose products with \(k\) are integers ([Lang and Skowron](https://www.lamsade.dauphine.fr/~lang/papers/LS18.pdf)). No result explicitly treating the support-encoded society above was located in the literature search.

Proven result

The problem is \(\mathrm{NP}\)-complete, even when every domain is \(\{0,1\}\) and the society has exactly \(\tau=2\) supported types. Hardness holds even when all required marginal counts are integers and both society masses are dyadic rationals.

Thus a polynomial-time algorithm for the general problem exists if and only if \(\mathrm{P}=\mathrm{NP}\).

Exact arithmetic and membership in \(\mathrm{NP}\)

Write \(d=\sum_{i=1}^{p}|D_i|\). For each supported type, write its mass as \(\mu_t=u_t/v_t\), with positive integers \(u_t,v_t\) encoded in binary. Define

\(\displaystyle Q=\prod_{t\in S}v_t,\qquad w_t=u_t(Q/v_t).\)

These are integers. Since the masses sum to one, \(\sum_{t\in S}w_t=Q\). The bit length of \(Q\) is at most the sum of the denominator bit lengths, plus one, hence is \(\mathrm{O}(L)\). Moreover, \(0<w_t\leq Q\).

For each attribute-value pair, compute

\(\displaystyle g_{i,a}=\sum_{\substack{t\in S\\t_i=a}}w_t.\)

Its marginal mass is exactly \(g_{i,a}/Q\). Consequently, a necessary condition for a perfect committee is

\(\displaystyle Q\mid k g_{i,a}\qquad\text{for every }i\text{ and }a\in D_i.\)

If any divisibility test fails, reject. Otherwise define the integer target counts \(b_{i,a}=k g_{i,a}/Q\). They satisfy \(0\leq b_{i,a}\leq k\).

A certificate lists \(k\) distinct candidate identifiers. Verify distinctness, count their attribute values, and check that every count equals \(b_{i,a}\). These conditions are precisely the definition of a perfect committee, so the verifier is both sound and complete.

Using schoolbook integer arithmetic, all arithmetic involves \(\mathrm{O}(L)\)-bit integers. After indexing the explicitly listed domain values, preprocessing takes

\(\displaystyle \mathrm{O}\bigl((\tau+p\tau+d+1)L^2\bigr)\)

bit operations. Certificate verification takes

\(\displaystyle \mathrm{O}\bigl((m+kp+d+1)L^2\bigr).\)

These deliberately conservative bounds include input indexing and checking candidate identifiers. The certificate length is \(\mathrm{O}(k\log(m+1))\), which is polynomial because \(k\leq m\). Therefore the problem belongs to \(\mathrm{NP}\). This argument imposes no divisibility promise.

Hardness with two supported types

We reduce from Exact Cover by 3-Sets: given an explicitly listed universe \(U\) of size \(3q\), with \(q\geq1\), and a family \(\mathcal F\) of three-element subsets, decide whether some subfamily covers each element exactly once. This source problem is \(\mathrm{NP}\)-complete; it is also the source of [Lang and Skowron’s Proposition 8](https://www.lamsade.dauphine.fr/~lang/papers/LS18.pdf).

Preliminary cases and padding

Let \(n=|\mathcal F|\). If \(n<q\), the source instance is negative: fewer than \(q\) triples cannot cover \(3q\) elements. Output the following fixed negative instance:

• \(p=1\), with \(D_1=\{0,1\}\);
• two distinct candidates, both having value \(0\);
• \(k=2\);
• society masses \(1/2\) on each of the types \((0)\) and \((1)\).

Every possible committee contains zero candidates of value \(1\), whereas perfection requires one.

Otherwise \(n\geq q\). Let \(K\) be the smallest power of two satisfying \(K\geq\max\{2,q\}\). Add \(K-q\) pairwise disjoint triples of new elements to the universe, and add exactly those triples to the family. Call the resulting objects \(U'\) and \(\mathcal F'\).

Each new element occurs in exactly one available triple. Hence every exact cover of \(U'\) must contain every added triple. Removing them yields an exact cover of \(U\); conversely, adjoining them extends any exact cover of \(U\). Thus padding preserves the answer.

Also, \(|U'|=3K\), \(|\mathcal F'|=n+K-q\geq K\), and \(K<2\max\{2,q\}\), so the padding is polynomial in size.

Committee instance and correctness

Set \(p=3K\), index attributes by \(x\in U'\), and give each domain \(\{0,1\}\). For every \(F\in\mathcal F'\), create a distinct candidate \(c_F\) with \(X_x(c_F)=1\) exactly when \(x\in F\). Set \(k=K\).

The society support consists of \(\mathbf0=(0,\ldots,0)\) and \(\mathbf1=(1,\ldots,1)\), with

\(\displaystyle \mu_{\mathbf1}=\frac1K,\qquad \mu_{\mathbf0}=\frac{K-1}{K}.\)

Both masses are positive and sum to one. For every attribute, the required counts are one candidate of value \(1\) and \(K-1\) of value \(0\).

Thus a size-\(K\) committee is perfect exactly when its associated triples contain every element of \(U'\) exactly once. This is exactly an exact cover. Together with padding, this proves equivalence to the source instance.

The constructed parameters are

\(\displaystyle m=n+K-q,\qquad p=3K,\qquad k=K,\qquad \tau=2,\qquad |D_i|=2.\)

The incidence vectors contain \(mp\) bits. Including candidate identifiers, domains, support vectors, and masses, the output length is

\(\displaystyle \mathrm{O}\bigl(mp+m\log(m+1)+p+\log(k+1)\bigr),\)

and construction takes polynomial time, for example

\(\displaystyle \mathrm{O}\bigl((mp+m+p+1)\log(m+p+1)\bigr)\)

bit operations. Because \(K\) is a power of two, both masses are dyadic. Their marginal products with \(k\) are integers.

Conclusion

The reduction supplies the entire society using only two explicitly listed types. It therefore establishes hardness for the requested support encoding without enumerating the exponentially large type space. Combined with the exact polynomial-time verifier, it proves \(\mathrm{NP}\)-completeness.

⟨structured verdict parsed — rendered above⟩

The proof resolves the task: perfect-committee existence is \(\mathrm{NP}\)-complete, including the claimed restriction to binary domains, exactly two supported types, dyadic masses, and integral target counts. No mathematical gap or false step was found.

• Exact rational arithmetic is valid. Every denominator \(v_t\) divides \(Q=\prod_{t\in S}v_t\), so each \(w_t=u_t(Q/v_t)\) is an integer. The normalization assumption gives \(\sum_{t\in S}w_t=Q\), and positivity gives \(0<w_t\leq Q\). The stated bound on the bit length of \(Q\) is valid even without reduced fractions.

• The divisibility test is necessary and exact. The marginal for an attribute-value pair is \(g_{i,a}/Q\). An integral committee count can equal \(kg_{i,a}/Q\) only when \(Q\mid kg_{i,a}\). Once this condition holds, checking the integer targets \(b_{i,a}\) is exactly equivalent to checking the task’s marginal equations. Unrepresented values have \(g_{i,a}=0\) and are correctly handled.

• Membership in \(\mathrm{NP}\) is established. A certificate specifies exactly \(k\) distinct candidate identifiers. Checking their validity, distinctness, and attribute counts verifies an integral subset of the required size. Candidates with identical vectors cause no problem because identifiers, rather than vectors, distinguish candidates.

All arithmetic operands, including products \(kg_{i,a}\), have \(\mathrm{O}(L)\) bits. The stated schoolbook-arithmetic bounds are conservative and polynomial. The certificate length \(\mathrm{O}(k\log(m+1))\) is polynomial because \(k\leq m\) and candidates are explicitly listed.

• The source problem is appropriate. The prover states the exact-cover decision problem with an explicitly listed universe of size \(3q\) and three-element subsets. Its cited connection to Proposition 8 is accurate: that proposition uses this source problem and the same incidence-vector interpretation. [Lang and Skowron, Proposition 8](https://www.lamsade.dauphine.fr/~lang/papers/LS18.pdf)

• The preliminary negative case is correct. When \(n<q\), the available triples cannot cover all \(3q\) elements. The fixed output satisfies every target-input restriction, including \(k\leq m\), positive masses, and exactly two supported types. Its required count of one candidate with value \(1\) is impossible.

• Padding preserves the answer. Every newly introduced element belongs to exactly one available triple, forcing every added triple into any exact cover. Removing or adjoining those triples gives the two directions of the claimed equivalence. The resulting universe has \(3K\) elements, and its family has at least \(K\) triples.

The bound \(K<2\max\{2,q\}\) is correct, including \(q=1\). Thus padding is polynomial. Choosing \(K\geq2\) also ensures that both eventual society masses are positive.

• The constructed committee instance is valid. It has \(p=3K\geq1\), binary domains, \(m=n+K-q\geq K=k\), and distinct candidate identifiers. The two support vectors are distinct. Their masses are positive, sum to one, and are dyadic because \(K\) is a power of two.

• The reduction’s equivalence is exact. Every attribute has marginal mass \(1/K\) for value \(1\), so a perfect size-\(K\) committee must contain exactly one candidate whose triple contains each universe element. This is precisely an exact cover. Conversely, an exact cover gives all required counts, including the complementary count \(K-1\) for value \(0\).

• The size and complexity claims suffice. The explicitly written incidence vectors contribute \(mp\) bits; the two support vectors contribute only linear size in \(p\). The remaining listed encoding costs are consistent with the stated output bound under ordinary indexed encodings. The construction is polynomial in the explicitly listed source instance. No enumeration of the full type space is required.

• The conclusion follows. Polynomial verification and the answer-preserving polynomial reduction establish \(\mathrm{NP}\)-completeness. Every additional restriction claimed in the opening statement is satisfied by both branches of the reduction. No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩