0

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}$

siamii
  • 277

2 Answers2

1

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)$

Ross Millikan
  • 374,822
  • is $\Delta n \in {-1,0,1}$ ? – siamii Mar 10 '14 at 19:25
  • It is not guaranteed. We have the sum of the unrounded $r$'s is $n$, but you could round a lot of them up. Suppose $n=20$ and the unrounded $r$'s have $12$ at $0.6, 8$ at $1.6$ The rounded $r$'s will have $12\ 1$'s and $8\ 2$'s, giving $\Delta n=8$ In this example it is not obvious what the correct final answer is. – Ross Millikan Mar 10 '14 at 22:51
0

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$.

Guy
  • 8,857
  • 1
  • 28
  • 57
  • The result must be a list of integers that sum to $n$ – siamii Mar 10 '14 at 16:03
  • alternately round up and down. – Guy Mar 10 '14 at 16:05
  • should work imo. – Guy Mar 10 '14 at 16:07
  • I have updated the question, can you please elaborate when to round up or down? – siamii Mar 10 '14 at 16:08
  • @siamii I have update my answer. It doesn't matter if you reverse the order of rounding up and down though. – Guy Mar 10 '14 at 16:15
  • Alternately rounding may not help. If $n=10$, you could have the first $9 b_i$'s be $0.101$ and the last one be $0.091$. Then multiplying by $10$ gives $1.01$ for the first $9$ and $0.91$ for the last. If I round up even four of the first $9$, I get $13$ seats assigned before I get to the tenth. – Ross Millikan Mar 10 '14 at 16:22
  • @RossMillikan ah! dammit, i always forget the extreme cases. random testing isn't so good after all. +1 to your answer. – Guy Mar 10 '14 at 18:43