Re: [EM] Nondeterminism in Multiwinner Methods
On Wed, Oct 29, 2008 at 8:42 PM, Kristofer Munsterhjelm <[EMAIL PROTECTED]> wrote: > There's another problem. If you pick n ballots, with some probability more > than one ballot is going to have the same first place candidate. This might > be solvable by picking the first place candidate of the first of the n > ballots, then eliminating it, and so on. Would that be cloneproof? It depends on how you handle the elimination. If each voter submits a ranked ballot and the highest ranked (non-elected) candidate on the ballot is elected, then I think it is clone proof. The order of the ballots being drawn matters, but that is just randomness. A faction cannot increase its probability of winning by fielding many candidates. > I think Woodall wrote that Clone-Winner is incompatible with Droop > proportionality; but what of Clone-Loser? Dunno. However, the above system is not guaranteed to be Droop proportional, it is just proportional on average. > It should pass Clone loser, since > adding a clone never splits the vote, since the worst thing that could > happen is that one of the clones are eliminated, after which another clone > may be in first place on the other ballots. Sounds reasonable. > It might be nonmonotonic. The monotonicity criterion for nondeterministic > methods would be "raising A on a ballot shouldn't decrease A's probability > of winning". The single-winner equivalent would be "IRV with random ballot > elimination". I think it is probably still non-monotonic. If you decrease your favourite's chance of being eliminated, he might end up making it to the final round and then losing. However, if you don't boost your favourite, your 2nd choice might be able to beat your least favourite. I don't think elimination order would help here. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Nondeterminism in Multiwinner Methods
Raph Frank wrote: On Wed, Oct 29, 2008 at 7:12 PM, Kristofer Munsterhjelm <[EMAIL PROTECTED]> wrote: A multiwinner analog of random candidate would be vulnerable to cloning, and I don't think random ballot (pick n ballots) would be proportional either. Actually, pick n ballots would be proportional. If there are N seats and you have 1/N support, then on average you will get one seat. Ofc, there would be variation from the average. An extremist faction could win all N seats, but that is not likely. However, that is also true for single seat random ballot, a candidate with 1% support could win. There's another problem. If you pick n ballots, with some probability more than one ballot is going to have the same first place candidate. This might be solvable by picking the first place candidate of the first of the n ballots, then eliminating it, and so on. Would that be cloneproof? I think Woodall wrote that Clone-Winner is incompatible with Droop proportionality; but what of Clone-Loser? It should pass Clone loser, since adding a clone never splits the vote, since the worst thing that could happen is that one of the clones are eliminated, after which another clone may be in first place on the other ballots. Has anyone considered PR-STV with random ballot elimination? It would work exactly like PR-STV except one ballot would be picked and the lowest ranked candidate on the ballot uneliminated candidate would be eliminated (excluding elected candidates). Also, ballots that are being 'held' by elected candidates would not be included for selection. It might be nonmonotonic. The monotonicity criterion for nondeterministic methods would be "raising A on a ballot shouldn't decrease A's probability of winning". The single-winner equivalent would be "IRV with random ballot elimination". Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Nondeterminism in Multiwinner Methods
On Wed, Oct 29, 2008 at 7:12 PM, Kristofer Munsterhjelm <[EMAIL PROTECTED]> wrote: > A multiwinner analog of random > candidate would be vulnerable to cloning, and I don't think random ballot > (pick n ballots) would be proportional either. Actually, pick n ballots would be proportional. If there are N seats and you have 1/N support, then on average you will get one seat. Ofc, there would be variation from the average. An extremist faction could win all N seats, but that is not likely. However, that is also true for single seat random ballot, a candidate with 1% support could win. Has anyone considered PR-STV with random ballot elimination? It would work exactly like PR-STV except one ballot would be picked and the lowest ranked candidate on the ballot uneliminated candidate would be eliminated (excluding elected candidates). Also, ballots that are being 'held' by elected candidates would not be included for selection. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Nondeterminism in Multiwinner Methods
Greg Nisbet wrote: For the record, I am against nondeterminism in single winner methods, but that is another ball of wax that I want to keep separate. Anyway, the single winner methods can be divided into a few basic types: 1) slow (these take O(candidates!) time. They are non-iterative) 2) fast (these rely on iterations. Usually a kind of elect and punish cycle (think RRV or STV).) 3) party-based 4) nondeterministic (this includes your collusion-based methods (Asset Voting) and random ones (e.g. random ballot)) 5) naive (without making any changes, use a single winner method) 6) plurality-based (CV, Block vote, Preferential Block etc...) (1)s tend to become unwieldy. (2)s suffer bizarre paradoxes (3)s require parties (4)s produce lower quality winners on average (5)s do not produce proportional results... (6)s are kinda unimpressive Just a bit of multiwinner voting theory: I suspect it would be relatively uncontroversial to declare (1) to be best if execution time weren't an issue. However, it is. What do you do about it? There are various shortcuts to help a reasonable solution be found quickly. You could resort to iteration, randomness, parties, or give up. Of course, various elements of these can be combined. It would be possible to have a party-based method with various other methods inside of it. Nondeterministic elements do seem to be useful in the case of multiwinner methods. It is unlikely that a nondeterminstic solution would be perfect, of course. However, I suspect that it can deliver at least some of the benefits of group (1) without incurring factorial execution time. Any thoughts on the matter? Raph gave an explanation with multiple groups doing the optimization. Another option that would probably seem fair would be to find an initial council by using a type-2 method, then hill climb from there. The outcome may still have strange paradoxes (since the type-2 method may be nonmonotonic with the two outcomes being respective local minima), but it would be deterministic and may do better. This would be a scale, where the nondeterministic "pure randomness" shortcut would be on one end, and this on the other. In the middle you would have something like genetic algorithm-based optimization, or simulated annealing. If there's a PTAS for the problem in question, that could also be used. Of course, then one has to ask, a polynomial time approximation scheme of what? What variable does an election method approximate? That would have easier answers for PAV/LPV/etc methods, since those minimize or maximize some satisfaction number. Also, one may ask if a strategyproof nondeterministic method exists for multiwinner elections (like Random Ballot for single-winner). That question may not be of much practical use, though, but could give some ideas of how multiwinner methods "should" be constructed. A multiwinner analog of random candidate would be vulnerable to cloning, and I don't think random ballot (pick n ballots) would be proportional either. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Nondeterminism in Multiwinner Methods
On Sun, Oct 26, 2008 at 4:44 AM, Greg Nisbet <[EMAIL PROTECTED]> wrote: > It is unlikely that a nondeterminstic solution would be perfect, of course. > > However, I suspect that it can deliver at least some of the benefits > of group (1) without incurring factorial execution time. > > Any thoughts on the matter? Another option is to allow the candidates to submit winning sets. Only those winning sets are then considered. The process would be: - voters cast their ballots - ballot info is published* - Each candidate submits a winning set within (say) 1-2 days - all candidate sets are considered and the winning set is declared the winner *This would have to be enough to work out the true winner This is deterministic (though it depends on both the ballots and the outcomes submitted by the candidates), but still allows the more open system to be used. Each candidate would submit the winning set with the highest score (or likely Condorcet winner) that has the candidate as a member. This means that it is very likely that the final outcome is similar to the true winner. It also allows unsecured computing power to be used to find a winner. There could be a "Green [EMAIL PROTECTED]" effort. Checking a result is likely to be much easier than finding the optimal. Mostly, though everyone will just agree on the winning set, it is only in edge cases that there is a dispute. Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Nondeterminism in Multiwinner Methods
For the record, I am against nondeterminism in single winner methods, but that is another ball of wax that I want to keep separate. Anyway, the single winner methods can be divided into a few basic types: 1) slow (these take O(candidates!) time. They are non-iterative) 2) fast (these rely on iterations. Usually a kind of elect and punish cycle (think RRV or STV).) 3) party-based 4) nondeterministic (this includes your collusion-based methods (Asset Voting) and random ones (e.g. random ballot)) 5) naive (without making any changes, use a single winner method) 6) plurality-based (CV, Block vote, Preferential Block etc...) (1)s tend to become unwieldy. (2)s suffer bizarre paradoxes (3)s require parties (4)s produce lower quality winners on average (5)s do not produce proportional results... (6)s are kinda unimpressive Just a bit of multiwinner voting theory: I suspect it would be relatively uncontroversial to declare (1) to be best if execution time weren't an issue. However, it is. What do you do about it? There are various shortcuts to help a reasonable solution be found quickly. You could resort to iteration, randomness, parties, or give up. Of course, various elements of these can be combined. It would be possible to have a party-based method with various other methods inside of it. Nondeterministic elements do seem to be useful in the case of multiwinner methods. It is unlikely that a nondeterminstic solution would be perfect, of course. However, I suspect that it can deliver at least some of the benefits of group (1) without incurring factorial execution time. Any thoughts on the matter? Election-Methods mailing list - see http://electorama.com/em for list info
