[EM] Instant Pairwise Elimination (IPE) vote-counting method

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

[EM] Instant Pairwise Elimination (IPE) vote-counting method

VoteFair-2
Here's a suggestion for an easy-to-understand vote-counting method that
produces very fair results for single-seat elections:

Voters rank the candidates using up to 7 ranking levels (or 5 ranking
levels if ovals are marked on a paper ballot and space is limited).
During counting, each elimination round eliminates the candidate who
loses every pairwise contest against every other remaining candidate.
If an elimination round has no pairwise-losing candidate then, for that
round, each ballot gives one count to the lowest-ranked remaining
candidate on that ballot, and the candidate with the highest such count
is eliminated.  The last remaining candidate wins.

Unless someone recognizes it as having a different name, I suggest
calling it Instant Pairwise Elimination (IPE).  The word "instant"
indicates that this method is similar to instant-runoff voting (IRV) in
the sense of "instantly" doing multiple elimination rounds.  The word
"pairwise" makes it clear that the eliminations use pairwise counting,
rather than the less-fair counting method used in IRV.

This is a hybrid of Condorcet-loser elimination and the Coombs method.
For fun, someone on Reddit (u/jpfed) suggested calling it "Coombsdorcet".

This is not a Condorcet-compliant method!  A test has already found a
case where the IPE winner is not the Condorcet winner.  Also note that
the description does not introduce the word Condorcet, even though it
eliminates Condorcet losers.

I suggested it on Reddit in the r/EndFPTP subreddit because the
single-seat voting methods being discussed there most often are
approval, score, STAR, and IRV, which are easier to understand than
Condorcet methods, but they have one or both of these disadvantages:

* Quite vulnerable to tactical/strategic voting

* Do not work in situations that involve general/runoff elections

The IPE method seems to be easier to explain to typical
(non-math-oriented) voters than any of the Condorcet methods (including
my favorite, the Condorcet-Kemeny method), yet it comes close to
providing the fairness of Condorcet methods.

The inspiration for this method is the relative success of the STAR
method, which is a hybrid of score and runoff.

Based on the surprisingly favorable response on Reddit, apparently most
voters are more trusting of a method that eliminates one candidate at a
time in a way they understand.  This contrasts with Condorcet methods,
which can identify the winner just by "looking at" a table of pairwise
counts.

Also, explicitly identifying "losers," and identifying them one at a
time, seems to be emotionally appealing to voters.  Perhaps this is part
of why IRV is seen as appealing.

Yes, this method is vulnerable to the burial tactic, at least from the
voter's perspective.  Yet when voting methods finally get measured for
HOW OFTEN each method fails each fairness criterion, I suspect that this
burial-criterion failure will not affect the results often enough to be
significant, especially compared to IRV’s frequent fairness-criteria
failures.

In fact, the method may appeal to some voters because it will give them
the emotional satisfaction of burying "enemy" politicians.

Please correct me if I'm wrong, but I believe that -- unlike IRV -- use
of the IPE method would enable polling places to start by sending their
pairwise counts to the central counting location, and the winner can be
identified quickly in most(?) cases.  Of course some elections
(especially if they are highly competitive) will require more ballot
data to be sent to the central counting location before a winner can be
calculated.  In elections that involve lots of candidates, the original
pairwise counts might clarify the elimination sequence for the
less-popular candidates, which would reduce the amount of ballot data
that needs to be sent quickly to determine the winner.  By contrast, IRV
needs almost all the raw ballot data, and the full ranking data with
lots of candidates does not lend itself to being compressed or summarized.

According to u/Chackoony, this method is "sexier" than some other
methods, and he says: "The future is RIPE for IPE!"

Please share your feedback about IPE, either positive or negative (or
both).  Thanks!

Richard Fobes
Author of
Ending The Hidden Unfairness In U.S. Elections
----
Election-Methods mailing list - see http://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Instant Pairwise Elimination (IPE) vote-counting method

Kristofer Munsterhjelm-3
On 13/01/2019 04.44, VoteFair wrote:

