[EM] Participation criterion and Condorcet rules

Post by John
The fact that Condorcet methods fail participation is fairly
immaterial. I want to know WHEN they fail participation. I suspect, to
be short, that a Condorcet method exists (e.g. any ISDA method) which
can only fail participation when the winner is not the first Smith-set
candidate ranked on the ballot. Likewise, I suspect that the
probability of such failure is vanishingly-small for some methods, and
relies on particular and uncommon conditions in the graph.

You have the right idea. The important point is the issue of HOW OFTEN
a method fails one criterion or another.

My prediction is that when this issue finally gets analyzed, the
Condorcet-Kemeny method will have the fewest failures.

As for simplicity (which you mention in your full message), the
Condorcet-Kemeny method is easier to understand than the
Condorcet-Schulze method. For clarification, both methods usually
identify the same winner in most real-life situations.

Currently I'm refining the design of the "VoteFair marble machine" that
demonstrates Condorcet-Kemeny calculations using a marble machine --
which actually uses steel balls instead of marbles because they are
smaller and don't shatter. A video of that machine in use will further
demonstrate the method's simplicity. Here is the link to the current
description/design:

http://www.votefair.org/votefair_marble_machine.html

I'll update that description when I've created the 3D-object file for
the 3D "module" where a large "marble" hits a small "marble" from one
side or the other.

John, thank you for taking time to understand alternate election-method
reform methods.

In case you missed it, here is my latest article at Democracy Chronicles
that puts election-method reform into perspective -- in a way that
"average" (non-mathematical) folks can understand:

https://democracychronicles.org/postwar-monopoly/

Richard Fobes
Author of "Ending The Hidden Unfairness In U.S. Elections"

Post by John
Current theory suggests Condorcet methods are incompatible with the
Participation criterion: a set of ballots can exist such that a
Condorcet method elects candidate X, and a single additional ballot
ranking X ahead of Y will change the winner from X to Y.
https://en.wikipedia.org/wiki/Participation_criterion
This criterion seems ill-fitted, and I feel needs clarification.
First, so-called Condorcet methods are simply Smith-efficient (some are
Schwartz-efficient, which is a subset): they elect a candidate from the
Smith set. If the Smith set is one candidate, that is the Condorcet
candidate, and all methods elect that candidate.
From that standpoint, each Condorcet method represents an arbitrary
selection of a candidate from a pool of identified suitable candidates.
Ranked Pairs elects the candidate with the strongest rankings; Schulze
elects a more-suitable candidate with less voter regret (eliminates
candidates with relatively large pairwise losses); Tideman's Alternative
methods resist tactical voting and elect some candidate or another.
Given that Tideman's Alternative methods resist tactical voting, one
might suggest a bona fide Condorcet candidate is automatically resistant
to tactical voting and thus unlikely to be impacted by the no-show paradox.
I ask if the following hold true in Condorcet methods where tied
1. In methods independent of Smith-dominated alternatives (ISDA),
ranking X above Y will not change the winner from X to Y /unless/ Y
is already in the Smith Set prior to casting the ballot.
2. In ISDA methods, ranking X above Y will not change the winner from X
to Y /unless/ some candidate Z both precedes X and is in the Smith
set prior to casting the ballot.
3. In ISDA methods, ranking X above Y will not change the winner from X
/unless/ some candidate Z both precedes X and is in the Smith set
/after/ casting the ballot.
4. In ISDA methods, ranking X above Y and ranking Z above X will either
not change the winner from X /or/ will change the winner from X to Z
if Z is not in the Smith Set prior to casting the ballot and is in
the Smith Set after casting the ballot.
5. in ISDA methods, ranking X above Y will not change the winner from X
to Y /unless/ Y precedes Z in a cycle after casting the
ballot /and/ Z precedes X on the ballot.
I have not validated these mathematically.
#1 stands out to me because ranking ZXY can cause Y to beat W. If W is
in the Smith Set, this will bring Y into the Smith Set; it will also
strengthen both Z and X over W. Z and X beat Y, as well.
This is trivially valid for Ranked Pairs; I am uncertain of Schulze or
Tideman's Alternative. Schulze should elect Z or X.
In Tideman's Alternative, X can't win without being first-ranked more
frequently than Z and W; bringing Y into the Smith Set removes all of
X's first-ranked votes where Y was ranked above X (X* becomes YX*). Y
cannot suddenly dominate all candidates in this way, and should quickly
lose ground: X might go first, but that just turns XZ* and XW* votes
into Z and W votes, and Z and W previously dominated Y and so Y will be
the /second/ eliminated if not the /first/.
/
/
#2 is similar. If you rank X first, Ranked Pairs will tend to get to X
sooner, possibly moving it ahead of a prior pairwise lock-in of Y, but
not behind. The losses for X get weaker and the wins get stronger. X
also necessarily cannot be the plurality loser in Tideman's Alternative,
and will not change its position relative to Y. X must be preceded by a
candidate already in the Smith Set prior to casting the ballot for the
winner to change from X to Y.
#3 suggests similar: if a candidate Z precedes X and is not in the
Smith set after casting the ballot, X is the first candidate, and #2
holds (this is ISDA).
#4 might be wrong: pulling Z into the Smith set by ZXY might not be
able to change the winner from X.
#5 suggests you can't switch from X to Y unless the ballot ranks Z over
X /and/ Y has a beatpath that reaches X through Z.
I haven't tested or evaluated any of these; I suspect some of these are
true, some are false, and some are weaker statements than what does hold
true.
The fact that Condorcet methods fail participation is fairly
immaterial. I want to know WHEN they fail participation. I suspect, to
be short, that a Condorcet method exists (e.g. any ISDA method) which
can only fail participation when the winner is not the first Smith-set
candidate ranked on the ballot. Likewise, I suspect that the
probability of such failure is vanishingly-small for some methods, and
relies on particular and uncommon conditions in the graph.
----
Election-Methods mailing list - see http://electorama.com/em for list info

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

John

2018-08-08 18:43:35 UTC

That method is NP-hard and involves complex tabulation. If you can
demonstrate it more-simply, that helps.

Alternative Scwartz is O(n^2) polynomial and simple. It selects from the
same set as Schulze, whereas Alternative Smith uses the whole Smith Set.
Both resist tactical manipulation; Kenemy seems to fail clone independence.

Thoughts?

You have the right idea. The important point is the issue of HOW OFTEN
a method fails one criterion or another.
My prediction is that when this issue finally gets analyzed, the
Condorcet-Kemeny method will have the fewest failures.
As for simplicity (which you mention in your full message), the
Condorcet-Kemeny method is easier to understand than the
Condorcet-Schulze method. For clarification, both methods usually
identify the same winner in most real-life situations.
Currently I'm refining the design of the "VoteFair marble machine" that
demonstrates Condorcet-Kemeny calculations using a marble machine --
which actually uses steel balls instead of marbles because they are
smaller and don't shatter. A video of that machine in use will further
demonstrate the method's simplicity. Here is the link to the current
http://www.votefair.org/votefair_marble_machine.html
I'll update that description when I've created the 3D-object file for
the 3D "module" where a large "marble" hits a small "marble" from one
side or the other.
John, thank you for taking time to understand alternate election-method
reform methods.
In case you missed it, here is my latest article at Democracy Chronicles
that puts election-method reform into perspective -- in a way that
https://democracychronicles.org/postwar-monopoly/
Richard Fobes
Author of "Ending The Hidden Unfairness In U.S. Elections"

paradox.

