Complexity of coalition structure generation (d4-conf-atal-2011-0113)

Given finitely many types \(T\), rational masses \(\mu\in\mathbb{Q}_{\ge0}^{T}\) with \(\sum_t\mu_t=1\), rational per-agent weights \(w_t\), and a rational per-capita quota \(q>0\), partition the unit mass into finitely many profiles \(x^1,\ldots,x^r\in\mathbb{R}_{\ge0}^{T}\) satisfying \(\sum_j x^j=\mu\), maximizing the number of blocks \(j\) with \(\sum_t w_t x^j_t\ge q\), using a compact multiplicity representation for repeated profiles.

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a binary rational weight \(w_t\ge0\); the binary rational quota satisfies \(0<q\le\sum_t w_t\mu_t\), so the whole society is winning.
A coalition structure is any finite list of nonzero profiles \(x^j\in\mathbb R_{\ge0}^{T}\) with \(\sum_jx^j=\mu\). Mass is freely divisible, and a block is winning exactly when \(\sum_tw_tx_t^j\ge q\). Its welfare is the integer number of winning blocks.
An optimal structure maximizes welfare. Represent repeated profiles by pairs \((y^i,c_i)\), with binary rational nonzero profiles \(y^i\) and binary integer multiplicities \(c_i\ge1\), satisfying \(\sum_i c_i y^i=\mu\); multiplicities count separate blocks. Losing blocks are permitted.
Let \(L\) be the total input bit length. State running times in \(\tau\) and \(L\); there is no separate parameter \(m\) in this scalar-weight problem.

Is computing an optimal coalition structure for this continuous weighted voting problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?