> Here's a suggestion for an easy-to-understand vote-counting method that
> produces very fair results for single-seat elections:
>
> Voters rank the candidates using up to 7 ranking levels (or 5 ranking
> levels if ovals are marked on a paper ballot and space is limited).
> During counting, each elimination round eliminates the candidate who
> loses every pairwise contest against every other remaining candidate. If
> an elimination round has no pairwise-losing candidate then, for that
> round, each ballot gives one count to the lowest-ranked remaining
> candidate on that ballot, and the candidate with the highest such count
> is eliminated.  The last remaining candidate wins.

This seems very close to Smith//Coombs, but it's not exactly the same
thing. I think it may fail Smith, even.

Suppose that we have a nested inequality situation with an ABCA cycle
and candidates DEF are all beaten by {ABCA} but have a DEFD cycle among
themselves. Then the Smith set is {ABCA}, and the Antiplurality
elimination stage triggers because nobody is beaten by everybody else.
The Antiplurality elimination stage might then eliminate one of ABCA,
and in the worst case, might sequentially eliminate all of them, making
the method fail Smith.

It's probably not monotone either, as very few candidate elimination
methods are, and probably fails independence of clones since both
Antiplurality and Coombs do.

> Unless someone recognizes it as having a different name, I suggest
> calling it Instant Pairwise Elimination (IPE).  The word "instant"
> indicates that this method is similar to instant-runoff voting (IRV) in
> the sense of "instantly" doing multiple elimination rounds.  The word
> "pairwise" makes it clear that the eliminations use pairwise counting,
> rather than the less-fair counting method used in IRV.
>
> This is a hybrid of Condorcet-loser elimination and the Coombs method.
> For fun, someone on Reddit (u/jpfed) suggested calling it "Coombsdorcet".
>
> This is not a Condorcet-compliant method!  A test has already found a
> case where the IPE winner is not the Condorcet winner.  Also note that
> the description does not introduce the word Condorcet, even though it
> eliminates Condorcet losers.

Oh, oops. You already figured out what I wrote above :-)

Both Nanson and Baldwin (Borda-elimination methods) are Condorcet
without having an explicit Condorcet step or using a Condorcet matrix.
So are methods of this type:

Arrange the candidates in a line according to some initial ordering.
Start with the last candidate in line, and compare him to the
second-to-last. Eliminate the one of the pair who is beaten one-on-one
by the other. If they tie each other, use whatever tiebreaker you want.
Keep on going up the line until only one candidate is left; he wins.

(Those methods are Smith. They're also summable as long as the methods
used for tiebreaks and initial ordering are.)

> I suggested it on Reddit in the r/EndFPTP subreddit because the
> single-seat voting methods being discussed there most often are
> approval, score, STAR, and IRV, which are easier to understand than
> Condorcet methods, but they have one or both of these disadvantages:
>
> * Quite vulnerable to tactical/strategic voting
>
> * Do not work in situations that involve general/runoff elections
>
> The IPE method seems to be easier to explain to typical
> (non-math-oriented) voters than any of the Condorcet methods (including
> my favorite, the Condorcet-Kemeny method), yet it comes close to
> providing the fairness of Condorcet methods.
>
> The inspiration for this method is the relative success of the STAR
> method, which is a hybrid of score and runoff.
>
> Based on the surprisingly favorable response on Reddit, apparently most
> voters are more trusting of a method that eliminates one candidate at a
> time in a way they understand.  This contrasts with Condorcet methods,
> which can identify the winner just by "looking at" a table of pairwise
> counts.
>
> Also, explicitly identifying "losers," and identifying them one at a
> time, seems to be emotionally appealing to voters.  Perhaps this is part
> of why IRV is seen as appealing.

Do you think the line method above would be received favorably? It is
very simple but has a less explicit loser elimination component.

> Yes, this method is vulnerable to the burial tactic, at least from the
> voter's perspective.  Yet when voting methods finally get measured for
> HOW OFTEN each method fails each fairness criterion, I suspect that this
> burial-criterion failure will not affect the results often enough to be
> significant, especially compared to IRV’s frequent fairness-criteria
> failures.
>
> In fact, the method may appeal to some voters because it will give them
> the emotional satisfaction of burying "enemy" politicians.