Post by John
I ask if the following hold true in Condorcet methods where tied
1. In methods independent of Smith-dominated alternatives (ISDA),
ranking X above Y will not change the winner from X to Y /unless/ Y
is already in the Smith Set prior to casting the ballot.
2. In ISDA methods, ranking X above Y will not change the winner from X
to Y /unless/ some candidate Z both precedes X and is in the Smith
set prior to casting the ballot.
3. In ISDA methods, ranking X above Y will not change the winner from X
/unless/ some candidate Z both precedes X and is in the Smith set
/after/ casting the ballot.
4. In ISDA methods, ranking X above Y and ranking Z above X will either
not change the winner from X /or/ will change the winner from X to Z
if Z is not in the Smith Set prior to casting the ballot and is in
the Smith Set after casting the ballot.
5. in ISDA methods, ranking X above Y will not change the winner from X
to Y /unless/ Y precedes Z in a cycle after casting the
ballot /and/ Z precedes X on the ballot.
I have not validated these mathematically.
#1 stands out to me because ranking ZXY can cause Y to beat W. If W is
in the Smith Set, this will bring Y into the Smith Set; it will also
strengthen both Z and X over W. Z and X beat Y, as well.
This is trivially valid for Ranked Pairs; I am uncertain of Schulze or
Tideman's Alternative. Schulze should elect Z or X.
In Tideman's Alternative, X can't win without being first-ranked more
frequently than Z and W; bringing Y into the Smith Set removes all of
X's first-ranked votes where Y was ranked above X (X* becomes YX*). Y
cannot suddenly dominate all candidates in this way, and should quickly
lose ground: X might go first, but that just turns XZ* and XW* votes
into Z and W votes, and Z and W previously dominated Y and so Y will be
the /second/ eliminated if not the /first/.
/
/
#2 is similar. If you rank X first, Ranked Pairs will tend to get to X
sooner, possibly moving it ahead of a prior pairwise lock-in of Y, but
not behind. The losses for X get weaker and the wins get stronger. X
also necessarily cannot be the plurality loser in Tideman's Alternative,
and will not change its position relative to Y. X must be preceded by a
candidate already in the Smith Set prior to casting the ballot for the
winner to change from X to Y.
#3 suggests similar: if a candidate Z precedes X and is not in the
Smith set after casting the ballot, X is the first candidate, and #2
holds (this is ISDA).
#4 might be wrong: pulling Z into the Smith set by ZXY might not be
able to change the winner from X.
#5 suggests you can't switch from X to Y unless the ballot ranks Z over
X /and/ Y has a beatpath that reaches X through Z.
I haven't tested or evaluated any of these; I suspect some of these are
true, some are false, and some are weaker statements than what does hold
true.
The fact that Condorcet methods fail participation is fairly
immaterial. I want to know WHEN they fail participation. I suspect, to
be short, that a Condorcet method exists (e.g. any ISDA method) which
can only fail participation when the winner is not the first Smith-set
candidate ranked on the ballot. Likewise, I suspect that the
probability of such failure is vanishingly-small for some methods, and
relies on particular and uncommon conditions in the graph.
----
Election-Methods mailing list - see http://electorama.com/em for list

info

VoteFair

2018-08-10 05:20:21 UTC

Post by John
That method is NP-hard and involves complex tabulation.

Keep in mind that NP-hardness of the Condorcet-Kemeny method applies to
ranking ALL the choices, from most popular, second-most popular, and so
on down to least popular.

In an election, only the winner needs to be identified.

So, if there are, say, 150 candidates, most of those candidates can
easily be identified as not winning, and I'd guess there would be, at
most, 15 candidates who might be able to win, and, in a worst-case
scenario, the full ranking of those 15 candidates can be calculated --
with the raw Condorcet-Kemeny method -- within a few hours at most. If
there are "just" 12 might-win candidates, the calculations take just a
few seconds at most.

Another way to say this is that if there is circular ambiguity that
amounts to a near-tie among 20 or more candidates, then, yes, the
calculations, in theory, would take a very long time. How often would
that occur? So rarely that it's not an issue in real-life elections.
It's more of an academic issue.

Of course people who prefer a different Condorcet method (or sometimes
IRV advocates) like to use NP-hardness as a reason to dismiss the
Condorcet-Kemeny method.

As I said earlier, I predict that the Condorcet-Kemeny method will have
lower failure rates for most of the desired vote-counting criteria. If
that's true, then a few extra seconds of computation time will not be a
significant disadvantage.

BTW, the reason for this prediction is that when a method is designed to
fully avoid specific fairness failure criteria, the likely consequence
is an increase in the failure rates for other fairness criteria.

As for "complex tabulation," the results are calculated from the
pairwise counts, the same as for any Condorcet method. If you are
referring to the task of writing the code to do the calculations, I've
already done that, and posted the code here:

https://github.com/cpsolver/VoteFair-ranking

The code also handles ties, meaning that if there are any ties at any
ranking levels, the full-ranking results include which choices are tied
at which levels. In other words, unlike some vote-counting code, this
code does not give up when it reaches a tie; instead it fully calculates
the full ranking, ties included.

One more point. When election-method reform gets to the point of
needing to go beyond single-seat elections to get proportional results,
the VoteFair ranking software also does those calculations.

Richard Fobes

Post by John
That method is NP-hard and involves complex tabulation. If you can
demonstrate it more-simply, that helps.
Alternative Scwartz is O(n^2) polynomial and simple. It selects from
the same set as Schulze, whereas Alternative Smith uses the whole Smith
Set. Both resist tactical manipulation; Kenemy seems to fail clone
independence.
Thoughts?

Post by John
The fact that Condorcet methods fail participation is fairly
immaterial. I want to know WHEN they fail participation. I

suspect, to

Post by John
be short, that a Condorcet method exists (e.g. any ISDA method) which
can only fail participation when the winner is not the first

Smith-set

Post by John
candidate ranked on the ballot. Likewise, I suspect that the
probability of such failure is vanishingly-small for some

methods, and

Post by John
relies on particular and uncommon conditions in the graph.

You have the right idea. The important point is the issue of HOW OFTEN
a method fails one criterion or another.
My prediction is that when this issue finally gets analyzed, the
Condorcet-Kemeny method will have the fewest failures.
As for simplicity (which you mention in your full message), the
Condorcet-Kemeny method is easier to understand than the
Condorcet-Schulze method. For clarification, both methods usually
identify the same winner in most real-life situations.
Currently I'm refining the design of the "VoteFair marble machine" that
demonstrates Condorcet-Kemeny calculations using a marble machine --
which actually uses steel balls instead of marbles because they are
smaller and don't shatter. A video of that machine in use will further
demonstrate the method's simplicity. Here is the link to the current
http://www.votefair.org/votefair_marble_machine.html
I'll update that description when I've created the 3D-object file for
the 3D "module" where a large "marble" hits a small "marble" from one
side or the other.
John, thank you for taking time to understand alternate election-method
reform methods.
In case you missed it, here is my latest article at Democracy Chronicles
that puts election-method reform into perspective -- in a way that
https://democracychronicles.org/postwar-monopoly/
Richard Fobes
Author of "Ending The Hidden Unfairness In U.S. Elections"

(some are

Post by John
Schwartz-efficient, which is a subset): they elect a candidate

from the

Post by John
Smith set. If the Smith set is one candidate, that is the Condorcet
candidate, and all methods elect that candidate.
From that standpoint, each Condorcet method represents an arbitrary
selection of a candidate from a pool of identified suitable

candidates.

Post by John
Ranked Pairs elects the candidate with the strongest rankings; Schulze
elects a more-suitable candidate with less voter regret (eliminates
candidates with relatively large pairwise losses); Tideman's

Alternative

Post by John
methods resist tactical voting and elect some candidate or another.
Given that Tideman's Alternative methods resist tactical voting, one
might suggest a bona fide Condorcet candidate is automatically

resistant

Post by John
to tactical voting and thus unlikely to be impacted by the no-show

paradox.

/unless/ Y

Post by John
is already in the Smith Set prior to casting the ballot.
2. In ISDA methods, ranking X above Y will not change the winner

from X

Post by John
to Y /unless/ some candidate Z both precedes X and is in the Smith
set prior to casting the ballot.
3. In ISDA methods, ranking X above Y will not change the winner

from X

Post by John
/unless/ some candidate Z both precedes X and is in the Smith set
/after/ casting the ballot.
4. In ISDA methods, ranking X above Y and ranking Z above X will

either

Post by John
not change the winner from X /or/ will change the winner from

X to Z

Post by John
if Z is not in the Smith Set prior to casting the ballot and is in
the Smith Set after casting the ballot.
5. in ISDA methods, ranking X above Y will not change the winner

from X

Post by John
to Y /unless/ Y precedes Z in a cycle after casting the
ballot /and/ Z precedes X on the ballot.
I have not validated these mathematically.
#1 stands out to me because ranking ZXY can cause Y to beat W. If

W is

Post by John
in the Smith Set, this will bring Y into the Smith Set; it will also
strengthen both Z and X over W. Z and X beat Y, as well.
This is trivially valid for Ranked Pairs; I am uncertain of Schulze or
Tideman's Alternative. Schulze should elect Z or X.
In Tideman's Alternative, X can't win without being first-ranked more
frequently than Z and W; bringing Y into the Smith Set removes all of
X's first-ranked votes where Y was ranked above X (X* becomes YX*). Y
cannot suddenly dominate all candidates in this way, and should

quickly

Post by John
lose ground: X might go first, but that just turns XZ* and XW* votes
into Z and W votes, and Z and W previously dominated Y and so Y

will be

Post by John
the /second/ eliminated if not the /first/.
/
/
#2 is similar. If you rank X first, Ranked Pairs will tend to get

to X

Post by John
sooner, possibly moving it ahead of a prior pairwise lock-in of Y, but
not behind. The losses for X get weaker and the wins get stronger. X
also necessarily cannot be the plurality loser in Tideman's

Alternative,

Post by John
and will not change its position relative to Y. X must be

preceded by a

