The Maximin Support Method: An Extension of the D'Hondt Method to Approval-Based Multiwinner Elections (d4-conf-aaai-2021-0219)

Given a finite candidate set \(C\), committee size \(k\), finite approval-type set \(T\), and rational masses \(\mu_t\ge0\) with \(\sum_{t\in T}\mu_t=1\), choose an integral committee \(W\subseteq C\) with \(\lvert W\rvert=k\) maximizing \(M_\mu(W)=\max_f\min_{c\in W}\sum_{t:c\in t}\mu_t f_{t,c}\), where \(f_{t,c}\ge0\), \(f_{t,c}=0\) when \(c\notin t\), and \(\sum_{c\in t\cap W}f_{t,c}=1\) for every positive-mass type intersecting \(W\).

Let \(C\) be a candidate set with \(m=|C|\) and \(1\le k\le m\). A society is given by its support: a list \(T\subseteq 2^C\) of \(\tau\) distinct approval types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible approval types. Require \(\sum_{t:c\in t}\mu_t>0\) for every \(c\in C\); empty approval types are allowed.
For an integral committee \(W\subseteq C\) with \(|W|=k\), a support assignment has real variables \(f_{t,c}\ge0\) for \((t,c)\in T\times W\), with \(f_{t,c}=0\) when \(c\notin t\) and \(\sum_{c\in t\cap W}f_{t,c}=1\) whenever \(t\cap W\ne\varnothing\). Types disjoint from \(W\) contribute nothing.
Define \(M_\mu(W)=\max_f\min_{c\in W}\sum_{t:c\in t}\mu_t f_{t,c}\). Given also a binary rational threshold \(q\ge0\), decide whether some such committee satisfies \(M_\mu(W)\ge q\). Let \(L\) be the total input bit length; state running times in \(m,\tau,k,L\).

Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For finite unit-weight electorates, global maximin support maximization coincides with max-Phragmén and is NP-hard. [Source](https://doi.org/10.1007/s10107-022-01805-8)
Positive real voter strengths with fractional support assignments have already been studied for this same objective, including NP-hardness; the normalized rational formulation is a specialization of that model, so the requested complexity target is already settled. [Source](https://arxiv.org/html/2004.12990v3)

Result

The decision problem is \(\mathrm{NP}\)-complete, even when all masses are equal and every approval type contains exactly two candidates. Consequently, it is polynomial-time solvable if and only if \(\mathrm{P}=\mathrm{NP}\).

The hardness proof below normalizes the reduction in Theorem 9 of [Cevallos and Stewart](https://arxiv.org/html/2004.12990v3#S3). It directly satisfies the requirement that the input lists distinct support types.

Polynomial-time verification of a committee

Fix a committee \(W\) with \(|W|=k\). The feasible assignments form a nonempty product of simplices: for each type intersecting \(W\), its fractions are nonnegative and sum to one. This set is compact, and the minimum candidate support is continuous. Thus the maximum defining \(M_\mu(W)\) is attained.

Construct a directed network with source \(s\), one vertex for each \(t\in T\), one vertex for each \(c\in W\), and sink \(z\). Its arcs and capacities are:

• \(s\to t\), with capacity \(\mu_t\);
• \(t\to c\), with capacity \(1\), whenever \(c\in t\cap W\);
• \(c\to z\), with capacity \(q\).

We claim that
\[ M_\mu(W)\ge q \quad\Longleftrightarrow\quad \text{the network admits a flow of value }kq. \]

Forward direction. Given a qualifying assignment, initially send mass \(\mu_t f_{t,c}\) from \(t\) to \(c\). Each candidate receives at least \(q\). For each candidate separately, retain exactly \(q\) of its incoming mass and delete the excess. Send the retained row totals from \(s\) to the types and send \(q\) from every candidate to \(z\). This respects all capacities and gives flow value \(kq\).

Reverse direction. A flow of value \(kq\) saturates every candidate-to-sink arc, since their total capacity is \(kq\). Write \(x_{t,c}\) for its type-to-candidate flows. Then
\[ \sum_{c\in t\cap W}x_{t,c}\le\mu_t, \qquad \sum_{t:c\in t}x_{t,c}=q \quad(c\in W). \]
For every type intersecting \(W\), allocate its unused mass to any one candidate in that intersection. This only increases candidate supports. Dividing each resulting allocation by the positive number \(\mu_t\) gives the required fractions \(f_{t,c}\), with every active row summing to one.

This proves the claim, including the distinction between flow capacities and the problem’s requirement to allocate all active mass.

Exact running times and membership in \(\mathrm{NP}\)

For every assignment, total candidate support is at most \(1\), so \(M_\mu(W)\le 1/k\). Therefore \(q=0\) is immediately a yes-instance, and \(q>1/k\) is immediately a no-instance.

For other thresholds, the network has at most
\[ V_*=\tau+k+2, \qquad E_*=\tau k+\tau+k \]
vertices and arcs, respectively.

Multiply capacities by the product \(D\) of the input denominators. This produces integer capacities. Because the sum of the denominators’ bit lengths is at most \(L\), both \(D\) and all scaled capacities have \(O(L)\) bits. Exact integer max flow therefore avoids any numerical approximation.

Edmonds–Karp uses \(O(V_*E_*^2)\) arithmetic operations, independently of capacity magnitudes. Including network construction, denominator scaling, and elementary integer arithmetic, a conservative bit-time bound for checking one committee is
\[ O\!\left( \bigl[m\tau+(\tau+k+2)(\tau k+\tau+k)^2\bigr](L+1)^2 \right). \]

A certificate need only specify \(W\), using \(O(k\log(m+1))\) bits. The verifier checks its size and runs this exact flow test. Hence the decision problem belongs to \(\mathrm{NP}\), despite allowing real support fractions.

Enumerating all committees gives an exact deterministic algorithm with running time
\[ O\!\left( \binom{m}{k} \bigl[m\tau+(\tau+k+2)(\tau k+\tau+k)^2\bigr](L+1)^2 \right). \]

Hardness for normalized, distinct support types

Use the known \(\mathrm{NP}\)-complete problem of deciding whether a nonempty simple cubic graph \(G=(V,E)\) has an independent set of size \(k\), with \(1\le k\le |V|\).

Set \(C=V\), and write \(N=|E|\). For each edge \(e=\{u,v\}\), introduce approval type \(t_e=\{u,v\}\), with
\[ \mu_{t_e}=\frac1N, \qquad q=\frac3N. \]
Simplicity ensures distinct types. Their masses sum to \(1\), and every candidate has positive approval mass \(3/N\).

If \(W\) is independent, every type intersecting \(W\) contains exactly one selected candidate. Assign its entire mass there. Each selected candidate receives \(3/N=q\).

Conversely, if \(W\) contains adjacent vertices \(u,v\), exactly five edges are incident to at least one of them. Each corresponding type contributes at most \(1/N\) to their combined support. Thus every assignment satisfies
\[ \operatorname{supp}_f(u)+\operatorname{supp}_f(v)\le\frac5N, \qquad \min_{c\in W}\operatorname{supp}_f(c) \le\frac{5}{2N}<q. \]
Therefore a qualifying committee exists exactly when the graph has the required independent set.

Here \(m=|V|\) and \(\tau=N=3m/2\). Masses and threshold have \(O(\log m)\)-bit encodings; even a dense incidence representation has polynomial length. The construction is consequently a polynomial-time many-one reduction.

Conclusion

The reduction proves \(\mathrm{NP}\)-hardness under the stated normalization and support requirements. Exact polynomial-time committee verification proves membership in \(\mathrm{NP}\). Together they settle the target question.

⟨structured verdict parsed — rendered above⟩

Verdict

The prover establishes the claimed \(\mathrm{NP}\)-completeness, including the restriction to equal masses and distinct approval types of size two. The flow characterization, exact verification algorithm, and hardness reduction are correct. No major or minor mathematical issues were found.

Step-by-step verification

1. Existence of an optimal support assignment

For every type intersecting \(W\), the permitted fractions form a nonempty simplex. All remaining variables are forced to zero. Thus the full feasible set is nonempty and compact.

Each candidate’s support is a linear function of these variables, and the minimum of finitely many continuous functions is continuous. Therefore the maximum defining \(M_\mu(W)\) is attained.

This justifies using an assignment attaining at least \(q\) whenever \(M_\mu(W)\ge q\).

2. Network construction and forward implication

The network correctly includes precisely the permitted type-to-candidate connections.

For a qualifying assignment, the proposed initial allocation satisfies
\[ \sum_{c\in t\cap W}\mu_t f_{t,c}\le\mu_t. \]
Each individual allocation is at most \(\mu_t\le1\), so the capacity \(1\) on each type-to-candidate arc is sufficient.

Retaining exactly \(q\) at each candidate is possible because its initial incoming mass is at least \(q\). Deleting incoming mass only decreases each type’s outgoing total. Setting the source-to-type flows equal to the retained totals restores conservation at every type, while sending \(q\) to the sink restores conservation at every candidate.

The resulting feasible flow has value \(kq\). This implication is correct.

3. Reverse implication and full allocation requirement

A flow of value \(kq\) must saturate every candidate-to-sink arc: these arcs have total capacity exactly \(kq\).

Flow conservation then gives the stated row inequalities and candidate equalities. Every active type has unused mass
\[ \mu_t-\sum_{c\in t\cap W}x_{t,c}\ge0. \]
Its intersection with \(W\) is nonempty, so the prover’s instruction to allocate this mass to one candidate is well-defined. This adjustment makes its row total exactly \(\mu_t\) and never decreases any candidate’s support.

Division by \(\mu_t\) is valid because every mass is positive. The resulting fractions satisfy all support-assignment constraints. Inactive types contribute nothing.

The flow equivalence is fully established, including the requirement to allocate all active mass.

4. Thresholds and edge cases

The sum of candidate supports equals the mass of types intersecting \(W\), which is at most \(1\). Consequently, the stated bound \(M_\mu(W)\le1/k\) is correct.

The immediate decisions are also correct:

• At \(q=0\), any committee of the required size qualifies.
• At \(q>1/k\), no committee qualifies.
• Empty approval types create no difficulty: their network vertices cannot send flow to candidates.
• The arguments apply to both \(k=1\) and \(k=m\).

No unsupported positivity assumption about committee support is needed.

5. Exact arithmetic and running times

The vertex and arc bounds are correct:
\[ V_*=\tau+k+2,\qquad E_*=\tau k+\tau+k. \]

Multiplying by the product of the rational denominators makes every capacity integral. That product has \(O(L)\) bits because its logarithm is bounded by the total denominator encoding length. Scaled capacities likewise have \(O(L)\) bits.

The invoked Edmonds–Karp bound applies to this finite directed network with nonnegative integer capacities. Its bound of \(O(V_*E_*^2)\) arithmetic operations is independent of capacity magnitudes. Residual capacities and flow values have polynomially bounded bit lengths, so the additional factor \((L+1)^2\) safely covers elementary exact arithmetic and scaling.

The displayed bound for committee verification is therefore a valid conservative bit-time upper bound. Multiplying it by \(\binom{m}{k}\) gives the claimed enumeration bound.

A committee is a polynomial-length certificate, and the exact verifier runs in polynomial time. Hence membership in \(\mathrm{NP}\) is established without requiring real-valued fractions as part of the certificate.

6. Hardness source and reduction validity

The prover explicitly states the source problem and its restrictions. The cited [Theorem 9 proof of Cevallos and Stewart](https://arxiv.org/html/2004.12990v3#S3) uses independent set on cubic graphs and the same edge-to-approval construction. The normalization in the submitted proof is consistent with that construction.

For a nonempty simple cubic graph, \(N>0\), so all displayed masses and the threshold are defined. Simplicity guarantees distinct two-element approval types. Cubic degree guarantees positive approval mass \(3/N\) for every candidate. The masses sum to \(1\), and the construction has polynomial encoding length.

7. Both directions of the hardness equivalence

If \(W\) is independent, each edge touching \(W\) has exactly one selected endpoint. Allocating its mass to that endpoint gives each selected vertex support \(3/N=q\). This direction is correct.

If \(W\) contains adjacent vertices \(u,v\), their incident edge sets have sizes three and share exactly their mutual edge. Their union therefore has exactly five edges.

Only those five types can support \(u\) or \(v\), and each contributes at most \(1/N\) to their combined support. Thus the combined-support bound \(5/N\) is correct, regardless of any other selected vertices. It follows that
\[ \min_{c\in W}\operatorname{supp}_f(c) \le\frac{5}{2N}<\frac3N=q \]
for every assignment.

This establishes the exact yes/no equivalence required for a polynomial-time many-one reduction.

Repair feedback

No mathematical repair or additional clarification is required. The proof settles the requested complexity classification and supplies valid running-time bounds.

⟨structured verdict parsed — rendered above⟩