[EM] Extent of quota violation in Webster

[Kristofer Munsterhjelm]

On 01/06/2015 12:41 AM, Toby Pereira wrote:
> Webster's mathematically equivalent to Sainte-Laguë isn't it? I don't
> see why there should be a limit. Let's say you have 100 representatives,
> and one state has 1% of the population and therefore you'd expect the
> state to have one representative. This state could win all the
> representatives, however. To win the 100th representative, it's
> population would have to be over 199 times as great as any other state.
> This could happen if there were enough states (about 20,000). And
> there's no limit to how far you can take this either in terms of
> lowering the percentage of the population in the largest state, or
> increasing the number of representatives.

Yeah, that seems reasonable. So the extent of the violation depends on 
the number of states. Looking at the Sainte-Laguë equivalence, it 
doesn't seem that the extent of quota violation would depend on the 
population, just on the number of states.

The reason I am asking is because I'm looking at polynomial time 
approximation schemes for various NP-hard problems that proportional 
representation can be reduced to. (This is how I came up with the 
Bucklinesque method I mentioned earlier.) These approximation schemes 
usually have approximation factors, e.g. "we can get within a factor of 
log n of the true optimum by violating quota by 1+e". I was thus trying 
to find out the minimum of what such a bound could be if I wanted the 
method to reduce to Webster. But these bounds are usually given as a 
function of n (the population plus the number of candidates) rather than 
a function of the number of seats or states.

One way of looking at it is that Webster permits quota violation in 
return for being population-pair and house monotone. So if the methods 
I'm thinking of can be seen as monotone, a little bit of quota violation 
won't bother me, and probably will be required. But if the quota 
violation is excessive, the method won't be of much use.

Perhaps one could recast the above in terms of a population quota 
violation factor. For the situation above to happen, there must be at 
least 20000 states, and each of these has to have at least one 
representative. So to miss the target by 99 representatives, you need a 
population of at least 20000, and the violation factor will be 99x 
(since the largest state's quota was 1 and it got 99 times that).