Divide $n$ seats by a list of $\mathbf{w}$ weights proportionally.

Question

I have $n$ number of seats and I have list of weights $\mathbf{w} \in \mathbb{R}^{k}$ which is a probability distribution with $k$ possible values, $\sum_{i=1}^k{w_i}=1$. I want to divide the $n$ seats proportional to the weights as much as possible. An example might be, given a set of political parties and the fraction of votes they won, how many seats should they be assigned such that their seats number approximates their weight as best as possible. I'm looking for an algorithm with complete description. The result will be a list of elements $\mathbf{r} \in \mathbb{N}^k$ such that $\sum_{i=1}^k r_i = n$ and $\mathbf{r} \propto \mathbf{w}$

Answer 1

We call the list of weights $S$ and denote the individual weights by $a_i$. Let $$\sum_{i=1}^{\mathbb w}a_i = T$$

Hence divide each $a_i$ by T to 'normalize' the weights. Now each new $b_i =\frac{a_i}{T}$ is a percentage. Multiply by $n$.

To make them integers round up and down, alternately. It doesn't matter in which order. A good strategy would be round up all numbers for $i=1,3,5,7\cdots$ and round down for $i=2,4,6,8\cdots$ In all cases this should lead to a total of $n$. But to be on the safe side, when you reach the last $i$, instead of calculating as $a_i*n/T$, sum all previous as signings and subtract from n. This is guaranteed to lead to a total of $n$.

Answer 2

Initially set $r_i=nw_i$ and round to the closest number. Then add up the $r_i$'s and check against $n$. If they are equal, you are done. If not let $\Delta n=\sum_i r_i-n$ be the number of seats of excess. If $\Delta n$ is positive, rank the $r_i$'s by how much they were rounded up and decrease the $\Delta n$ largest round ups. If $\Delta n$ is negative, increase the $\Delta n$ that had the largest round down. For an example, let $n=5, \mathbf{w}=(0.12,0.14,0.16,0.18,0.4)$ Then $\mathbf{r}=(1,1,1,1,2)$, rounded from $(0.6,0.7,0.8,0.9,2)$ We have assigned six seats instead of $5$. Since the first was rounded up the most, our final result is $\mathbf{r}=(0,1,1,1,2)$