Post by John
candidate already in the Smith Set prior to casting the ballot for the
winner to change from X to Y.
#3 suggests similar: if a candidate Z precedes X and is not in the
Smith set after casting the ballot, X is the first candidate, and #2
holds (this is ISDA).
#4 might be wrong: pulling Z into the Smith set by ZXY might not be
able to change the winner from X.
#5 suggests you can't switch from X to Y unless the ballot ranks Z

over

Post by John
X /and/ Y has a beatpath that reaches X through Z.
I haven't tested or evaluated any of these; I suspect some of

these are

Post by John
true, some are false, and some are weaker statements than what

does hold

Post by John
true.
The fact that Condorcet methods fail participation is fairly
immaterial. I want to know WHEN they fail participation. I

suspect, to

Post by John
be short, that a Condorcet method exists (e.g. any ISDA method) which
can only fail participation when the winner is not the first Smith-set
candidate ranked on the ballot. Likewise, I suspect that the
probability of such failure is vanishingly-small for some methods, and
relies on particular and uncommon conditions in the graph.
----
Election-Methods mailing list - see http://electorama.com/em for

list info

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

Kristofer Munsterhjelm

2018-08-10 12:58:31 UTC

Post by John
That method is NP-hard and involves complex tabulation.

Determining the winner is also NP-hard, as given in

BARTHOLDI, John; TOVEY, Craig A.; TRICK, Michael A. Voting schemes for
which it can be difficult to tell who won the election. Social Choice
and welfare, 1989, 6.2: 157-165,

theorem 2 (p. 163).

Post by VoteFair
So, if there are, say, 150 candidates, most of those candidates can
easily be identified as not winning, and I'd guess there would be, at
most, 15 candidates who might be able to win, and, in a worst-case
scenario, the full ranking of those 15 candidates can be calculated --
with the raw Condorcet-Kemeny method -- within a few hours at most. If
there are "just" 12 might-win candidates, the calculations take just a
few seconds at most.

What you're saying here is more that the intractability of an NP-hard
problem is a worst case property. That is true (assuming P != NP). For
instance, 3-SAT or integer linear programming is NP-hard, but many
instances of 3-SAT of IP problems are easy to solve in practice (e.g.
integer programs with totally unimodular constraint matrices). Likewise,
some Kemeny instances are very easy indeed, but the problem of finding
the winner is still NP-hard.

Post by VoteFair
Another way to say this is that if there is circular ambiguity that
amounts to a near-tie among 20 or more candidates, then, yes, the
calculations, in theory, would take a very long time. How often would
that occur? So rarely that it's not an issue in real-life elections.
It's more of an academic issue.
As for "complex tabulation," the results are calculated from the
pairwise counts, the same as for any Condorcet method. If you are
referring to the task of writing the code to do the calculations, I've
https://github.com/cpsolver/VoteFair-ranking

To my knowledge, that method is not the same as the Kemeny method. That
is, there exist elections where the Kemeny winner is X and the VoteFair
ranking software returns Y as the winner. They may be unlikely, but as
long as there exists at least one such election, the method is not the
same, mathematically speaking.

After adjusting an old script of mine, it finds the following example:

1: A>E>G>B>D>F>C
1: B>F>D>A>G>E>C
1: C>G>B>E>F>D>A
1: F>A>E>D>B>C>G
1: F>C>D>A>E>G>B

The script says that VoteFair elects B here (with full ordering
B>F>A>D>E>C>G).
The best Kemeny ordering starting with B is B>F>D>A>E>C>G with score 64,
but the best Kemeny ordering starting with F is F>A>E>B>D>C>G with score
65. 65 is the maximum Kemeny score for this election, so F is the winner
according to Kemeny.

Post by VoteFair
The code also handles ties, meaning that if there are any ties at any
ranking levels, the full-ranking results include which choices are tied
at which levels. In other words, unlike some vote-counting code, this
code does not give up when it reaches a tie; instead it fully calculates
the full ranking, ties included.

If a tie between A and B for first place should exist whenever the
maximum Kemeny score achievable by an ordering starting with A is the
same as the maximum Kemeny score by an ordering starting with B, then
there are instances where two candidates are tied according to that
definition, but VoteFair doesn't find the tie. In my 2012 example, both
C>D>B>A and B>C>D>A have Kemeny score 44, but VoteFair does not rank C
and B equal.

The other direction is also possible. The script finds:

1: C>A>F>G>E>B>D
1: E>B>G>C>D>A>F
1: F>D>B>C>E>A>G

where C is the unique Kemeny winner (C>F>E>B>D>A>G with score 40), but
VoteFair considers B, C, and F tied for first (full ordering:
B=C=F>E>A=D=G).

There may be bugs in my scripts, of course; if I've got any of those
observations wrong, tell me and I'll try to fix the bugs :-)
----
Election-Methods mailing list - see http://electorama.com

stephane.rouillon stephane.rouillon

2018-08-10 19:18:50 UTC

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

stephane.rouillon stephane.rouillon

2018-08-10 19:43:51 UTC

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

VoteFair

2018-08-11 05:22:32 UTC

Post by Kristofer Munsterhjelm
....
1: A>E>G>B>D>F>C
1: B>F>D>A>G>E>C
1: C>G>B>E>F>D>A
1: F>A>E>D>B>C>G
1: F>C>D>A>E>G>B

This is a good example of my point that real-life elections would almost
never have a carefully constructed situation like this where it would be
"NP-hard" to correctly calculate the winner using the Condorcet-Kemeny
method.

I do agree with Kristofer's correction that, in SOME cases, it can be
NP-hard to calculate the winner.

Both of theses concepts are related to the point that in a real-life
election of, say, 50 candidates or more, most of those candidates can be
dismissed as clearly not being a winner.

Yes, as the above example demonstrates, it is possible to carefully
construct a case where none of the candidates is easily dismissed, but
the key word here is "carefully."

In a real-life election, if such a convoluted/balanced/whatever case
arose, the ballots would be counted a second time, and that recount
would probably produce a different pairwise count.

Another way to say this (which I've said before) is that such cases are
analogous to correctly identifying which sand dune in a desert is really
the tallest sand dune. In contrast, real-life elections seldom involve
such closeness, and are more analogous to identifying the tallest
mountain peak in a mountain range, where the correct identification is
much easier to objectively recognize.

When an election is THAT "sand-dune-like" close, it's essentially a tie,
and there are time-honored ways to deal with ties.

Regarding cases where the VoteFair ranking software differs from the
Condorcet-Kemeny method, the software uses a setting that determines how
many top choices are used in the final calculation. Currently that
setting is, I believe, without looking, 6 choices. That's why the
example here has 7 choices. If that setting is changed to 12, then 13
choices would be needed in order to construct a case in which the
results differ (between VoteFair software and raw Condorcet-Kemeny
calculations).

In a real-life election such an uncertain result difference -- between
Condorcet-Kemeny and any other method, including Condorcet-Schulze and
even Instant-Runoff Voting -- would be analyzed by looking at the
pairwise counts for only the winners according to each method, and the
actual winner would be the choice that is confirmed to be preferred by
more than half the voters (not counting same-preference votes).

The only real-life election I've heard of where there were carefully
balanced ballots is in a city where everyone was related to everyone and
the voters paired up while in line to vote, and one person in the pair
agreed to vote for candidate/relative A and the other person agreed to
vote for candidate/relative B. The result, as intended, was an exact tie.

So, again, these edge cases are of interest to academic discussions --
including the ones here -- but these differences are not important in
the typical results of real-life elections involving thousands (or even
just hundreds) of voters. After all, as long as Instant-Runoff Voting
is seriously being considered by many people to be "fair," then the
subtleties that Kristofer refers to are way too insignificant to be
important in an actual election.

As a refinement, I'll more fully state that I predict that the
Condorcet-Kemeny method, and the "insertion-sort" calculation method
that is used in VoteFair popularity ranking to reduce the number of
candidates used in the final Condorcet-Kemeny calculations, will have
fewer failures according to most fairness criteria, compared to the
failures of other vote-counting methods.

To clarify, strictly speaking Kristofer is correct in all his
statements. Yet it's important to remember:

* The default setting specified in the VoteFair ranking software can be
increased so that the difference between "Kemeny" and "VoteFair"
requires more and more choices.

* As more and more choices are needed to carefully construct cases where
"Kemeny" and "VoteFair" differ, the probability of those cases occurring
in a real-life election are so small that they are similar to the odds
of getting an exact tie in plurality elections, and they can be handled
in the same way (typically involving a judicial ruling).

* Real-life elections so rarely involve NP-hard cases (that affect who
wins) that a long Condorcet-Kemeny computation time is as unlikely as an
exact tie in plurality counting. If a week-long calculation time were
needed to be certain of the Condorcet-Kemeny result, then the election
does not have a Condorcet winner, and ANY reasonable result -- by ANY
method -- is going to be very controversial, and probably subject to
judicial oversight.

When academic research finally analyzes the different vote-counting
methods to measure HOW OFTEN each method fails each fairness criterion,
then we will know whether the Condorcet-Kemeny method indeed has fewer
failures. Assuming it does, the minor issue of extremely rare,
carefully constructed, NP-hard (long-computation-time) cases becomes
insignificant as a barrier to its use.

Richard Fobes

Post by John
That method is NP-hard and involves complex tabulation.

Determining the winner is also NP-hard, as given in
BARTHOLDI, John; TOVEY, Craig A.; TRICK, Michael A. Voting schemes for
which it can be difficult to tell who won the election. Social Choice
and welfare, 1989, 6.2: 157-165,
theorem 2 (p. 163).

Post by VoteFair
So, if there are, say, 150 candidates, most of those candidates can
easily be identified as not winning, and I'd guess there would be, at
most, 15 candidates who might be able to win, and, in a worst-case
scenario, the full ranking of those 15 candidates can be calculated --
with the raw Condorcet-Kemeny method -- within a few hours at most.
If there are "just" 12 might-win candidates, the calculations take
just a few seconds at most.

To my knowledge, that method is not the same as the Kemeny method. That
is, there exist elections where the Kemeny winner is X and the VoteFair
ranking software returns Y as the winner. They may be unlikely, but as
long as there exists at least one such election, the method is not the
same, mathematically speaking.
1: A>E>G>B>D>F>C
1: B>F>D>A>G>E>C
1: C>G>B>E>F>D>A
1: F>A>E>D>B>C>G
1: F>C>D>A>E>G>B
The script says that VoteFair elects B here (with full ordering
B>F>A>D>E>C>G).
The best Kemeny ordering starting with B is B>F>D>A>E>C>G with score 64,
but the best Kemeny ordering starting with F is F>A>E>B>D>C>G with score
65. 65 is the maximum Kemeny score for this election, so F is the winner
according to Kemeny.

Post by VoteFair
The code also handles ties, meaning that if there are any ties at any
ranking levels, the full-ranking results include which choices are
tied at which levels. In other words, unlike some vote-counting code,
this code does not give up when it reaches a tie; instead it fully
calculates the full ranking, ties included.

If a tie between A and B for first place should exist whenever the
maximum Kemeny score achievable by an ordering starting with A is the
same as the maximum Kemeny score by an ordering starting with B, then
there are instances where two candidates are tied according to that
definition, but VoteFair doesn't find the tie. In my 2012 example, both
C>D>B>A and B>C>D>A have Kemeny score 44, but VoteFair does not rank C
and B equal.
1: C>A>F>G>E>B>D
1: E>B>G>C>D>A>F
1: F>D>B>C>E>A>G
where C is the unique Kemeny winner (C>F>E>B>D>A>G with score 40), but
B=C=F>E>A=D=G).
There may be bugs in my scripts, of course; if I've got any of those
observations wrong, tell me and I'll try to fix the bugs :-)

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

