Getting as close to a target vector as possible

Say I have P number of political parties in an election that I'm trying to rig. My boss has decided what number of percentage of the votes it is best that each party should get. N number of votes have already been cast and it has already been publicly known what party they cast their votes. I have X votes remaining and I need to calculate how to cast them in an as "fair" way as possible. That is, if a party is supposed to get 25% of the votes and I can't make that happen with my remaining votes, my cheat votes should be distributed in a way that makes their share as close as possible to that number. But it is better if two parties suffer a 3% point deviation from their target rather than one suffering 6% point and the other 0%.

Also, to make the problem more interesting (if it is to easy) the acceptable deviation should be proportional to the size of the party target. It is better if a party that should have gotten 45% gets 40% rather than one that should have gotten 5% gets 1% because its absolute size is smaller so the deviation matters much more.

• This isn't really voting-theory... – Rahul May 10 '12 at 18:46

So: you are given a vector $\bf v$ (the votes already cast) and a "target" vector $\bf u$ (the desired results) and you want to find a vector $\bf x$ satisfying constraints all $x_i \ge 0$, $\sum_i x_i = t$ (the number of votes you have available) to minimize some (incompletely specified) notion of distance between ${\bf x}+\bf v$ and $\bf u$. If you use the Euclidean distance $d({\bf x},{\bf y}) = \left(\sum_i (x_i-y_i)^2\right)^{1/2}$, this is a constrained least-squares problem. For other metrics, it's a convex programming problem. An obvious strategy (which I think provides the optimal solution at least in the least-squares case) is to take $x_i = \max(u_i - v_i - q, 0)$ where $q$ is chosen so that $\sum_i x_i = t$.
• Sort $y_i = u_i-v_i$ into decreasing order. If $g(q) = \sum_i \max(y_i - q, 0)$, then $g(y_k) = \sum_{i \le k} (y_i - y_k) = S_k - k y_k$ where $S_k = \sum_{i=1}^k y_i$. Find $k$ so $g(y_k) \ge t \ge g(y_{k+1})$ and interpolate linearly. – Robert Israel May 11 '12 at 1:52
• I should have added, if there are $n$ parties then $g(q) = S_n - n q$ for $q < y_n$. For example, suppose ${\bf v} = [100, 200, 300]$, ${\bf u} = [300, 250, 400]$, and $t = 150$. ${\bf y} = [200,50,100]$: after sorting, this is $[200,100,50]$. Then $S_0 = 0$, $S_1 = 200$, $S_2 = 200+100=300$, $S_3 = 300+50=350$. So $g(200) = 200- 200 = 0$, $g(100) = 300 - 2\times 100 = 100$, $g(50) = 350 - 3 \times 50 = 200$. Since $t = 150 = (1/2) 100 + (1/2) 200$, $q = (1/2) 100 + (1/2) 50 = 75$. Thus $x_1 = 200 - 75 = 125$, $x_2 = 0$ (because $50 - 75 < 0$), $x_3 = 100 - 75 = 25$. – Robert Israel May 11 '12 at 18:15
• On the other hand, if $t=260$, for $q < 50$ we have $g(q) = 350 - 3 q$, and this is $260$ when $q = 30$, so in that case $x_1 = 200 - 30 = 170$, $x_2 = 50 - 30 = 20$, $x_3 = 100 - 30 = 70$. – Robert Israel May 11 '12 at 18:20