Every voting method permits an angry voter to decide "I'm going to
punish X" and change his vote from A>X>B>C to A>B>C>X. Pervasive burial
susceptibility is more problematic when it creates a feeling that "I
need to put the frontrunner I like the least at the very bottom or he'll
win"; and then everybody does that, and a nobody wins.

I generally think Condorcet methods are (on the whole) robust enough to
disincentivize such massive burial sprees, but I haven't done any
analysis on IPE in particular.

> Please correct me if I'm wrong, but I believe that -- unlike IRV -- use
> of the IPE method would enable polling places to start by sending their
> pairwise counts to the central counting location, and the winner can be
> identified quickly in most(?) cases.  Of course some elections
> (especially if they are highly competitive) will require more ballot
> data to be sent to the central counting location before a winner can be
> calculated.  In elections that involve lots of candidates, the original
> pairwise counts might clarify the elimination sequence for the
> less-popular candidates, which would reduce the amount of ballot data
> that needs to be sent quickly to determine the winner.  By contrast, IRV
> needs almost all the raw ballot data, and the full ranking data with
> lots of candidates does not lend itself to being compressed or summarized.

If there's a clear Condorcet order, then you're right. But as soon as
the Antiplurality elimination step comes into play, the districts will
have to send their ballot data over to the center (or do two-way
communication like in IRV). The reason is that who is next to be
eliminated depends on which candidates have been eliminated so far in a
way that can't be handled by a summed array -- just like IRV.
----
Election-Methods mailing list - see http://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Instant Pairwise Elimination (IPE) vote-counting method

VoteFair-2
Based on Kristofer's feedback (below), here are the criteria that I
suspect the Instant Pairwise Elimination (IPE) method fails:

Majority: fail
Majority loser: fail
Mutual majority: fail
Condorcet: fail
Smith/ISDA: fail
LIIA: fail
IIA: fail
Cloneproof: fail
Monotone: fail
Consistency: fail
Reversal symmetry: fail
Later no harm: fail
Later no help: fail
Burying: fail

I'm guessing that IPE fails these criteria:

Participation: fail ?
No favorite betrayal: fail ?

Of course IPE passes these criteria:

Ranks equal: pass
Ranks greater than 2: pass
Polytime/resolvable: pass/pass

I'm guessing that IPE passes this criterion:

Condorcet loser: pass ?

And here's my guess about summability:

Summable: O(N!) ?

On the surface, these characteristics do not look promising ...

... yet I'll say once again that what really matters is HOW OFTEN a
method complies with the criteria. When we have that data we can more
meaningfully compare different voting methods -- beyond just looking at
checklists.

In fact, this topic, which I would call "Compliance Frequency," is being
discussed on Reddit, with my suggestions at the following link:

https://www.reddit.com/r/EndFPTP/comments/afc9mm/quantifying_criteria_failure_rates/edy8gyh

I had intended to post these compliance-frequency suggestions here on
this mailing list, but I seldom have time to write
election-method-reform messages while at my PC, whereas I can type
Reddit responses on my iPad while eating a meal.

Again, thank you Kristofer for your very useful feedback! (And no I had
not already figured out the details that you clarified.)

Again, thanks to all for considering this suggested method. I'm assuming
from the lack of criticism that the method is not as seriously flawed as
IRV, which means it deserves attention as an alternative when a city
considers adopting something better than plurality voting.

My next question is whether anyone wants to put the IPE method on the
Electrowiki (or Electorama) site? (I tried using my login info from long
ago, but with no success.) I can supply edited text if that's helpful.
In advance, thanks!

Richard Fobes


On 1/13/2019 3:10 AM, Kristofer Munsterhjelm wrote:

> On 13/01/2019 04.44, VoteFair wrote:
>> Here's a suggestion for an easy-to-understand vote-counting method that
>> produces very fair results for single-seat elections:
>>
>> Voters rank the candidates using up to 7 ranking levels (or 5 ranking
>> levels if ovals are marked on a paper ballot and space is limited).
>> During counting, each elimination round eliminates the candidate who
>> loses every pairwise contest against every other remaining candidate. If
>> an elimination round has no pairwise-losing candidate then, for that
>> round, each ballot gives one count to the lowest-ranked remaining
>> candidate on that ballot, and the candidate with the highest such count
>> is eliminated.  The last remaining candidate wins.
>
> This seems very close to Smith//Coombs, but it's not exactly the same
> thing. I think it may fail Smith, even.
>
> Suppose that we have a nested inequality situation with an ABCA cycle
> and candidates DEF are all beaten by {ABCA} but have a DEFD cycle among
> themselves. Then the Smith set is {ABCA}, and the Antiplurality
> elimination stage triggers because nobody is beaten by everybody else.
> The Antiplurality elimination stage might then eliminate one of ABCA,
> and in the worst case, might sequentially eliminate all of them, making
> the method fail Smith.
>
> It's probably not monotone either, as very few candidate elimination
> methods are, and probably fails independence of clones since both
> Antiplurality and Coombs do.
>
>> Unless someone recognizes it as having a different name, I suggest
>> calling it Instant Pairwise Elimination (IPE).  The word "instant"
>> indicates that this method is similar to instant-runoff voting (IRV) in
>> the sense of "instantly" doing multiple elimination rounds.  The word
>> "pairwise" makes it clear that the eliminations use pairwise counting,
>> rather than the less-fair counting method used in IRV.
>>
>> This is a hybrid of Condorcet-loser elimination and the Coombs method.
>> For fun, someone on Reddit (u/jpfed) suggested calling it "Coombsdorcet".
>>
>> This is not a Condorcet-compliant method!  A test has already found a
>> case where the IPE winner is not the Condorcet winner.  Also note that
>> the description does not introduce the word Condorcet, even though it
>> eliminates Condorcet losers.
>
> Oh, oops. You already figured out what I wrote above :-)
>
> Both Nanson and Baldwin (Borda-elimination methods) are Condorcet
> without having an explicit Condorcet step or using a Condorcet matrix.
> So are methods of this type:
>
> Arrange the candidates in a line according to some initial ordering.
> Start with the last candidate in line, and compare him to the
> second-to-last. Eliminate the one of the pair who is beaten one-on-one
> by the other. If they tie each other, use whatever tiebreaker you want.
> Keep on going up the line until only one candidate is left; he wins.
>
> (Those methods are Smith. They're also summable as long as the methods
> used for tiebreaks and initial ordering are.)
>
>> I suggested it on Reddit in the r/EndFPTP subreddit because the
>> single-seat voting methods being discussed there most often are
>> approval, score, STAR, and IRV, which are easier to understand than
>> Condorcet methods, but they have one or both of these disadvantages:
>>
>> * Quite vulnerable to tactical/strategic voting
>>
>> * Do not work in situations that involve general/runoff elections
>>
>> The IPE method seems to be easier to explain to typical
>> (non-math-oriented) voters than any of the Condorcet methods (including
>> my favorite, the Condorcet-Kemeny method), yet it comes close to
>> providing the fairness of Condorcet methods.
>>
>> The inspiration for this method is the relative success of the STAR
>> method, which is a hybrid of score and runoff.
>>
>> Based on the surprisingly favorable response on Reddit, apparently most
>> voters are more trusting of a method that eliminates one candidate at a
>> time in a way they understand.  This contrasts with Condorcet methods,
>> which can identify the winner just by "looking at" a table of pairwise
>> counts.
>>
>> Also, explicitly identifying "losers," and identifying them one at a
>> time, seems to be emotionally appealing to voters.  Perhaps this is part
>> of why IRV is seen as appealing.
>
> Do you think the line method above would be received favorably? It is
> very simple but has a less explicit loser elimination component.
>
>> Yes, this method is vulnerable to the burial tactic, at least from the
>> voter's perspective.  Yet when voting methods finally get measured for
>> HOW OFTEN each method fails each fairness criterion, I suspect that this
>> burial-criterion failure will not affect the results often enough to be
>> significant, especially compared to IRV’s frequent fairness-criteria
>> failures.
>>
>> In fact, the method may appeal to some voters because it will give them
>> the emotional satisfaction of burying "enemy" politicians.
>
> Every voting method permits an angry voter to decide "I'm going to
> punish X" and change his vote from A>X>B>C to A>B>C>X. Pervasive burial
> susceptibility is more problematic when it creates a feeling that "I
> need to put the frontrunner I like the least at the very bottom or he'll
> win"; and then everybody does that, and a nobody wins.
>
> I generally think Condorcet methods are (on the whole) robust enough to
> disincentivize such massive burial sprees, but I haven't done any
> analysis on IPE in particular.
>
>> Please correct me if I'm wrong, but I believe that -- unlike IRV -- use
>> of the IPE method would enable polling places to start by sending their
>> pairwise counts to the central counting location, and the winner can be
>> identified quickly in most(?) cases.  Of course some elections
>> (especially if they are highly competitive) will require more ballot
>> data to be sent to the central counting location before a winner can be
>> calculated.  In elections that involve lots of candidates, the original
>> pairwise counts might clarify the elimination sequence for the
>> less-popular candidates, which would reduce the amount of ballot data
>> that needs to be sent quickly to determine the winner.  By contrast, IRV
>> needs almost all the raw ballot data, and the full ranking data with
>> lots of candidates does not lend itself to being compressed or summarized.
>
> If there's a clear Condorcet order, then you're right. But as soon as
> the Antiplurality elimination step comes into play, the districts will
> have to send their ballot data over to the center (or do two-way
> communication like in IRV). The reason is that who is next to be
> eliminated depends on which candidates have been eliminated so far in a
> way that can't be handled by a summed array -- just like IRV.
>
----
Election-Methods mailing list - see http://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Instant Pairwise Elimination (IPE) vote-counting method

