As far as I understand, Ranked Pairs and MAM need a tiebreaker to
properly pass clone independence. The recommended tiebreaker is random ballot or random voter hierarchy. But is that tiebreaker summable? It seems you'd need to know the full ranking of the voter you choose for the random ballot, and you can't know what voter (or which voters) you're going to choose in advance. Is there a way to make random ballot or RVH summable? Even if you were to choose beforehand a lucky voter from each district and transmit that voter's preference ordering along with the district magnitude, you'd run into problems if a district's voter didn't rank every candidate. The two options to try to solve that would be to do random voter hierarchy with every district's predetermined lucky voter, or to do random voter hierarchy for each district so that the "composite lucky ballot" always fully specifies every candidate. But either choice would seem to alter the distribution. In the former case, you can't complete one district's voter's ballot with a ballot from the same district, and in the latter case, you can't complete one district's voter's ballot with a ballot from another district. Unrestricted random voter hierarchy can do both. Maybe this is not a problem and either of the completion strategies will work for clone independence purposes, but in that case, summable Ranked Pairs or MAM with multiple districts differs from summable Ranked Pairs or MAM in only one district. Or maybe I'm missing some easy way of making random ballot or RVH summable, in which case it'd be interesting to hear how to do so :-) -km ---- Election-Methods mailing list - see https://electorama.com/em for list info |
This issue makes me wonder, between these approaches: 1. Resolve ALL legal ways of forming the hierarchy for RP and declare a tie among all possible victors. 2. Same as #1 but with River. 3. Resolve Schulze, without handling a tie in the outcome. Do we expect differences in decisiveness? My hunch is yes... River admits fewer contests than RP so fewer ties can have an effect. For Schulze I'm not sure. It may be just an imaginary advantage, that the Schulze beatpath algorithm doesn't have to resolve tied contests mid-evaluation. On the other hand, maybe the defeat locking process (with the effect of dropping out some contests) has more potential to disrupt the outcome than exists in Schulze. Kevin
Le vendredi 14 février 2020 à 08:46:44 UTC−6, Kristofer Munsterhjelm <[hidden email]> a écrit :
As far as I understand, Ranked Pairs and MAM need a tiebreaker to properly pass clone independence. The recommended tiebreaker is random ballot or random voter hierarchy. But is that tiebreaker summable? It seems you'd need to know the full ranking of the voter you choose for the random ballot, and you can't know what voter (or which voters) you're going to choose in advance. Is there a way to make random ballot or RVH summable? Even if you were to choose beforehand a lucky voter from each district and transmit that voter's preference ordering along with the district magnitude, you'd run into problems if a district's voter didn't rank every candidate. The two options to try to solve that would be to do random voter hierarchy with every district's predetermined lucky voter, or to do random voter hierarchy for each district so that the "composite lucky ballot" always fully specifies every candidate. But either choice would seem to alter the distribution. In the former case, you can't complete one district's voter's ballot with a ballot from the same district, and in the latter case, you can't complete one district's voter's ballot with a ballot from another district. Unrestricted random voter hierarchy can do both. Maybe this is not a problem and either of the completion strategies will work for clone independence purposes, but in that case, summable Ranked Pairs or MAM with multiple districts differs from summable Ranked Pairs or MAM in only one district. Or maybe I'm missing some easy way of making random ballot or RVH summable, in which case it'd be interesting to hear how to do so :-) -km ---- ---- Election-Methods mailing list - see https://electorama.com/em for list info |
On 14/02/2020 21.26, Kevin Venzke wrote:
> This issue makes me wonder, between these approaches: > 1. Resolve ALL legal ways of forming the hierarchy for RP and declare > a tie among all possible victors. > 2. Same as #1 but with River. > 3. Resolve Schulze, without handling a tie in the outcome. > > Do we expect differences in decisiveness? My hunch is yes... River > admits fewer contests than RP so fewer ties can have an effect. For > Schulze I'm not sure. It may be just an imaginary advantage, that the > Schulze beatpath algorithm doesn't have to resolve tied contests > mid-evaluation. On the other hand, maybe the defeat locking process > (with the effect of dropping out some contests) has more potential to > disrupt the outcome than exists in Schulze. Unfortunately, determining whether some candidate X can be made the winner of Ranked Pairs by breaking ties a particular way is NP-complete: https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/download/5018/5461 Schulze does have a fairly high tie rate because it's based on Minmax, which does tie a lot in small elections. I'm reminded of my Ext-Minmax tiebreaker. The Ext-Minmax winner is the candidate whose minimal victory is the greatest. In the case of ties, look at the next-to-minimal victory, then the third-to-minimal, etc. I've been thinking that there must be some way of applying the same logic to Schulze, but I haven't been able to find a good generalization. It might be easier to do so to the CSSD formulation of Schulze. The CSSD formulation is this: 1. Calculate the Schwartz set based only on undropped defeats. 2. If there are no defeats among the members of that set then they (plural in the case of a tie) win and the count ends. 3. Otherwise, drop the weakest defeat among the candidates of that set. Go to 1. Perhaps you could break ties in #3 in a somehow analogous way to Ext-Minmax, e.g. drop the weakest pairwise contest and if there are more than one with the same strength, drop the X>Y contest where X's next weakest pairwise contest is weakest, and so on up. But that's just a guess. And as for River, I've been thinking about a River-ish method that would simplify the tie problem a lot, and where you could easily declare a tie among winners. It's related to the observation that running River is like calculating a maximum spanning tree. Many of River's properties seem not to depend upon the resulting tree being a maximum spanning tree, but that it's a maximum bottleneck spanning tree. A maximum bottleneck spanning tree is one where the minimum strength is maximized. Every maximum spanning tree is also a maximum bottleneck spanning tree, but vice versa is not true. I *think* that River passing independence of strongly dominated candidates is a consequence of the bottleneck property, but I could be wrong: I only started thinking about this after writing my last post. In any case, the directed graph version of a maximum bottleneck spanning tree is a maximum bottleneck spanning arborescence, and there are algorithms for calculating the MBSA with the provision that the arborescence has to grow from a certain root. The simple interpretation of such a root is that the root node is the candidate who remains undefeated, i.e. the winner. So all you'd have to do to implement this new method (Bottleneck River or what you might call it) is to run Tarjan's algorithm with each candidate as root in turn. For each candidate you get a different tree. The candidate whose tree has the maximal minimal locked edge weight (locked victory) is the winner, and if there's more than one, you can either break ties by considering the next-to-minimal edge weight, or just use a coin toss (or whatever). Tarjan's algorithm is here: https://en.wikipedia.org/wiki/Minimum_bottleneck_spanning_tree#Gabow_and_Tarjan_algorithm_for_MBSA Note that it's specified in terms of a minimum bottleneck spanning arborescence: you can go from maximum to minimum by just turning all the victories negative and adding the total number of voters (and then the winner is the candidate with the minimal maximal edge weight). This pretty much kills all the elegance of the River method, though. ---- Election-Methods mailing list - see https://electorama.com/em for list info |
Hi Kristofer,
Le vendredi 14 février 2020 à 15:38:21 UTC−6, Kristofer Munsterhjelm <[hidden email]> a écrit :
On 14/02/2020 21.26, Kevin Venzke wrote: > This issue makes me wonder, between these approaches: > 1. Resolve ALL legal ways of forming the hierarchy for RP and declare > a tie among all possible victors. > 2. Same as #1 but with River. > 3. Resolve Schulze, without handling a tie in the outcome. > > Do we expect differences in decisiveness? My hunch is yes... River > admits fewer contests than RP so fewer ties can have an effect. For > Schulze I'm not sure. It may be just an imaginary advantage, that the > Schulze beatpath algorithm doesn't have to resolve tied contests > mid-evaluation. On the other hand, maybe the defeat locking process > (with the effect of dropping out some contests) has more potential to > disrupt the outcome than exists in Schulze. Unfortunately, determining whether some candidate X can be made the winner of Ranked Pairs by breaking ties a particular way is NP-complete: https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/download/5018/5461 [Kevin:] Because you might have to check a high percentage of all the rankings? I guess that's bad, and I certainly wouldn't advocate a method that involves forking the process at each tie in any case. But one could still do a decisiveness comparison. Schulze does have a fairly high tie rate because it's based on Minmax, which does tie a lot in small elections. I'm reminded of my Ext-Minmax tiebreaker. The Ext-Minmax winner is the candidate whose minimal victory is the greatest. In the case of ties, look at the next-to-minimal victory, then the third-to-minimal, etc. [Kevin:] Not so clone-proof though, if I understand. I guess I am a little surprised if the ties creating issues under Schulze don't cause similar issues under RP or River. A possible result of a comparison, that occurred to me, would be if Schulze proved to be more decisive. That would mean, in other words, that it's more decisive than methods that actually get interrupted in the middle in order to handle ties. I've been thinking that there must be some way of applying the same logic to Schulze, but I haven't been able to find a good generalization. It might be easier to do so to the CSSD formulation of Schulze. The CSSD formulation is this: 1. Calculate the Schwartz set based only on undropped defeats. 2. If there are no defeats among the members of that set then they (plural in the case of a tie) win and the count ends. 3. Otherwise, drop the weakest defeat among the candidates of that set. Go to 1. Perhaps you could break ties in #3 in a somehow analogous way to Ext-Minmax, e.g. drop the weakest pairwise contest and if there are more than one with the same strength, drop the X>Y contest where X's next weakest pairwise contest is weakest, and so on up. But that's just a guess. [Kevin:] That feels a little painful, that to improve decisiveness in Schulze you would use the formulation that can have ties during the calculation. And as for River, I've been thinking about a River-ish method that would simplify the tie problem a lot, and where you could easily declare a tie among winners. It's related to the observation that running River is like calculating a maximum spanning tree. Many of River's properties seem not to depend upon the resulting tree being a maximum spanning tree, but that it's a maximum bottleneck spanning tree. A maximum bottleneck spanning tree is one where the minimum strength is maximized. Every maximum spanning tree is also a maximum bottleneck spanning tree, but vice versa is not true. I *think* that River passing independence of strongly dominated candidates is a consequence of the bottleneck property, but I could be wrong: I only started thinking about this after writing my last post. In any case, the directed graph version of a maximum bottleneck spanning tree is a maximum bottleneck spanning arborescence, and there are algorithms for calculating the MBSA with the provision that the arborescence has to grow from a certain root. The simple interpretation of such a root is that the root node is the candidate who remains undefeated, i.e. the winner. So all you'd have to do to implement this new method (Bottleneck River or what you might call it) is to run Tarjan's algorithm with each candidate as root in turn. For each candidate you get a different tree. The candidate whose tree has the maximal minimal locked edge weight (locked victory) is the winner, and if there's more than one, you can either break ties by considering the next-to-minimal edge weight, or just use a coin toss (or whatever). Tarjan's algorithm is here: Minimum bottleneck spanning tree Note that it's specified in terms of a minimum bottleneck spanning arborescence: you can go from maximum to minimum by just turning all the victories negative and adding the total number of voters (and then the winner is the candidate with the minimal maximal edge weight). This pretty much kills all the elegance of the River method, though. [Kevin:] Kevin ---- Election-Methods mailing list - see https://electorama.com/em for list info |
Free forum by Nabble | Edit this page |