[EM] Ranked pairs summable?

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

[EM] Ranked pairs summable?

Kristofer Munsterhjelm-3
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
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Ranked pairs summable?

Kevin Venzke
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





----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Ranked pairs summable?

Kristofer Munsterhjelm-3
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
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Ranked pairs summable?

Kevin Venzke
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:]
Yes although I do like the idea of "proposing" each candidate in turn, as the winner, and measuring what gets fouled up by going with that as the outcome.

Kevin


----
Election-Methods mailing list - see https://electorama.com/em for list info