Kristofer Munsterhjelm-3
On 14/01/2019 01.55, VoteFair wrote:
> Based on Kristofer's feedback (below), here are the criteria that I
> suspect the Instant Pairwise Elimination (IPE) method fails:
>
> Majority: fail
> Majority loser: fail

If there's a majority loser X, for every other candidate Y, a majority
of the voters prefer Y to X. So X is thus a Condorcet loser; see below
for that criterion.

Majority failure: Consider

10: A > D > B > C
10: A > C > D > B
11: A > B > C > D
10: B > C > D > A
10: C > D > B > A
10: D > B > C > A

There's a Condorcet cycle between {B, C, D}, and A is the Antiplurality
loser. So IPE will eliminate A first, but A is ranked first by 50.8% of
the voters. Hence IPE definitely fails majority.

> Mutual majority: fail

If a method fails majority, it also fails mutual majority.

A nice thing about methods that eliminate one candidate at a time until
some winner remains, is that if they pass a criterion for a single
candidate, they also pass it for a set. That means that such an
elimination method passes mutual majority iff it passes majority, and
passes Smith iff it passes Condorcet.

> Condorcet: fail

If a method fails majority, it also fails Condorcet.

> Smith/ISDA: fail

... and if a method fails Condorcet, it also fails Smith/ISDA.

> IIA: fail

Every deterministic ranked method fails IIA.

> Consistency: fail

Only positional voting systems (x points for first, y points for second,
etc) pass consistency. IPE is not such a system, so it automatically fails.

What I mean by consistency is here the same-winning-candidate version,
not the same-social-ordering version that Kemeny passes. If you mean
that one, I'd agree with you: it probably fails it, but I can't think of
a proof.

(The same-social-ordering one is sometimes called reinforcement to
distinguish it from consistency; yet in other articles, consistency and
reinforcement are taken to mean the same thing, and which one it is
depends on whether the voting method is defined to output a ranking or a
winner.)

> I'm guessing that IPE passes this criterion:
>
> Condorcet loser: pass ?

