<div class="gmail_quote">2011/6/19 Kristofer Munsterhjelm <span dir="ltr"><<a href="mailto:km_elmet@lavabit.com">km_elmet@lavabit.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<div><div></div><div class="h5"><a href="mailto:fsimmons@pcc.edu" target="_blank">fsimmons@pcc.edu</a> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
In the discussion of a proportional representation version of SODA it<br>
was lamented that the non- sequential version of PAV was<br>
computationally hard, and was suggested to make use of  the PAV measure of goodness to pick the winning slate from all of the slates<br>
that anybody cared to nominate.<br>
<br>
While that would certainly be feasible and very likely near optimal,<br>
another possibility is to use non- sequential PAV to choose the first<br>
three members of the slate, and then choose the remaining members sequentially, conditioned on the membership of the first three as<br>
well as those chosen subsequently.<br>
<br>
The number of slates of size three is only  n*(n-1)*(n-2)/6 , which<br>
is less than five million when there are (n=)three hundred<br>
candidates.<br>
<br>
If the members of the senate were chosen this way, the first three<br>
could be a kind of triumvirate presidency of the senate.<br>
</blockquote>
<br></div></div>
You could also do this to get a hybrid of sequential and non-sequential<br>
PAV. Decide on a chunk size k, then you calculate the first k winners<br>
non-sequentially (n choose k for n candidates). Lock these (i.e. decide<br>
they'll win), then try every council of size min(k*2, desired size) with<br>
these locked. Then min(k*3, desired size), min(k*4, desired size), etc,<br>
until you have elected as many as you want.<br>
<br>
Sequential PAV is just this kind of PAV with k=1. k=2 or k=3 should be<br>
feasible even with very large values of n, and would approximate true<br>
PAV better than would ordinary sequential PAV.<br>
<br>
So, for instance, if you want to elect eight winners out of A-Z with<br>
k=3, you'd first do<br>
<br>
elect ??? -> say the optimum here is ABC, then<br>
elect ABC??? -> say the optimum is ABCDFG, then<br>
elect ABCDFG?? -> say the optimum is ABCDFGKQ, and then that's your outcome.<div><div></div><div class="h5"><br>
<br></div></div></blockquote><div><br></div><div>I like this idea, but instead of electing 3,3,2 in this example as you suggest, you should elect 2,3,3 (that is, AB, CDF, GKQ, assuming it comes out the same, which it usually would). That concentrates the broadest optimization nearer to the threshold, where it matters more. (In fact, you'd probably get the same results with less computing effort by electing 1,1,1,1,1,3).</div>

<div><br></div><div>JQ</div></div>