Kristofer Munsterhjelm

2018-08-14 14:28:15 UTC

Post by Kristofer Munsterhjelm
....
1: A>E>G>B>D>F>C
1: B>F>D>A>G>E>C
1: C>G>B>E>F>D>A
1: F>A>E>D>B>C>G
1: F>C>D>A>E>G>B

As I said, it's always NP-hard, because NP-hard is a *worst-case property*.

The subset sum problem "given a set of numbers A and a number b, find a
subset of A that sums to b" is NP-hard (and the decision problem is
NP-complete).
However, if the numbers in A are so that the every number is greater in
value than the sum of all the numbers smaller than it, then it's easy.
All you have to do is find the greatest number less than b, add it to
the solution, subtract this number from b, and repeat. If you end up
with excess at the end, then there's no such subset of A that sums to b.

NP-hard is not always hard :-)

Post by VoteFair
Currently that setting is, I believe, without looking, 6 choices.
That's why the example here has 7 choices.

That was mainly for convenience. I have one with 5 as well, but it's
more messy as I haven't let the script run through as many different
examples:

1: A>B>D>E>C
1: A>C>B>D>E
1: A>D>C>B>E
1: A>E>B>D>C
1: B>E>C>A>D
1: B>E>C>A>D
1: C>A>D>B>E
1: C>B>E>A>D
1: C>B>E>A>D
1: D>C>A>B>E
1: D>C>B>E>A
1: D>C>E>B>A
1: D>E>A>B>C
1: D>E>A>B>C
1: E>C>A>D>B
1: E>C>D>B>A
1: E>D>B>C>A

According to Kemeny score, there's a tie for first between D and E
(score 93 for orderings D>C>B>E>A and E>C>A>D>B), but VoteFair says that
C (score 92 for C>E>A>D>B) is the unique winner.

In any case, I see what you're saying, but the introduction of "real
life cases" makes analysis much harder and can potentially open up
loopholes. For instance, IRV advocates sometimes claim that monotonicity
failure happens so rarely that IRV should be considered to pass
monotonicity in all real-world settings. From a mathematical point of
view, a method fails some property as long as there's at least one
example, but a common response is "but that one doesn't count, find
another".

For VoteFair, I don't think it's too likely that it gets the result
wrong in real life. But I could be wrong. I don't know if the number of
wrong-call elections stay low as the number of candidates increases, or
if there's some strategy that exploits these. In contrast, the behavior
of Kemeny itself is well known.

To avoid that tangle, perhaps you could use an algorithm that is always
correct, but in a few rare cases runs for a very long time (or times out
with "can't tell in the time allotted").

That way, all properties that hold for Kemeny would also hold for
VoteFair, and the counters would know whether they were in what a
hard-to-tell election or not without having to calculate the exact
Kemeny scores for comparison.

The simplest way to do that, that I can think of, is to use an integer
programming library/interface like Math::LP and set up the program for
solving a Kemeny election.
https://www.cs.cmu.edu/~conitzer/kemenyAAAI06.pdf page 4 gives a linear
programming approximation to determining the Kemeny score of a
candidate. The approximation is exact if the x_(a,b) variables are
specified to be integers.

There are also fixed-parameter tractable algorithms whose runtime is
polynomial if the number of upsets is fixed, but exponential in the
number of upsets, e.g.

RAMAN, Venkatesh; SAURABH, Saket. Parameterized algorithms for feedback
set problems and their duals in tournaments. Theoretical Computer
Science, 2006, 351.3: 446-458,

but coding them from scratch could be tedious.
----
Election-Methods mailing list - see http://electorama.com/em for list info

VoteFair

2018-08-16 04:23:29 UTC

Post by Kristofer Munsterhjelm
As I said, it's always NP-hard, because NP-hard is a *worst-case property*.

If you mean that the Condorcet-Kemeny METHOD is NP-hard, yes, I agree.

Post by Kristofer Munsterhjelm
NP-hard is not always hard :-)

Yes, this is my point.

Yet critics claim (or imply) that if the Condorcet-Kemeny method were
used in real-life elections, then the computation time would be too long.

As I've pointed out, long computation times for calculating a single
winner when there are more than about 50 (or maybe 200) ballots would be
very rare (regardless of how many candidates there are).

Post by Kristofer Munsterhjelm
....
1: A>B>D>E>C
1: A>C>B>D>E
1: A>D>C>B>E
1: A>E>B>D>C
1: B>E>C>A>D
1: B>E>C>A>D
1: C>A>D>B>E
1: C>B>E>A>D
1: C>B>E>A>D
1: D>C>A>B>E
1: D>C>B>E>A
1: D>C>E>B>A
1: D>E>A>B>C
1: D>E>A>B>C
1: E>C>A>D>B
1: E>C>D>B>A
1: E>D>B>C>A
According to Kemeny score, there's a tie for first between D and E
(score 93 for orderings D>C>B>E>A and E>C>A>D>B), but VoteFair says that
C (score 92 for C>E>A>D>B) is the unique winner.

The method created by John Kemeny does not specify how to deal with
ties. (If someone knows otherwise, I'd love to read what Kemeny wrote
about handling ties.)

The VoteFair ranking software DOES deal with ties.

It turns out that ties using the Condorcet-Kemeny method can be very
complex, and in subtle ways.

Before jumping to your complex case, it's useful to consider the simple
case where the result sequences D>C>B>E>A and C>D>B>E>A have the same
sequence scores. In this case it's obvious that D and C are tied.

In your example above, where D>C>B>E>A and E>C>A>D>B have the same
sequence score, this simplicity does not exist.

Without careful analysis I'm going to assume that the reason VoteFair
ranking identifies C as the winner is that C is pairwise preferred over
D and C is pairwise preferred over E.

(In a textbook the words "this exercise is left to the reader" would
appear here.)

Regardless of whether that assumption is correct (I don't have time to
check it), I'll repeat that you have identified a case where John
Kemeny's described method does not specify who should win!

When I was writing the code to handle ties I encountered some bizarre
cases where there was circular ambiguity in odd ways, such as in your
example.

The code I wrote and posted on GitHub (in the CPSolver account)
clarifies how I decided to resolve those tied cases.

