Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
This isn't really voting-theory... –  Rahul May 10 '12 at 18:46

1 Answer 1

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

share|improve this answer
    
Thanks, that is a much better way to state it. But how do you calculate the value of q? I think that's the core of my problem. –  Björn Lindqvist May 10 '12 at 20:22
    
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 don't understand a word of that. –  Björn Lindqvist May 11 '12 at 8:16
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.