Proportional Justified Representation (d4-conf-aaai-2017-0235)

Given candidates
(
mathcal{C}
)
, committee size
(
k
)
, a finite approval-type set
(
mathcal{T}
subseteq 2^{
mathcal{C}
}
)
, and rational masses
(
mu_A
ge0
)
summing to
(
1
)
, decide whether some
(
W
subseteq\mathcal{C}
)
with
(
|W|=k
)
admits nonnegative masses
(
x_{A,w}
)
such that
(
x_{A,w}=0
)
for
(
w
notin A
)
,
(
sum_{w
in W}x_{A,w}=mu_A
)
for every
(
A
)
, and
(
sum_{A
inmathcal{T}}x_{A,w}=1/k
)
for every
(
w
in W
)
; if so, output
(
W
)
and such an assignment.

Given a candidate set \(\mathcal{C}\), \(k\leq |\mathcal{C}|\), approval types \(\mathcal{T}\subseteq2^{\mathcal{C}}\), and rational masses \(\mu_A\geq0\) with \(\sum_{A\in\mathcal{T}}\mu_A=1\), a committee \(W\subseteq\mathcal{C}\) of size \(k\) has fractional perfect representation if there are \(x_{A,w}\geq0\) such that \(x_{A,w}=0\) when \(w\notin A\), \(\sum_{w\in W}x_{A,w}=\mu_A\) for every \(A\), and \(\sum_{A\in\mathcal{T}}x_{A,w}=1/k\) for every \(w\in W\).

Target. Is deciding whether such a committee exists polynomial-time solvable, or NP-hard?

For finite voter profiles with \(k\mid n\), deciding whether a perfectly representative committee exists is NP-complete. For finite voter profiles without the divisibility condition, deciding whether a fractional-perfectly-representative committee exists is NP-complete.

The decision problem is NP-complete, under the usual explicit encoding of approval types and binary encoding of rational masses. Here \(1\leq k\leq|\mathcal C|\), as required for \(1/k\) to be defined.

The key point is that, on finite profiles where \(k\) divides the number of voters, fractional perfect representation is equivalent to ordinary perfect representation.

• Equivalence on divisible finite profiles.

Consider a finite profile with \(n\) voters and \(k\mid n\). For each approval set \(A\) occurring in the profile, let \(n_A\) be the number of voters with that approval set. Set \(\mu_A=n_A/n\) and \(q=n/k\).

Fix a committee \(W\) of size \(k\). If the voters can be assigned to approved members of \(W\), with exactly \(q\) voters assigned to each member, let \(y_{A,w}\) count the type-\(A\) voters assigned to \(w\). Then \(x_{A,w}=y_{A,w}/n\) satisfies all fractional-perfect-representation constraints.

Conversely, suppose such fractional variables \(x_{A,w}\) exist. Construct a directed network with source \(s\), one vertex for each approval type \(A\), one vertex for each \(w\in W\), and sink \(t\). Its arcs and capacities are:

• \(s\to A\), with capacity \(n_A\);
• \(A\to w\), with capacity \(n\), whenever \(w\in A\cap W\);
• \(w\to t\), with capacity \(q\).

The values \(f(s,A)=n_A\), \(f(A,w)=nx_{A,w}\), and \(f(w,t)=q\) define a feasible flow of value \(n\). Indeed, conservation at each type and committee vertex follows from the two prescribed marginal sums. Also, \(nx_{A,w}\leq n\), since \(x_{A,w}\leq\mu_A\leq1\).

All capacities are nonnegative integers. The integral maximum-flow theorem therefore guarantees an integral maximum flow. Its value is \(n\): the displayed fractional flow attains this value, and the total capacity leaving \(s\) is \(n\). Consequently, every source arc and every sink arc is saturated, since their respective total capacities are both \(n\).

Write \(y_{A,w}\) for the integral flow on \(A\to w\). For each \(A\), these nonnegative integers sum to \(n_A\), so the \(n_A\) individual voters of that type can be partitioned into groups of sizes \(y_{A,w}\) and assigned accordingly. Every assignment respects approval, and every committee member receives exactly \(q\) voters. Thus \(W\) is ordinarily perfectly representative.

• Polynomial-time reduction and hardness.

Use the NP-complete problem stated in the question: existence of an ordinarily perfectly representative committee for an explicitly listed finite profile satisfying \(k\mid n\).