When you claim that my software does not match what John Kemeny
described, remember that he did not specify what to do when there is
more than a single highest sequence score (or, more precisely, a single
lowest "Kemeny" score since his version counts opposition rather than
support).

I should clarify that the code at GitHub is more recent than the code at
VoteFair.org, so there might be some differences between those two
versions of the VoteFair ranking software. But those differences should
only apply to cases that involve ties. If there is only one highest
sequence score, both versions should produce the same results
(remembering to consider the setting that specifies how many choices to
consider when doing the full check-all-the-sequence-scores calculations).

Kristofer, I appreciate your rigorous checking of the Condorcet-Kemeny
method as calculated by my VoteFair ranking software. Thanks!

Post by Kristofer Munsterhjelm
....
.... For instance, IRV advocates sometimes claim that monotonicity
failure happens so rarely that IRV should be considered to pass
monotonicity in all real-world settings. From a mathematical point of
view, a method fails some property as long as there's at least one
example, but a common response is "but that one doesn't count, find
another".
For VoteFair, I don't think it's too likely that it gets the result
wrong in real life. But I could be wrong. I don't know if the number of
wrong-call elections stay low as the number of candidates increases, or
if there's some strategy that exploits these. In contrast, the behavior
of Kemeny itself is well known.

Actually measurements of HOW OFTEN each vote-counting method fails each
fairness criterion is not well-known.

If someone wants to tackle that ambitious project in a simpler way, it
can be done by running simulations that start with a few number of
ballots (maybe 9 to start with) and a few number of candidates (three),
and testing all possible preferences for all the voters. Then those
numbers can be increased one by one. That would yield measurements that
show whether the failure rate settles into an integer percentage value
(ignoring decimal numbers).

The tricky part of such an analysis is for the criteria that involve two
related scenarios, such as with and without a clone candidate.

If that analysis is ever done, the difference between the "official"
Condorcet-Kemeny method that does not handle ties, and the VoteFair
ranking method that does handle ties, will be very tiny!

What will be more interesting is to see if there is any significant
difference in frequencies between the insertion-sort-like-presort that
I've used in the VoteFair ranking software, and the "official" John
Kemeny method (with ties being avoided).

Richard Fobes

Post by Kristofer Munsterhjelm
....
1: A>E>G>B>D>F>C
1: B>F>D>A>G>E>C
1: C>G>B>E>F>D>A
1: F>A>E>D>B>C>G
1: F>C>D>A>E>G>B

As I said, it's always NP-hard, because NP-hard is a *worst-case property*.
The subset sum problem "given a set of numbers A and a number b, find a
subset of A that sums to b" is NP-hard (and the decision problem is
NP-complete).
However, if the numbers in A are so that the every number is greater in
value than the sum of all the numbers smaller than it, then it's easy.
All you have to do is find the greatest number less than b, add it to
the solution, subtract this number from b, and repeat. If you end up
with excess at the end, then there's no such subset of A that sums to b.
NP-hard is not always hard :-)

Post by VoteFair
Currently that setting is, I believe, without looking, 6 choices.
That's why the example here has 7 choices.

That was mainly for convenience. I have one with 5 as well, but it's
more messy as I haven't let the script run through as many different
1: A>B>D>E>C
1: A>C>B>D>E
1: A>D>C>B>E
1: A>E>B>D>C
1: B>E>C>A>D
1: B>E>C>A>D
1: C>A>D>B>E
1: C>B>E>A>D
1: C>B>E>A>D
1: D>C>A>B>E
1: D>C>B>E>A
1: D>C>E>B>A
1: D>E>A>B>C
1: D>E>A>B>C
1: E>C>A>D>B
1: E>C>D>B>A
1: E>D>B>C>A
According to Kemeny score, there's a tie for first between D and E
(score 93 for orderings D>C>B>E>A and E>C>A>D>B), but VoteFair says that
C (score 92 for C>E>A>D>B) is the unique winner.
In any case, I see what you're saying, but the introduction of "real
life cases" makes analysis much harder and can potentially open up
loopholes. For instance, IRV advocates sometimes claim that monotonicity
failure happens so rarely that IRV should be considered to pass
monotonicity in all real-world settings. From a mathematical point of
view, a method fails some property as long as there's at least one
example, but a common response is "but that one doesn't count, find
another".
For VoteFair, I don't think it's too likely that it gets the result
wrong in real life. But I could be wrong. I don't know if the number of
wrong-call elections stay low as the number of candidates increases, or
if there's some strategy that exploits these. In contrast, the behavior
of Kemeny itself is well known.
To avoid that tangle, perhaps you could use an algorithm that is always
correct, but in a few rare cases runs for a very long time (or times out
with "can't tell in the time allotted").
That way, all properties that hold for Kemeny would also hold for
VoteFair, and the counters would know whether they were in what a
hard-to-tell election or not without having to calculate the exact
Kemeny scores for comparison.
The simplest way to do that, that I can think of, is to use an integer
programming library/interface like Math::LP and set up the program for
solving a Kemeny election.
https://www.cs.cmu.edu/~conitzer/kemenyAAAI06.pdf page 4 gives a linear
programming approximation to determining the Kemeny score of a
candidate. The approximation is exact if the x_(a,b) variables are
specified to be integers.
There are also fixed-parameter tractable algorithms whose runtime is
polynomial if the number of upsets is fixed, but exponential in the
number of upsets, e.g.
RAMAN, Venkatesh; SAURABH, Saket. Parameterized algorithms for feedback
set problems and their duals in tournaments. Theoretical Computer
Science, 2006, 351.3: 446-458,
but coding them from scratch could be tedious.

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

Kristofer Munsterhjelm

2018-09-01 22:41:34 UTC

Post by Kristofer Munsterhjelm
As I said, it's always NP-hard, because NP-hard is a *worst-case property*.

If you mean that the Condorcet-Kemeny METHOD is NP-hard, yes, I agree.

Method X being NP-hard means "if you're given an algorithm that can
solve any instance of X in polynomial time, you can solve any decision
problem that is in NP in polynomial time, as well". Since these
reductions are on a method level rather than on an instance level,
NP-hardness is only defined for problems as a whole.

So you can't say that a problem instance is or isn't NP-hard. Hence "the
METHOD is NP-hard" is the only way one can speak of NP-hardness.

Post by VoteFair
Yet critics claim (or imply) that if the Condorcet-Kemeny method were
used in real-life elections, then the computation time would be too long.
As I've pointed out, long computation times for calculating a single
winner when there are more than about 50 (or maybe 200) ballots would be
very rare (regardless of how many candidates there are).

The Conitzer et al. paper I linked to in my previous post makes a
similar point. Because the mixed integer programming approach can
quickly handle instances up to 40 candidates (using a good solver), even
with voting patterns close to a tie, runtime is not the problem in
itself. The only ways this could count against Kemeny is if we can find
another method that is not NP-hard and is otherwise as good as Kemeny,
or if the context is so that we deal with enormous numbers of candidates
(e.g. web page ranking).

My argument against Kemeny would probably be a combination of the former
above (there are simpler methods that do just as well) and that Kemeny
itself isn't cloneproof, so it's more vulnerable to tactical nomination
than methods that are cloneproof. Thus I'd prefer MAM/Ranked Pairs,
which is cloneproof, simpler to implement, and always polytime if you
accept tiebreaking by random voter hierarchy.

Of course, implicit in this is my value judgement that consistency is
not all that important a criterion. Since every Condorcet method fails
reinforcement, it seems unlikely that someone would say "I like methods
where, if you have two districts and the same winner comes up in both,
the election with the two ballot sets combined should also have the same
winner. No Condorcet method does that, but at least Kemeny does it if
the complete social order is the same in both districts, so I'm going to
choose that one". Others might disagree with me.

The method created by John Kemeny does not specify how to deal with
about handling ties.) >
The VoteFair ranking software DOES deal with ties.

I was under the impression that VoteFair's standard was to rank
candidates according to their Kemeny score, e.g. if there's an order
starting with A with Kemeny score 91 and another starting with B with
Kemeny score 92, you get B>A. This would make sense given how you said
that VoteFair was primarily concerned with winners rather than full
orderings, because ranking by Kemeny score would show how good a claim
each candidate has on being the winner.

But from what you're saying, it seems that I'm wrong, and that you're
instead aiming to preserve the actual Kemeny ordering, i.e. if A>B>C>D
is the unique ordering with the highest Kemeny score, VoteFair should
return A>B>C>D in that order, even if, say, the greatest Kemeny score
ordering starting in C has a greater Kemeny score than the greatest
ordering starting in B.

As for dealing with ties, I can think of two ways of doing so. The first
is to use random voter hierarchy to construct a tiebreaker ordering and
adding an epsilon (less than 1/numvoters^2) to every pairwise contest
that agrees with the tiebreaker ordering. The second is to find every
ordering that has maximum Kemeny score and recursively apply Kemeny to
the orderings. Both tiebreaking methods preserve (their own) variant of
consistency.

The former would pass that if the tiebreak is the same for both, or if
one district has a certain ordering be the unambiguous winner (no ties)
and the other has that ordering tied with some others, and has that
ordering as the RVH tiebreak, then the result for the combined district
will be the same as for those two districts.

The latter would pass it if both districts are ties with the same set of
orderings tied for maximum Kemeny score, then the combined result would
also have that set of orderings tied for maximum Kemeny score, and so
the tiebreaker would provide the same result.

It seems your approach is more in the spirit of the latter (as combining
A>B>C>D and A>B>D>C to A>B>C=D looks like some kind of aggregation),
except that the Kemeny method only returns strict orderings, and so
would still need some final tiebreak or adjustment to deal with that
scenario.

Post by VoteFair
Actually measurements of HOW OFTEN each vote-counting method fails each
fairness criterion is not well-known.

The problem with such a calculation is that it depends on the
distribution of ballots. Formally speaking, the chance of getting a
wrong scenario with k voters and n candidates is

integral over all k-voter, n-candidate ballot sets x: p(x) * L(x) dx

where L(x) is 1 if the method gets it wrong and 0 otherwise. We may
replace the integral with an averaging operation if voter weights are
always integer-valued (as in a real election).

However, p(x), the probability of encountering ballot x, depends on how
voters behave, and how the method induces the voters to behave, and
opens up a considerable element of ambiguity. That's the problem with
determining how often something happens. The criterion compliance
approach to getting around this problem is to ensure that L(x) is zero
for all possible x, as then the integral (or mean) will be zero no
matter what.

If we just want a raw count, we can let p be some predefined probability
distribution, e.g. the Dirichlet distribution corresponding to choosing
n! random numbers subject to that they sum up to k, or the discrete
impartical culture which consists of picking a random ordering of the
candidates and letting that be a ballot, k times. But such choices are
still vulnerable to the claim that this amplifies/attenuates realistic
regions and attenuates/amplifies unrealistic ones.

For VoteFair, I think the value of the integral will be small for any
reasonable probability distribution, at least unless there are too many
candidates. But if we, instead of using a method that always runs in
polynomial time but sometimes gets it wrong, use a method that always
gets it right but sometimes takes a long time, then we would sidestep
the whole issue entirely. So why not do so?

Post by VoteFair
The tricky part of such an analysis is for the criteria that involve two
related scenarios, such as with and without a clone candidate.

There are two ways of doing that, I think. To use monotonicity as an
example:

The first is to consider ballot set X to exhibit a monotonicity failure
if there exists some ballot set Y so that:
- the method elects some candidate A when given ballot set X
- Y is equal to X, except that on some ballots, A has been raised
(moved up in rank)
- the method elects someone else than A when given ballot set Y

(and similarly for X not electing A and then lowering A makes A win)

The second is to consider all pairs X, Y so that
- the method elects A when given ballot set X
- Y is equal to X, except that on some ballots, A has been raised
(moved up in rank)

and then consider how many of these (X,Y) pairs have the method elect
someone else than A when Y is given to the method, relative to the
number of (X,Y) pairs possible.

I prefer the former, because the latter doesn't mirror what really
happens. The voters vote, and then the result is called; they don't
vote, get a result, and then modify their ballots to (e.g.) raise the
winner.
----
Election-Methods mailing list - see http://electorama.

VoteFair

2018-09-05 17:39:58 UTC

...

Post by Kristofer Munsterhjelm
I was under the impression that VoteFair's standard was to rank
candidates according to their Kemeny score, e.g. if there's an order
starting with A with Kemeny score 91 and another starting with B with
Kemeny score 92, you get B>A. ....
But from what you're saying, it seems that I'm wrong, and that you're
instead aiming to preserve the actual Kemeny ordering, i.e. if A>B>C>D
is the unique ordering with the highest Kemeny score, VoteFair should
return A>B>C>D in that order, even if, say, the greatest Kemeny score
ordering starting in C has a greater Kemeny score than the greatest
ordering starting in B.

That's right, only the highest score is significant. And it is
associated with a ranking or sequence, and NOT associated with a
specific candidate.

Specifically, in VoteFair popularity ranking, the sequence that is
associated with the highest "sequence score" indicates the full ranking
from most popular to least popular.

For clarification, in the method described by John Kemeny, the sequence
associated with the LOWEST "Kemeny score" indicates the full ranking.
Remember that the method described by John Kemeny counts opposition
rather than support.

Post by Kristofer Munsterhjelm
As for dealing with ties, I can think of two ways of doing so. ...

Keep in mind that there are several kinds of ties.

One kind of tie that can happen in the Condorcet-Kemeny method is when
more than one sequence has the same highest "sequence score" (or the
lowest "Kemeny score").

The method described by John Kemeny does not deal with how to resolve
such a tie.

The VoteFair ranking software, which is available as open-source code,
does specify how to deal with that kind of tie.

Another kind of tie is when two (or more) candidates are tied -- either
for the winning seat or at any other ranking that might be significant.

I think this is the kind of tie your suggestions refer to. If so, ...

My recommended approach is to first recount the ballots, and then, if
there is still the same tie, a judicial court can cast a tie-breaking
ballot. In the case of any method that uses 1-2-3 ballots, the
tie-breaking ballot cannot rank two candidates at the same preference level.

If instead you are thinking of something like the ties that can occur in
IRV where an elimination round can involve a tie, then such a
tie-breaking method that looks deeper into the ballots to resolve the
tie is actually a technique for overcoming the fact that the raw method
itself ignores very significant preference information.

The Condorcet-Kemeny method does not have that weakness. Basically the
method looks "deeply" into all the ballots. As a result, there is not
any preference information being ignored that should be reconsidered as
part of a method-specific way to resolve such a "tie."

Post by VoteFair
Actually measurements of HOW OFTEN each vote-counting method fails each
fairness criterion is not well-known.

The problem with such a calculation ...

Later, when I have time again, I'll reply to this part of your message.
And I'll start a new thread because this topic applies to all methods.

Once again, thank you Kristofer for your great contributions to this forum!

Richard Fobes

Post by Kristofer Munsterhjelm
As I said, it's always NP-hard, because NP-hard is a *worst-case property*.

If you mean that the Condorcet-Kemeny METHOD is NP-hard, yes, I agree.

Method X being NP-hard means "if you're given an algorithm that can
solve any instance of X in polynomial time, you can solve any decision
problem that is in NP in polynomial time, as well". Since these
reductions are on a method level rather than on an instance level,
NP-hardness is only defined for problems as a whole.
So you can't say that a problem instance is or isn't NP-hard. Hence "the
METHOD is NP-hard" is the only way one can speak of NP-hardness.

The Conitzer et al. paper I linked to in my previous post makes a
similar point. Because the mixed integer programming approach can
quickly handle instances up to 40 candidates (using a good solver), even
with voting patterns close to a tie, runtime is not the problem in
itself. The only ways this could count against Kemeny is if we can find
another method that is not NP-hard and is otherwise as good as Kemeny,
or if the context is so that we deal with enormous numbers of candidates
(e.g. web page ranking).
My argument against Kemeny would probably be a combination of the former
above (there are simpler methods that do just as well) and that Kemeny
itself isn't cloneproof, so it's more vulnerable to tactical nomination
than methods that are cloneproof. Thus I'd prefer MAM/Ranked Pairs,
which is cloneproof, simpler to implement, and always polytime if you
accept tiebreaking by random voter hierarchy.
Of course, implicit in this is my value judgement that consistency is
not all that important a criterion. Since every Condorcet method fails
reinforcement, it seems unlikely that someone would say "I like methods
where, if you have two districts and the same winner comes up in both,
the election with the two ballot sets combined should also have the same
winner. No Condorcet method does that, but at least Kemeny does it if
the complete social order is the same in both districts, so I'm going to
choose that one". Others might disagree with me.

The method created by John Kemeny does not specify how to deal with
about handling ties.) >
The VoteFair ranking software DOES deal with ties.

I was under the impression that VoteFair's standard was to rank
candidates according to their Kemeny score, e.g. if there's an order
starting with A with Kemeny score 91 and another starting with B with
Kemeny score 92, you get B>A. This would make sense given how you said
that VoteFair was primarily concerned with winners rather than full
orderings, because ranking by Kemeny score would show how good a claim
each candidate has on being the winner.
But from what you're saying, it seems that I'm wrong, and that you're
instead aiming to preserve the actual Kemeny ordering, i.e. if A>B>C>D
is the unique ordering with the highest Kemeny score, VoteFair should
return A>B>C>D in that order, even if, say, the greatest Kemeny score
ordering starting in C has a greater Kemeny score than the greatest
ordering starting in B.
As for dealing with ties, I can think of two ways of doing so. The first
is to use random voter hierarchy to construct a tiebreaker ordering and
adding an epsilon (less than 1/numvoters^2) to every pairwise contest
that agrees with the tiebreaker ordering. The second is to find every
ordering that has maximum Kemeny score and recursively apply Kemeny to
the orderings. Both tiebreaking methods preserve (their own) variant of
consistency.
The former would pass that if the tiebreak is the same for both, or if
one district has a certain ordering be the unambiguous winner (no ties)
and the other has that ordering tied with some others, and has that
ordering as the RVH tiebreak, then the result for the combined district
will be the same as for those two districts.
The latter would pass it if both districts are ties with the same set of
orderings tied for maximum Kemeny score, then the combined result would
also have that set of orderings tied for maximum Kemeny score, and so
the tiebreaker would provide the same result.
It seems your approach is more in the spirit of the latter (as combining
A>B>C>D and A>B>D>C to A>B>C=D looks like some kind of aggregation),
except that the Kemeny method only returns strict orderings, and so
would still need some final tiebreak or adjustment to deal with that
scenario.

Post by VoteFair
Actually measurements of HOW OFTEN each vote-counting method fails each
fairness criterion is not well-known.

The problem with such a calculation is that it depends on the
distribution of ballots. Formally speaking, the chance of getting a
wrong scenario with k voters and n candidates is
integral over all k-voter, n-candidate ballot sets x: p(x) * L(x) dx
where L(x) is 1 if the method gets it wrong and 0 otherwise. We may
replace the integral with an averaging operation if voter weights are
always integer-valued (as in a real election).
However, p(x), the probability of encountering ballot x, depends on how
voters behave, and how the method induces the voters to behave, and
opens up a considerable element of ambiguity. That's the problem with
determining how often something happens. The criterion compliance
approach to getting around this problem is to ensure that L(x) is zero
for all possible x, as then the integral (or mean) will be zero no
matter what.
If we just want a raw count, we can let p be some predefined probability
distribution, e.g. the Dirichlet distribution corresponding to choosing
n! random numbers subject to that they sum up to k, or the discrete
impartical culture which consists of picking a random ordering of the
candidates and letting that be a ballot, k times. But such choices are
still vulnerable to the claim that this amplifies/attenuates realistic
regions and attenuates/amplifies unrealistic ones.
For VoteFair, I think the value of the integral will be small for any
reasonable probability distribution, at least unless there are too many
candidates. But if we, instead of using a method that always runs in
polynomial time but sometimes gets it wrong, use a method that always
gets it right but sometimes takes a long time, then we would sidestep
the whole issue entirely. So why not do so?

Post by VoteFair
The tricky part of such an analysis is for the criteria that involve two
related scenarios, such as with and without a clone candidate.

There are two ways of doing that, I think. To use monotonicity as an
The first is to consider ballot set X to exhibit a monotonicity failure
- the method elects some candidate A when given ballot set X
- Y is equal to X, except that on some ballots, A has been raised
(moved up in rank)
- the method elects someone else than A when given ballot set Y
(and similarly for X not electing A and then lowering A makes A win)
The second is to consider all pairs X, Y so that
- the method elects A when given ballot set X
- Y is equal to X, except that on some ballots, A has been raised
(moved up in rank)
and then consider how many of these (X,Y) pairs have the method elect
someone else than A when Y is given to the method, relative to the
number of (X,Y) pairs possible.
I prefer the former, because the latter doesn't mirror what really
happens. The voters vote, and then the result is called; they don't
vote, get a result, and then modify their ballots to (e.g.) raise the
winner.

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

Markus Schulze

2018-08-09 06:00:59 UTC

Hallo,

Alternative Schwartz is O(n^2) polynomial and simple.

I guess that Alternative Schwartz is O(n^3) polynomial
because the Schwartz set has to be re-calculated after
each stage.

Markus Schulze

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

Markus Schulze

2018-08-09 09:42:56 UTC

Hallo,

I suspect that a Condorcet method exists (e.g. any ISDA method)
which can only fail participation when the winner is not the
first Smith-set candidate ranked on the ballot.

Woodall's mono-add-top criterion says that adding ballots,
each with candidate A strictly preferred to every other candidate,
must not change the winner from candidate A to some other candidate.

To the best of my knowledge, there is no election method that
has been proven to satisfy the Smith criterion and mono-add-top.

Markus Schulze

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

Kristofer Munsterhjelm

2018-08-09 18:29:17 UTC

Not all Condorcet methods are Smith-efficient. For instance, Minmax is not.

Post by John
From that standpoint, each Condorcet method represents an arbitrary
selection of a candidate from a pool of identified suitable candidates.
Ranked Pairs elects the candidate with the strongest rankings; Schulze
elects a more-suitable candidate with less voter regret (eliminates
candidates with relatively large pairwise losses); Tideman's Alternative
methods resist tactical voting and elect some candidate or another.

I think that's more true of methods that go "If the CW exists, elect
him, otherwise...". Consider the Ranked Pairs method, for instance. The
RP method consists of sorting the pairwise victories in order of
magnitude (and tiebreaking by random voter hierarchy if necessary). It
then goes down the list, affirming pairwise victories unless there's a
contradiction with previously affirmed victories.

The procedure makes no explicit use of the Smith set, but always elects
from the Smith set because of how it works - if A is in Smith, and B is
not, then the affirming procedure will reach A>B before it reaches B>A,
so A will be ranked before B in the final ordering.

