[EM] Easy River definition (also my site is back up)

[Kevin Venzke]

Hi Closed Curves, Mike,

I thought about the definition a little. Let's try this, using the "bins" concept
rather than the "subordination" one:

1. Initially each candidate is in their own "bin" named for themselves.
2. Consider each pairwise defeat from strongest to weakest.
3. For a given defeat X>Y, move everyone in bin Y to the bin that X is in.
4. End loop. Go to the next defeat.
5. Elect one of the candidates who remains in their original bin.

Things to note about this:
Once Y has moved anywhere, no one will ever be in bin Y again. So we don't actually
have to throw out other defeats over Y.
If X is in Y's bin when X>Y is considered, rule 3 says that everyone in bin Y
(including X) moves to where X is, which is already Y. So nothing will happen in
this case either.

Should be right.

Closed Limelike Curves <closed.limelike.curves at gmail.com> a écrit :
> River is actually really easy to explain:
> 1. List all pairwise matches from biggest to smallest margin of victory.
> 2. If a candidate loses a match, cross them out (declare them to be a loser).
>Cross out any redundant matches that involve them (anything that would make them
>get eliminated twice).
> 3. Cross out any elections that would create a cycle.

I'd note that River isn't usually defined using margin of victory. (Certainly,
neither Mike nor I would do that.)

But yes, normally River is explained the same way as RP except with an extra rule
to ignore defeats over candidates already defeated. That might be more appealing.

But what I want to point out is that if you are asking "would locking X>Y create a
cycle?" for River, that is worsening the runtime and is harder to solve whether
manually or programmatically.

It is possible, I suppose, that one might use one algorithm to explain a proposal,
or do the needed advocacy, but then use a second, different algorithm to solve it in
practice.

Michael Ossipoff <email9648742 at gmail.com> wrote:
> Wow. River doesn’t need the exhaustive pairwise-count? How does its count-time
> compare to that of RP?
> 
> I didn’t know that about River. I believed that only Sequential-Pairwise was the
> only exception to the need for the exhaustive pairwise-count.
> 
> The exhaustive count requires, per voter, counting one pairwise-vote for each
> possible pair of candidates.
>
> How many votes need to be counted per voter in River?

If I understand you correctly, River does need it. River still needs you to count
all the preferences from each ballot.

River's runtime (as I described River) should be proportional to the number of
pairwise contests, so roughly N^2. For each contest, the action you take consumes a
constant time. That is definitely faster than RP, because RP expends a lot of effort
assessing potential cycles.

> If one only cares about finding the winner, rather than an output-ranking, could
> the count-instruction be written more briefly?

Unfortunately, River as I described it only returns a winner already.

Kevin
votingmethods.net