Suppose there's a Condorcet loser. By definition, he loses every
pairwise contest to every other candidate. Thus he'll be eliminated
right away by IPE, and hence IPE passes Condorcet loser.

> And here's my guess about summability:
>
> Summable: O(N!) ?
>
> On the surface, these characteristics do not look promising ...

A possible patch: instead of eliminating by Antiplurality, eliminate by
how many candidates beat the candidate in question. That is, eliminate
the candidate who is beaten by more of the others than any other. This
naturally eliminates the Condorcet loser (as in your current version)
without any special case logic. Then break further ties by (e.g.)
Antiplurality.

That should salvage Condorcet (and thus Smith) and Majority (and thus
Mutual Majority). It would probably still fail monotonicity and clone
independence, and it'll stay unsummable for most tiebreaks.

> ... yet I'll say once again that what really matters is HOW OFTEN a
> method complies with the criteria. When we have that data we can more
> meaningfully compare different voting methods -- beyond just looking at
> checklists.
>
> In fact, this topic, which I would call "Compliance Frequency," is being
> discussed on Reddit, with my suggestions at the following link:
>
> https://www.reddit.com/r/EndFPTP/comments/afc9mm/quantifying_criteria_failure_rates/edy8gyh

As I've said before, one problem with compliance frequency is that you
don't know the distribution to sample from. The distribution probably
depends on the method in use. E.g. Plurality encourages two-party rule,
so under Plurality, the voters will tend to vote consistent with
two-party rule.

In a way, this is where IRV got it wrong. One way of looking at IRV's
logic is like this: "under Plurality, sometimes fringe candidates make
the wrong major candidate win. So let's patch up that problem by
eliminating fringe candidates before deciding on the winner". That is
all well and fine ... *as long* as voters keep voting for two major
parties. Under the voting distribution induced by Plurality, IRV is very
good!

But if the voters, emboldened by that their votes now matter, change how
they vote in such a way that multiple strong candidates emerge, then IRV
can get confused and you get a Burlington.

You could measure compliance frequency by assuming that every candidate
permutation is equally likely - the so-called impartial culture. But the
same people who would say "but my method X only violates
monotonicity/ISDA/whatever once in a million elections, so that
violation shouldn't count" can then say "but the voters don't vote
according to impartial culture, and in the real world,
monotonicity/ISDA/whatever will only be violated once in a million
elections".

I suppose the only real way to circumvent the problem is to determine
the frequency according to many different distributions. If the method
consistently does badly, then it is bad. If the method consistently does
well, then it is good. If it's a mixed bag, then the advocates can argue
all night about which distributions matter and which don't.

(Another problem is the social rank vs winner distinction. That
distinction very rarely matters when you're only looking for a single
failure, but the frequency of social rank failure may differ from the
frequency of winner-becomes-loser.)

> I had intended to post these compliance-frequency suggestions here on
> this mailing list, but I seldom have time to write
> election-method-reform messages while at my PC, whereas I can type
> Reddit responses on my iPad while eating a meal.
>
> Again, thank you Kristofer for your very useful feedback! (And no I had
> not already figured out the details that you clarified.)
>
> Again, thanks to all for considering this suggested method. I'm assuming
> from the lack of criticism that the method is not as seriously flawed as
> IRV, which means it deserves attention as an alternative when a city
> considers adopting something better than plurality voting.

Well, for all its faults, IRV passes majority and is (strictly speaking)
independent of clones, whereas IPE is neither. The lack of harsh words
might be more attributable to that IPE doesn't have "the momentum"
(visible targets get more criticism), and there's no Rob Richie to
attract posters' ire, for IPE.

> My next question is whether anyone wants to put the IPE method on the
> Electrowiki (or Electorama) site? (I tried using my login info from long
> ago, but with no success.) I can supply edited text if that's helpful.
> In advance, thanks!

The Electorama wiki is moving to https://electowiki.org/. You should be
able to register a user there.
----
Election-Methods mailing list - see http://electorama.com/em for list info