| In France, regional elections are run in the following way. There
are a number of parties, P; voters, V; and seats, S. Each party consists
of an ordered (arbitrarily large) list of candidates. Each voter votes for
exactly 1 party.
k = ceiling(V/S) denotes the number of votes required to win a seat.
Let V_i be the number of votes for party i. s_i = floor(V_i/k) seats are
immediately allocated to party i. The top i candidates from the party i list
are hence elected. party i has r_i = V_i - k*(V_i/k) votes remaining, being
considered to have "spent" the rest. There are r = S - sum(i)(s_i) seats
remaining to be allocated. They are allocated to the r parties who have the
greatest r_i. (ie, the parties effectively bid with their remaining votes for
the remaining seats.) Each party can thus win at most 1 bonus seat this way,
on top of the s_i seats they won earlier. Ties in competition for the bonus
seats are resolved by lot.
Let's make it concrete with an example. Suppose 4 parties are
fighting for 6 seats, and have received 7,8,9,10 votes respectively. It will
cost ceiling(34/6) = 6 votes to buy each seat. This means that each party
gets a seat, and they have 1,2,3,4 votes over. Two of the parties can buy
the remaining two seats with 3&4 votes respectively.
Suppose that the votes have been cast. Can you construct a situation
where increasing by 1 the total number of seats would have the effect of
*reducing* the number of seats that a certain party, the Unlucky Party, would
win? Can you construct a situation where increasing by 1 the number of
votes won by a certain party, the Very Unlucky Party, would *reduce* the number
of seats the VUP would win?
Andrew.
|
| > Suppose that the votes have been cast. Can you construct a situation
>where increasing by 1 the total number of seats would have the effect of
>*reducing* the number of seats that a certain party, the Unlucky Party, would
>win? Can you construct a situation where increasing by 1 the number of
>votes won by a certain party, the Very Unlucky Party, would *reduce* the number
>of seats the VUP would win?
The first situation can happen.
Let there be three parties with V=111 voters and S=11 seats.
Call the parties A (the unlucky party), B, and C. Let the
vote count be A - 23, B - 44, C - 44. (That does total V=111.)
There will be ceiling(V/S) = ceiling(111/11) = ceiling(10+) = 11
votes needed per seat, so the seats parcel out as
A - 2 remainder 1
B - 4 remainder 0
C - 4 remainder 0
That's only 10 of the S=11 seats, so A gets a third seat, and the
seat distribution ends up A - 3, B - 4, C - 4.
Now add a seat to get S' = 12 seats. The new "price" per seat
is now ceiling(V/S') = ceiling(111/12) = ceiling(9+) = 10 votes
per seat. So the same vote count A - 23, B - 44, C - 44 yields
A - 2 remainder 3
B - 4 remainder 4
C - 4 remainder 4
The full seats only total 10, but the 2 left over now go to B and C,
with a final seat distribution of A - 2, B - 5, C - 5.
Dan
|
| > Suppose that the votes have been cast. Can you construct a situation
>where increasing by 1 the total number of seats would have the effect of
>*reducing* the number of seats that a certain party, the Unlucky Party, would
>win? Can you construct a situation where increasing by 1 the number of
>votes won by a certain party, the Very Unlucky Party, would *reduce* the number
>of seats the VUP would win?
I can interpret the second situation two different ways. One
interpretation has two completely different scenarios with the
same V (number of voters) and S (number of seats). The first
scenario, party A gets m votes yielding n seats, and in the second
scenario, party A gets m+1 votes yielding n-1 seats. Other aspects
of the scenarios, such as the number of parties and how many votes
they get, can differ.
The second interpretation is to fix a scenario with V voters,
S seats, and P parties with vote counts v1 + v2 + ... + VP = V.
Now change this by adding one new voter who votes for party 1,
resulting in V+1 voters, S seats, and P parties with vote counts
(v1+1) + v2 + ... + vP = V+1. Can party 1 end up with fewer
seats?
Which of the two interpretation did you have in mind? An example
for the first would be rather easy: 41 voters, 2 seats, 2 parties
with vote totals A-11, B-30 (resulting in one seat each). If party
B splits and loses a vote to A, then A-12, B1-15, B2-14 results in
A getting one more vote but no seats (one fewer seat).
Dan
|
|
Yes, it is possible for a Very Unlucky Party to exist.
Let the VUP have V votes out of a total of nS for some integral n.
Then seats = V/k.
If we increase VUP's votes by 1, we have (V+1) votes, but the divisor
is now k+1.
If V/k - (V+1)/(k+1) > 1 then we have lost seats.
This happens if V > k^2 + 2*k.
For example, suppose 25 seats and 6 parties.
Case (A): 275 votes cast, as follows:
v_i = (250,5,5,5,5,5)
k = ceiling(275/25) = 11
s_i = (22,0,0,0,0,0)
r_i = (8,5,5,5,5,5)
seats = (23,1,1,0,0,0)
Now suppose the first party gets an extra vote:
v_i = (251,5,5,5,5,5)
k = ceiling(276/25) = 12
s_i = (20,0,0,0,0,0)
r_i = (11,5,5,5,5,5)
seats = (21,1,1,1,1,0)
And the party is two seats worse off.
Interestingly, if you scale this example up to (say) v_i =
(1000,20,20,20,20,20) and seats = 100 then you end up with vacant seats
that cannot be allocated within the terms of the problem.
|