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.

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 rankings
are disallowed:

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.

On 8/7/2018 9:05 AM, John wrote:

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"

On 8/7/2018 9:05 AM, John wrote:

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?

On Wed, Aug 8, 2018, 2:36 PM VoteFair electionmethods@votefair.org wrote:

On 2018-08-07 18:05, John wrote:

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

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".

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.

On Thu, Aug 9, 2018 at 2:29 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:

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.

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.

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

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.

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.

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?

On 8/8/2018 11:43 AM, John wrote:

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

On 8/8/2018 11:43 AM, John wrote:

On 2018-08-10 07:20, VoteFair wrote:

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).

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.

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.

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 :-)

On 8/10/2018 5:58 AM, Kristofer Munsterhjelm wrote:

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

On 8/10/2018 5:58 AM, Kristofer Munsterhjelm wrote: