Multiwinner Approval Rules as Apportionment Methods (d4-conf-aaai-2017-0069)

Given parties \(i\in[p]\), \(k\) candidates \(C_i\) per party, approval types \(A_i=C_i\), and masses \(\mu_i\ge0\) with \(\sum_i\mu_i=1\), choose a committee \(S\subseteq\bigcup_i C_i\) with \(|S|=k\) and mass assignments \(y_{i,c}\ge0\) satisfying \(y_{i,c}=0\) for \(c\notin S\), \(\sum_{c\in S}y_{i,c}=\mu_i\), and \(\sum_i y_{i,c}=1/k\) for \(c\in S\), maximizing \(\sum_i\sum_{c\in S\cap A_i}y_{i,c}\); output the optimal seat distribution \(x_i=|S\cap C_i|\).

Definitions. Let \(C_1,\ldots,C_p\) be disjoint candidate sets with \(|C_i|=k\). Type \(i\) has rational mass \(\mu_i\ge 0\), with \(\sum_i\mu_i=1\), and approves exactly \(C_i\). Choose \(S\subseteq\bigcup_i C_i\) with \(|S|=k\), and \(y_{i,c}\ge0\) such that \(y_{i,c}=0\) for \(c\notin S\), \(\sum_{c\in S}y_{i,c}=\mu_i\), and \(\sum_i y_{i,c}=1/k\) for every \(c\in S\). Maximize \(\sum_i\sum_{c\in S\cap C_i}y_{i,c}\), and output \(x_i=|S\cap C_i|\).

Target. With the \(\mu_i\) encoded as binary rationals, is computing an optimal seat distribution \(x\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

Nearest known results. In the integral party-list counterpart, when \(k\mid\sum_i v_i\), ordinary Monroe's rule induces the Hamilton (largest-remainder) apportionment method. For arbitrary approval profiles, deciding whether a size-\(k\) committee attains a specified Monroe dissatisfaction threshold is NP-complete.

Computing an optimal seat distribution is in \(\mathrm{P}\). The Hamilton largest-remainder method is optimal for the stated fractional-assignment problem.

Assume \(k\geq 1\), as required by the capacity \(1/k\).

1. Optimal assignment value for a fixed seat distribution.

Fix nonnegative integers \(x_1,\ldots,x_p\) with \(\sum_i x_i=k\). Choose any \(x_i\) candidates from \(C_i\); this is possible because \(x_i\leq k=|C_i|\).

Write \(b_i=x_i/k\). The satisfied mass of type \(i\) cannot exceed either its total mass \(\mu_i\) or the total capacity \(b_i\) of its selected approved candidates. Consequently, every feasible assignment has objective value at most
\[ A(x)=\sum_i\min(\mu_i,b_i). \]

We prove that this bound is attained. Define
\[ a_i=\min(\mu_i,b_i),\qquad u_i=\mu_i-a_i,\qquad v_i=b_i-a_i. \]
These quantities are nonnegative, and
\[ \sum_i u_i=\sum_i v_i=1-\sum_i a_i=:T. \]
Moreover, \(u_i v_i=0\) for every \(i\), since \(a_i\) equals at least one of \(\mu_i,b_i\).

Let \(z_{ij}\) denote the mass assigned from type \(i\) to selected candidates belonging to \(C_j\). If \(T>0\), set
\[ z_{ij}=a_i\mathbf{1}_{i=j}+\frac{u_i v_j}{T}. \]
Its row and column sums are
\[ \sum_j z_{ij}=a_i+u_i=\mu_i, \qquad \sum_i z_{ij}=a_j+v_j=b_j. \]
Also, \(z_{ii}=a_i\), because \(u_i v_i=0\). If \(T=0\), the diagonal assignment \(z_{ii}=a_i\), with all other entries zero, has the same required properties.

For each \(j\) with \(x_j>0\), distribute \(z_{ij}\) equally among the \(x_j\) selected candidates in \(C_j\). Each such candidate receives total mass
\[ \frac{\sum_i z_{ij}}{x_j}=\frac{b_j}{x_j}=\frac1k. \]
If \(x_j=0\), its column sum is zero, so there is nothing to distribute. Thus this defines a feasible assignment satisfying exactly \(\sum_i a_i=A(x)\).

Therefore, the original problem is equivalent to maximizing
\[ \sum_i\min(k\mu_i,x_i) \]
over nonnegative integer vectors with coordinate sum \(k\).

2. An optimal distribution by largest remainders.

Define the quotas, integer parts, and remainders by
\[ q_i=k\mu_i,\qquad f_i=\lfloor q_i\rfloor,\qquad \rho_i=q_i-f_i. \]
Since \(\sum_i q_i=k\), the number
\[ r=k-\sum_i f_i=\sum_i\rho_i \]
is a nonnegative integer.

Choose a set \(R\) of \(r\) indices having the largest remainders, breaking ties arbitrarily, and output
\[ x_i^*=f_i+\mathbf{1}_{i\in R}. \]
For \(r=0\), take \(R\) empty.

This vector is feasible. Its coordinates sum to \(k\). If \(r>0\), there are more than \(r\) positive remainders: if their number is \(m\), then \(r=\sum_i\rho_i<m\), because each positive remainder is strictly less than \(1\). Hence every index in \(R\) has a positive remainder. For such an index, \(q_i\leq k\) and \(q_i\) is nonintegral, so \(f_i+1\leq k\).

To prove optimality, consider the marginal value of the \(t\)-th seat for type \(i\):
\[ d_{i,t}=\min(q_i,t)-\min(q_i,t-1), \qquad 1\leq t\leq k. \]
These marginal values consist of:

• \(f_i\) entries equal to \(1\);
• an entry equal to \(\rho_i\), at position \(f_i+1\), if \(f_i<k\);
• zeros at all subsequent positions.

For every feasible \(x\), telescoping gives
\[ \sum_i\min(q_i,x_i)=\sum_i\sum_{t=1}^{x_i}d_{i,t}. \]
The right-hand side selects exactly \(k\) entries from the multiset of all marginal values. It therefore cannot exceed the sum of that multiset’s \(k\) largest entries.

There are exactly \(F=\sum_i f_i=k-r\) entries equal to \(1\). All other entries are strictly smaller than \(1\). When \(r>0\), the next \(r\) largest entries are precisely the \(r\) largest remainders. Thus the sum of the \(k\) largest marginal values is
\[ F+\sum_{i\in R}\rho_i. \]
The proposed vector \(x^*\) attains this value: it takes all \(f_i\) unit-value seats for every type, and the next seat exactly for indices in \(R\). It is therefore optimal.

3. Polynomial running time with binary rational inputs.

Write each input mass as \(\mu_i=a_i/b_i\), where \(a_i\geq0\) and \(b_i>0\) are binary integers. Compute
\[ f_i=\left\lfloor\frac{k a_i}{b_i}\right\rfloor, \qquad n_i=k a_i-b_i f_i, \qquad \rho_i=\frac{n_i}{b_i}. \]
Remainders can be compared exactly using integer products:
\[ \rho_i\leq\rho_j \quad\Longleftrightarrow\quad n_i b_j\leq n_j b_i. \]

The algorithm performs these computations, sorts the remainders, and increments the \(r\) chosen coordinates. Every integer manipulated has bit length polynomial in the input length, so exact arithmetic and sorting take polynomial time.

The marginal-value multiset was used only in the proof; the algorithm does not construct it or iterate through \(k\) seats. Consequently, the running-time conclusion holds even when \(k\) is binary encoded. The requested vector has \(p\) coordinates, each at most \(k\), and therefore also has polynomial output length.

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the target: computing an optimal seat distribution is in \(\mathrm{P}\), including when \(k\) is binary encoded. No major or minor gaps were found.

• Domain and feasibility.

The assumption \(k\geq 1\) is necessary for the stated capacity \(1/k\). Any nonnegative integer vector with coordinate sum \(k\) automatically satisfies \(x_i\leq k\), so the required candidates can be selected from each \(C_i\). Disjointness ensures these choices form a committee of size \(k\).

• Upper bound for a fixed distribution.

The satisfied mass of type \(i\) is bounded by both \(\mu_i\) and \(b_i=x_i/k\). Summing gives the asserted upper bound \(A(x)=\sum_i\min(\mu_i,b_i)\). This uses precisely the assumption that type \(i\) approves only \(C_i\).

• Attainment of the upper bound.

The residual quantities \(u_i\) and \(v_i\) are nonnegative. Their sums agree because both total mass and total selected capacity equal \(1\). The identity \(u_iv_i=0\) follows directly from the definition of \(a_i\).

For \(T>0\), the proposed matrix is nonnegative, and its row sums, column sums, and diagonal entries are exactly those claimed. In particular, the residual assignment introduces no additional diagonal mass.

For \(T=0\), nonnegativity and zero residual sums imply every residual is zero, so the stated diagonal assignment has the required margins.

Dividing each nonzero column equally among its selected candidates preserves type masses and gives each candidate capacity \(1/k\). When \(x_j=0\), the nonnegative column has sum zero, so all its entries vanish. Thus no mass is lost by omitting that column. The objective is exactly the diagonal sum \(A(x)\).

• Reduction to integer seat optimization.

Multiplying \(A(x)\) by the positive constant \(k\) gives \(\sum_i\min(k\mu_i,x_i)\). Consequently, the reduced objective has exactly the same maximizing distributions. Both the upper bound and its attainment have been established, so this is a complete equivalence.

• Definition and feasibility of largest remainders.

The identity \(r=k-\sum_i f_i=\sum_i\rho_i\) correctly shows that \(r\) is a nonnegative integer.

When \(r>0\), the argument \(r<m\), where \(m\) counts positive remainders, is valid. It guarantees enough indices to choose and ensures every chosen remainder is positive. The resulting increment respects \(x_i^*\leq k\), as shown. Unincremented coordinates also satisfy this bound because \(f_i\leq q_i\leq k\). The coordinates sum to \(k\).

The case \(r=0\) is handled explicitly.

• Marginal-value optimality argument.

The marginal values are described correctly, including integer quotas, zero quotas, and \(q_i=k\). When \(\rho_i=0\), the listed remainder entry is simply zero.

The telescoping identity is valid because \(\min(q_i,0)=0\). Every feasible distribution selects exactly \(k\) marginal entries, so the sum of the globally largest \(k\) entries is a valid upper bound. This bound does not assume that arbitrary selections satisfy the required prefix structure.

There are exactly \(F=k-r\) unit entries. If \(r>0\), the remaining largest \(r\) entries are the largest positive remainders; quotas with \(f_i=k\) have zero remainder and cause no omission relevant to this selection. If \(r=0\), the unit entries already fill all \(k\) positions.

The proposed distribution selects precisely the prefixes attaining this upper bound. Arbitrary tie-breaking among equal remainders preserves the value. Optimality follows.

• Binary-input running time and output size.

The quotient and remainder formulas are exact, and cross multiplication compares remainders correctly because denominators are positive.

Products, quotients, and cross products have bit lengths polynomial in the binary input length. Sorting requires polynomially many such comparisons. Moreover, \(r<p\), so incrementing the selected coordinates does not require a loop of length \(k\).

The proof-only marginal multiset need not be constructed. The output has \(p\) integers bounded by \(k\), hence polynomial length. The assignment construction is used to establish optimality; the task asks only for the seat distribution, so explicitly outputting an assignment is unnecessary.

No external theorem is invoked, and neither nearest known result is needed. No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