For finite indivisible players, deciding whether welfare at least \(k\) is attainable is \(\mathrm{NP}\)-complete, and optimization is strongly \(\mathrm{NP}\)-hard. [Aziz and de Keijzer](https://arxiv.org/pdf/1101.1007).
A related splittable bin-covering model is polynomial-time solvable, but uses restricted assignments and proportional credit for partially covered bins. [Hellwig and Souza](https://arxiv.org/pdf/1109.3544). No result settling this exact continuous formulation was located.

Result

Computing an optimal coalition structure is in \(\mathrm P\). In fact, one repeated profile suffices.

Write \(W=\sum_{t\in T}w_t\mu_t\) for the society’s total weight. The optimal welfare is
\(\displaystyle K=\left\lfloor\frac{W}{q}\right\rfloor\),
and an optimal compressed structure is the single pair \(\displaystyle (\mu/K,K)\).

This construction uses precisely the stated freedom to divide every type’s mass.

Proof of optimality

Upper bound. Consider any feasible coalition structure \(x^1,\ldots,x^r\), and let \(J\) index its winning blocks. Its welfare is the integer \(h=|J|\). Each winning block has weight at least \(q\), so

\(\displaystyle hq\le\sum_{j\in J}\sum_{t\in T}w_tx_t^j\le\sum_{j=1}^{r}\sum_{t\in T}w_tx_t^j=\sum_{t\in T}w_t\mu_t=W.\)

The second inequality follows from nonnegativity of all weights and profiles; the equality follows from conservation of each type’s mass. Since \(q>0\), we obtain \(h\le\lfloor W/q\rfloor=K\). This bound applies even to structures with irrational profiles and arbitrarily many losing blocks.

Attainment. The hypothesis \(W\ge q>0\) gives \(K\ge1\). Define \(y_t=\mu_t/K\) for every \(t\in T\), and take \(K\) separate copies of \(y\).

Every coordinate of \(y\) is positive and rational, so the profile is nonzero. Conservation holds coordinatewise: \(Ky_t=\mu_t\). Moreover, each block has weight

\(\displaystyle \sum_{t\in T}w_ty_t=\frac{W}{K}\ge q,\)

because \(Kq\le W\). Thus all \(K\) blocks are winning. Together with the upper bound, this proves optimality.

Exact algorithm and bit complexity

Write the input rationals as \(w_t=a_t/d_t\), \(\mu_t=b_t/e_t\), and \(q=h/f\), with positive integer denominators. Compute

\(\displaystyle D=\prod_{t\in T}d_te_t,\qquad N=\sum_{t\in T}a_tb_t\frac{D}{d_te_t}.\)

Each quotient in this sum is an integer, and \(W=N/D\). Therefore exact integer division gives

\(\displaystyle K=\left\lfloor\frac{Nf}{Dh}\right\rfloor.\)

Output the single pair \((y,K)\), with coordinates \(y_t=b_t/(e_tK)\).

All integers in these computations have \(O(L)\) bits: products accumulate at most the total input bit length, and summing \(\tau\) terms adds at most \(O(\log\tau)\) bits. The same bound holds for \(K\) and each output numerator and denominator.

The algorithm uses \(O(\tau)\) integer arithmetic operations. With schoolbook multiplication and division, its running time is \(O(\tau L^2)\) bit operations, and its compressed output has \(O(\tau L)\) bits. If reduced fractions are required, computing greatest common divisors preserves this running-time bound.

The multiplicity encoding matters: with \(\tau=1\), \(\mu_1=w_1=1\), and \(q=2^{-b}\), the optimum contains \(2^b\) blocks, but the single pair \((2^{-b},2^b)\) has \(O(b)\) bits.

Relation to the indivisible model

The finite-player model partitions a set of indivisible players into coalitions ([Aziz and de Keijzer](https://arxiv.org/pdf/1101.1007)). Here, dividing every type equally among all blocks attains the total-weight bound directly, so that model’s hardness does not transfer to this formulation.

⟨structured verdict parsed — rendered above⟩

The output correctly resolves the assigned problem: computing an optimal coalition structure is in \(\mathrm P\) under the specified compressed representation. The proof and bit-complexity bounds are rigorous. No major or minor issues were found.

• Upper bound on welfare. For any feasible finite structure, each winning block contributes at least \(q\) weight. Nonnegative weights and profiles justify bounding the total weight of winning blocks by the total weight of all blocks. Coordinatewise conservation then gives \(hq\le W\). Since \(q>0\) and \(h\) is an integer, \(h\le\lfloor W/q\rfloor\). This argument covers real, including irrational, profiles and any finite number of losing blocks.

• Validity of the construction. The input promise \(W\ge q>0\) ensures that \(K=\lfloor W/q\rfloor\) is a positive integer, so division by \(K\) is defined. Each coordinate \(y_t=\mu_t/K\) is a positive rational, making \(y\) an admissible nonzero profile. The pair \((y,K)\) represents a finite list of \(K\) separate blocks, and \(Ky_t=\mu_t\) verifies conservation for every type.

• Attainment and optimality. Every represented block has weight \(W/K\ge q\), because \(Kq\le W\) and \(K>0\). Thus its welfare is exactly \(K\), matching the upper bound. Zero-weight types cause no problem: their positive mass is distributed with the other coordinates, and the winning condition follows from total weight. The boundary cases \(W=q\) and integral \(W/q\) are also covered by the stated inequalities.

• Exact arithmetic. With the stated rational encodings, \(D\) is positive and divisible by every \(d_te_t\). Consequently, every summand defining \(N\) is an integer, and \(N/D=W\). Since the quota numerator \(h\) and denominator \(f\) are positive, integer division of \(Nf\) by \(Dh\) computes precisely \(\lfloor W/q\rfloor\). The output coordinates \(b_t/(e_tK)\) represent the constructed profile exactly.

• Bit lengths and running time. The bit length of each product is bounded by the sum of the bit lengths of its factors. The factors in each relevant product come from the input, so these products have \(O(L)\) bits. Summing \(\tau\) terms adds at most \(O(\log\tau)\) bits, which remains \(O(L)\) because the input explicitly lists \(\tau\) types. This also bounds \(Nf\), \(Dh\), \(K\), and each output coordinate’s numerator and denominator. There are \(O(\tau)\) integer arithmetic operations on \(O(L)\)-bit integers, giving the claimed \(O(\tau L^2)\) bound with schoolbook arithmetic. Fraction reduction by classical greatest-common-divisor computation fits the same bound.

• Representation and scope. The compressed output has the claimed \(O(\tau L)\) bit bound. The example with quota \(2^{-b}\) correctly illustrates why explicitly listing every block could require exponentially many entries while the required representation remains polynomial in size. The discussion of indivisible players is consistent with the distinction stated in the task and is not used as a premise of the proof. No external theorem is needed for the continuous result.

No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