[EM] Participation criterion and Condorcet rules

[VoteFair]

On 8/8/2018 11:43 AM, John wrote:
 > 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


On 8/8/2018 11:43 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 at votefair.org
> <mailto:electionmethods at votefair.org>> wrote:
>
>     On 8/7/2018 9:05 AM, John wrote:
>      > 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"
>
>
>     On 8/7/2018 9:05 AM, John wrote:
>     > 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
>     > 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.
>     >
>     >
>     >
>     > ----
>     > Election-Methods mailing list - see http://electorama.com/em for
>     list info
>     >
>