Preserve \(\mathcal C\) and \(k\), group voters by identical approval sets, and output the occurring types with masses \(\mu_A=n_A/n\). There are at most \(n\) types, and each mass has a binary encoding of length \(O(\log n)\). Grouping and constructing this instance take polynomial time.

The equivalence proved above holds for every committee \(W\). Hence the original profile admits a perfectly representative committee if and only if the resulting rational-mass instance admits a fractionally perfectly representative committee. This proves NP-hardness.

• Membership in NP.

A certificate is simply a committee \(W\) of size \(k\). Its feasibility can be checked in polynomial time using a flow network with capacities \(\mu_A\) on \(s\to A\), capacity \(1\) on each allowed \(A\to w\), and capacity \(1/k\) on \(w\to t\).

A flow of value \(1\) exists exactly when the required variables exist. In particular, value \(1\) forces all source and sink arcs to be saturated because each family has total capacity \(1\).

To justify polynomial time with binary rational inputs, write each mass as \(\mu_A=a_A/b_A\), where \(b_A>0\), and let \(D=\prod_{A\in\mathcal T}b_A\). Multiplying every capacity by \(kD\) gives integer capacities. The bit length of \(D\) is at most the sum of the denominator bit lengths, up to a constant, so the scaled network has polynomial encoding length. A polynomial-time integer-capacity maximum-flow algorithm can therefore check whether its maximum flow has value \(kD\).

Thus the problem belongs to NP and, together with the reduction, is NP-complete.

⟨structured verdict parsed — rendered above⟩

The proof is correct under the stated explicit encoding and the intended domain \(1\leq k\leq|\mathcal C|\). It establishes NP-completeness, using the divisible-profile NP-completeness result supplied in the question.

• Equivalence for a fixed committee. The forward implication is valid: dividing assignment counts by \(n\) gives the required type masses and committee loads because \(q/n=1/k\).

For the reverse implication, the proposed flow satisfies all capacity constraints and conservation equations. In particular, nonnegativity and the type marginal imply \(x_{A,w}\leq\mu_A\), so the capacity \(n\) on an allowed type-to-member arc is sufficient.

• Application of flow integrality. The invoked theorem states that a finite flow network with nonnegative integer capacities has an integral maximum flow. Its hypotheses hold: \(n_A\) and \(n\) are integers, and \(q=n/k\) is an integer by divisibility.

The constructed fractional flow has value \(n\), while the source capacity bounds every flow by \(n\). Therefore the integral maximum flow also has value \(n\). Source and sink arcs are all saturated because each family has total capacity \(n\). This justifies both required integer marginals.

• Recovery of an ordinary assignment. For each type, the integral outgoing flows sum to its number of voters. Partitioning those voters into groups of the specified integer sizes is valid because they share the same approval set. Allowed arcs guarantee approval, and saturated sink arcs guarantee exactly \(q\) voters per committee member. Thus the equivalence holds committee by committee.

• Reduction and encoding size. Grouping an explicitly listed profile by approval set is polynomial-time. The number of resulting types is at most \(n\), and each numerator and denominator has \(O(\log n)\) bits. Preserving candidates and committee size preserves the committee choices, and the established equivalence proves both directions of the reduction. The supplied NP-completeness premise therefore establishes NP-hardness.

• Polynomial verification of a certificate. An explicitly listed committee has polynomial length. Its size and membership in \(\mathcal C\) can be checked directly. The rational-capacity network characterizes feasibility exactly: a flow of value \(1\) saturates every source and sink arc and hence supplies precisely the required marginals. Conversely, feasible fractional variables define such a flow.

Zero-mass types cause no difficulty. A positive-mass type with no approved committee member prevents a value-\(1\) flow, exactly as required by the original constraints.

• Binary arithmetic and running time. Scaling by \(kD\) yields integer capacities \(ka_A(D/b_A)\), \(kD\), and \(D\). The product \(D\) has polynomial bit length even if its numerical value is large. The network has polynomially many vertices and arcs, and polynomial-time maximum-flow algorithms apply to its binary-encoded integer capacities. This establishes a deterministic polynomial-time verifier and therefore membership in NP.

No false statements, unverified theorem applications, or substantive omissions were found. No repair is required. The restriction to positive \(k\) correctly makes explicit the domain already required by \(1/k\).

⟨structured verdict parsed — rendered above⟩