[EM] Mr.SODA

[Kristofer Munsterhjelm]

fsimmons at pcc.edu wrote:
> In the discussion of a proportional representation version of SODA it
> was lamented that the non- sequential version of PAV was
> computationally hard, and was suggested to make use of  the PAV 
> measure of goodness to pick the winning slate from all of the slates
> that anybody cared to nominate.
> 
> While that would certainly be feasible and very likely near optimal,
> another possibility is to use non- sequential PAV to choose the first
> three members of the slate, and then choose the remaining members 
> sequentially, conditioned on the membership of the first three as
> well as those chosen subsequently.
> 
> The number of slates of size three is only  n*(n-1)*(n-2)/6 , which
> is less than five million when there are (n=)three hundred
> candidates.
> 
> If the members of the senate were chosen this way, the first three
> could be a kind of triumvirate presidency of the senate.

You could also do this to get a hybrid of sequential and non-sequential
PAV. Decide on a chunk size k, then you calculate the first k winners
non-sequentially (n choose k for n candidates). Lock these (i.e. decide
they'll win), then try every council of size min(k*2, desired size) with
these locked. Then min(k*3, desired size), min(k*4, desired size), etc,
until you have elected as many as you want.

Sequential PAV is just this kind of PAV with k=1. k=2 or k=3 should be
feasible even with very large values of n, and would approximate true
PAV better than would ordinary sequential PAV.

So, for instance, if you want to elect eight winners out of A-Z with
k=3, you'd first do

elect ??? -> say the optimum here is ABC, then
elect ABC??? -> say the optimum is ABCDFG, then
elect ABCDFG?? -> say the optimum is ABCDFGKQ, and then that's your outcome.