Such a proof is implicit, and thus is similar to say, a proof that IRV
passes mutual majority. (If a majority of the voters rank k candidates
above everybody else but not necessarily in the same order, then after
at least k eliminations, one of these candidates must be the only one
left from that group, and since Plurality meets Majority, the remaining
candidate can't be eliminated.)

Since one wouldn't usually say "IRV is a method that selects an
arbitrary candidate from a pool of identified suitable candidates - the
smallest mutual majority set", I don't think the description works for
implicitly Smith methods like Ranked Pairs either. Mathematically, both
are true (Ranked Pairs elects from Smith and IRV elects from the
smallest mutual majority set), but neither methods' logic go "first
identify the set, then do something to pick someone from it".

Post by John
Given that Tideman's Alternative methods resist tactical voting, one
might suggest a bona fide Condorcet candidate is automatically resistant
to tactical voting and thus unlikely to be impacted by the no-show paradox.

James Green-Armytage's paper on strategy resistance,
http://jamesgreenarmytage.com/strategy-utility.pdf , gives some proofs
as to when "Condorcetifying" a method only improves its strategic
resistance. If I recall correctly, making a method Condorcet-compliant
usually doesn't alter its susceptibility to burial while it improves its
resistance to compromising.

So exploiting Participation failure probably isn't a very viable
strategy, and for a Condorcet-compliant analog of some other method,
it's not more viable than doing it in the other method. The exception
would be methods that automatically pass Participation (DAC, DSC,
Plurality).

But I imagine Participation is more a paradox-avoidance criterion than
it is a strategic criterion, similar to monotonicity. (Again in my
opinion,) IRV's monotonicity failure isn't something that can be
exploited in strategy as much as it is evidence of the method "getting
it wrong". You have two ballot sets where going from the first to the
second only improves candidate A's situation, but A wins according to
the first ballot set yet loses in the second.

Markus Schulze replied to this more succinctly than I could, but to
restate: Suppose X is the CW. Then by 1., adding a ballot ranking X
first should not deprive X of the victory. Hence every Condorcet method
should pass mono-add-top if the starting scenario is one where the
winning candidate is the CW.

I don't know if that's true, but at a first glance, it seems to be too
strong. Suppose we have an election with an A>B>C>A cycle, and all of
these candidates beat candidate D pairwise, so that D is the Condorcet
loser and the Smith set is {A,B,C}. Suppose that the method being used
elects A. Also suppose the B>D pairwise victory is very weak, so that
adding two ADBC ballots reverses it to D>B. Then that could admit D into
the Smith set, and the internal logic of the method could make D win.
Yet D was ranked below A, the winner, on those ADBC ballots.

E.g. for Smith//Plurality:

34: D>A>B>C
33: D>B>C>A
33: D>C>A>B
51: A>B>C>D
50: B>C>A>D

The Smith set is {A, B, C}. Eliminating the non-Smith member D gives the
election:

85: A>B>C
83: B>C>A
33: C>A>B

where A has the most first preference votes and thus wins.

Adding two A>D>B>C ballots gives

34: D>A>B>C
33: D>B>C>A
33: D>C>A>B
51: A>B>C>D
50: B>C>A>D
2: A>D>B>C

where the Smith set is {A, B, C, D}, and thus D wins with 100 first
preference votes.

Since Smith//Plurality passes ISDA, that should answer your five
questions in the negative.

The only Condorcet method I know of that passes both Condorcet and
mono-add-top is Minmax (margins), but that method fails Smith. As
Schulze said, the question of whether Smith and mono-add-top are
compatible is open.
----
Election-Methods mailing list - see http://elect

John

2018-08-09 19:28:54 UTC

Not all Condorcet methods are Smith-efficient. For instance, Minmax is not.

True. Most methods attempt to resolve a Condorcet cycle, but must be
Smith-efficient for the above to be true. Most methods people talk about
(Schulze, Ranked Pairs) when advocating Condorcet over IRV in public
discourse are Smith-efficient.

I think that's more true of methods that go "If the CW exists, elect
him, otherwise...".

Not really. If a method provably always elects from a particular subset
(Smith, Schwartz) which can be identified by some algorithm, then that
method essentially elects from a pool of suitable candidates and excludes
other candidates identified as not-suitable. The decision to use such a
method inherently assumes that this subset is suitable and those outside
this subset are non-suitable.

paradox.
James Green-Armytage's paper on strategy resistance,
http://jamesgreenarmytage.com/strategy-utility.pdf , gives some proofs
as to when "Condorcetifying" a method only improves its strategic
resistance. If I recall correctly, making a method Condorcet-compliant
usually doesn't alter its susceptibility to burial while it improves its
resistance to compromising.

I intended that a set of ballots which produces a Condorcet cycle is
more-vulnerable to manipulation than a set of ballots which produces a
single Condorcet winner.

If the winner is just A (Condorcet winner), you have to defeat A before the
outcome can change. If B defeats A and is undefeated by all other
candidates, B becomes the Condorcet winner. If B defeats A but C (also
undefeated by all except A) defeats B, you have a Condorcet cycle: the
Smith Set is A B C.

In that situation, you want to rank B C A, because you need B to defeat C
or C to defeat A to change the winner from A, and you want B to defeat C.
If you rank B A C, you strengthen A's win over C.

So exploiting Participation failure probably isn't a very viable

Post by Kristofer Munsterhjelm
strategy, and for a Condorcet-compliant analog of some other method,
it's not more viable than doing it in the other method. The exception
would be methods that automatically pass Participation (DAC, DSC,
Plurality).

Burying a Condorcet candidate seems unlikely in real life, too. Think
about a two-nominee system using STV to pick a spectrum from each party
(two Democrats, two Greens, two Libertarians, two Republicans). Who is
getting buried? This is an even more interesting question when you add
Electoral Fusion, and so the Democrats and Greens end up nominating three
candidates instead of four. (Double-nomination avoids the problem of the
politically-active subset being more-extreme and reducing voter choice in
general elections in our two-plus system; Fusion is another approach).

In practice, ranked voting controls marginal risk: maybe your candidate of
choice is Ben Jealous, but you think Ian Schlakman would have also made an
excellent Democratic candidate. Do you bury Ian, or do you rank him second
to push back against Hogan? If you think Ben and Ian are going to split
the voteâthat the Greens are going to suck away 5% of the votes and make
Hogan the winnerâranked voting gives you a way to say hey, I like Ian, too,
but my vote is for Ben. If Hogan BEATS Ben by 1% and most Democrats ranked
Ian #2 while Republicans either bullet-voted or tried to bury Ben, guess
what? Ian and Ben have a mutual majority vote over Hogan.

In a Condorcet cycle, Ian would still probably fall away, and Greens who
voted Ben #2 would likewise push Ben above Hogan. That's actually the
likely outcome.

Hogan voters casting Hogan-Ian to try and bury Ben are only likely to push
Ian above Ben and end up sending Ben's votes to Ian (Hogan beats Ben, Ian
beats Ben, Ian wins).

You start adding in a second middle-right candidate (the Libertarian?) and
it gets more-complex.

Alternative Smith seems to me as if a burying strategy would only work if
you elected a less-desirable candidate. That is: if you like the
Republican (Hogan) more than the Libertarian, and you like the Libertarian
more than the Democrat (Ben), any attempt to bury potential winner Ben will
only succeed if you rank the Green (Ian) FIRST, then Hogan; and Ben is
between Ian and Hogan. Why?

You need Ian to defeat Ben and knock him out of the Condorcet Cycle, so you
need to rank Ian above Ben.

If there is a Condorcet cycle, then a third candidate must be ranked above
Hoganâlikely Ian.

In such a case, if Ben is in the cycle, Ian probably brings Hogan into the
cycle by losing to Ben but defeating Hogan, while Hogan beats Ben.
Alternative Smith removes the plurality loser; Ian has the fewest
first-ranked votes and goes first. You want to remove Ben? You rank Ian
above Hogan. Ian's votes and Hogan's strategic votes would have to total
together to beat Ben but not defeat Hogan; and Ben's second votes would
have to be placed on Ian so infrequently as to not close the gap and elect
Hogan.

Good luck with that.

Post by Kristofer Munsterhjelm
But I imagine Participation is more a paradox-avoidance criterion than
it is a strategic criterion, similar to monotonicity. (Again in my
opinion,) IRV's monotonicity failure isn't something that can be
exploited in strategy as much as it is evidence of the method "getting
it wrong". You have two ballot sets where going from the first to the
second only improves candidate A's situation, but A wins according to
the first ballot set yet loses in the second.

Yes. Voters need confidence that their vote does what they want. I think
the best we can do is say it usually does what they want.

IRV's failure is that the candidate elected seems to not be one favored by
anyone: you can have a Condorcet Winner, a Plurality Winner, and an IRV
Winner in a race between three candidates, and each candidate can be the
winner of each of these three methods. If the Condorcet Winner beats the
other two head-to-head and the Plurality winner just bluntly gets the most
votes when everyone is asked to pick one of the three, what in the heck is
the IRV winner?

With a Smith-efficient method, every candidate not in the Smith set would
lose one-on-one to any and all candidates in the Smith set. We can tell
the voters, with absolute authority, that those candidates excluded are
candidates who cannot win against any of the candidates we might elect.
You have that confidence that we'll elect someone meaningful to the
expressed will of the voters.

As for what the method does besides that, well, it may do something
strange. It follows a mathematical rule and will not give anyone the power
to dictate the winner; the precise outcome may have a confusing
relationship with the ballots cast, even though the group from which we
elect a winner has a very clear relationship.

If nothing else, it's less about ground game and more about the voters as a
whole finding the candidate acceptable. Everyone's vote matters. Under
plurality (and with sufficiently-few candidates), your vote doesn't matter
if your district is 60% Democrat or 60% Republican.

Markus Schulze replied to this more succinctly than I could, but to
restate: Suppose X is the CW. Then by 1., adding a ballot ranking X
first should not deprive X of the victory. Hence every Condorcet method
should pass mono-add-top if the starting scenario is one where the
winning candidate is the CW.
I don't know if that's true, but at a first glance, it seems to be too
strong. Suppose we have an election with an A>B>C>A cycle, and all of
these candidates beat candidate D pairwise, so that D is the Condorcet
loser and the Smith set is {A,B,C}. Suppose that the method being used
elects A. Also suppose the B>D pairwise victory is very weak, so that
adding two ADBC ballots reverses it to D>B. Then that could admit D into
the Smith set, and the internal logic of the method could make D win.
Yet D was ranked below A, the winner, on those ADBC ballots.
34: D>A>B>C
33: D>B>C>A
33: D>C>A>B
51: A>B>C>D
50: B>C>A>D
The Smith set is {A, B, C}. Eliminating the non-Smith member D gives the
85: A>B>C
83: B>C>A
33: C>A>B
where A has the most first preference votes and thus wins.
Adding two A>D>B>C ballots gives
34: D>A>B>C
33: D>B>C>A
33: D>C>A>B
51: A>B>C>D
50: B>C>A>D
2: A>D>B>C
where the Smith set is {A, B, C, D}, and thus D wins with 100 first
preference votes.
Since Smith//Plurality passes ISDA, that should answer your five
questions in the negative.

Interesting. I wonder if close victories are a solvable election problem
or if that's an error that simply will never go away. We just had an
election here where a candidate won by about 20 votes, and three candidates
all received nearly the same number of votes. Two hundred votes change and
the third-place winner is the first-place winnerâout of 80,000 votes.

If fifteen voters had voted Brochin instead of Olszewski, the results would
have reversed.

Now you tell me: what's the difference between that and the election you
describe above? I've been approaching this from a technical standpoint;
I'm starting to think there's a philosophical problem hereâone that can't
be solved. Condorcet triesâit achieves something akin to mutual majority
consensusâbut if the needle only has to move a few fractions of a
millimeter to change the winner, have we elected someone or did they simply
win a contest?

Post by Kristofer Munsterhjelm
The only Condorcet method I know of that passes both Condorcet and
mono-add-top is Minmax (margins), but that method fails Smith. As
Schulze said, the question of whether Smith and mono-add-top are
compatible is open.

Kristofer Munsterhjelm

2018-09-01 22:32:47 UTC