0
$\begingroup$

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.

  • 0
    This isn't really [tag:voting-theory]...2012-05-10

1 Answers 1

2

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

  • 0
    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.2012-05-10
  • 0
    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.2012-05-11
  • 0
    I don't understand a word of that.2012-05-11
  • 0
    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$.2012-05-11
  • 0
    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$.2012-05-11
  • 0
    I still don't get it. You have a sorted vector y and S which is the sum of the previous indices values? I can figure out how you calculate the values of the function g() over the values in y, but I dont see how that helps to calculate q. In case v = {160, 400, 20, 80}, u = {168, 672, 0, 0} and t = 180, q should be 92 which is not given by your calculation.2012-05-15
  • 0
    In that case, after sorting, ${\bf y} = [272,80,20,8]$. $S_0 = 0$, $S_1 = 272$, $S_2 = 352$, $S_3 = 372$, $S_4 = 380$. $g(272) = 272 - 272 = 0$, $g(80) = 352 - 2 \times 80 = 192$, $g(20) = 372 - 3 \times 20 = 312$, $g(8) = 380 - 4 \times 8 = 348$. Now we interpolate linearly between $(272,0)$ and $(80,192)$: $t = 180 = (1/16) 0 + (15/16) 192$ where $15/16 = \dfrac{180-0}{192-0}$ so $q = (1/16) \times 272 + (15/16) \times 80 = 92$.2012-05-15