[email protected] 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.
----
Election-Methods mailing list - see http://electorama.com/em for list info
