Participation criterion and Condorcet rules
On 2018-08-11 07:22, VoteFair wrote:
On 8/10/2018 5:58 AM, Kristofer Munsterhjelm wrote:
....
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.
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 :-)
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.
On 8/14/2018 7:28 AM, Kristofer Munsterhjelm wrote:
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.
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).
....
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!
....
.... 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
On 8/14/2018 7:28 AM, Kristofer Munsterhjelm wrote:
On 2018-08-11 07:22, VoteFair wrote:
On 8/10/2018 5:58 AM, Kristofer Munsterhjelm wrote:
....
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.
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 :-)
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.
On 2018-08-09 21:28, John wrote:
On Thu, Aug 9, 2018 at 2:29 PM Kristofer Munsterhjelm
<km_elmet@t-online.de mailto:km_elmet@t-online.de> wrote:
On 2018-08-07 18:05, 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.
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.
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...".
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.
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.
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.
If your setting automatically excludes ballot sets that have no
Condorcet cycles (thus ignoring universal domain), then Condorcet passes
all of Arrow's other criteria.
It passes Pareto dominance since if every voter prefers A to B, then A
pairwise beats B, and so A comes before B in the social ordering.
It passes monotonicity because if some voters decide to rank A higher,
then that can never make A lose to some other candidate B that A used to
beat pairwise.
It passes non-imposition because for any ordering of the candidates,
there exists a ballot set that would lead Condorcet to give this ordering.
And it passes IIA because A>B changing to B>A can't introduce a cycle
(if it could, it would be forbidden). Thus the order stays transitive
and whether A ranks ahead of C depends only on whether A beats C pairwise.
But introducing cycles provides a contradictory region that can't be
evened out, which makes Condorcet methods fail IIA. By Condorcetifying a
method (like Smith,IRV), you replace the contradictions of IRV with a
well-behaved Condorcet region and some other contradictions in the cycle
region and the border between the two.
Green-Armytage's paper that the changes usually reduce strategy.
However, they can introduce criterion failures where none existed before
(e.g. IRV meets LNHarm; Smith,IRV does not).
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.
It might be possible to use burial to exploit the boundary between
Condorcet winner and cycle. E.g. the Condorcet winner is a centrist
which IRV doesn't like; then some voters bury the centrist to create a
cycle for the benefit of the IRV winner. Something like a modified LCR:
43: L>C>R
35: R>C>L
10: C>R>L
Some R-voters then bury C under L:
43: L>C>R
33: R>C>L
2: R>L>C
10: C>R>L
Now the Smith set is {C, L, R} and so Smith,IRV chooses R.
Of course, I would still prefer Smith,IRV (or Alternative Smith; they're
very similar) to plain old IRV, because while the Condorcetified method
provides a bad result given strategy, IRV provides a bad result without
strategy.
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?
In a simple election, I think the easiest explanation is that the IRV
winner is "the strongest candidate of the strongest wing". E.g. the LCR
from above:
43: L>C>R
35: R>C>L
10: C>R>L
We have two "wings" (left and right) and a moderate position (center).
Condorcet tries to find the median, so C is the CW. L wins a Plurality
election due to C splitting the vote. But the right wing is stronger
than the left if the center is removed, which is what IRV does. It
successively removes weaker factions until it's a contest between two of
them, and then the stronger faction wins.
In more complex settings, IRV can get quite chaotic since it's
path-dependent. The fragmented Yee diagrams make this pretty clear.
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.
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.
In every voting method, a candidate is either elected or he isn't;
there's no such thing as "winning slightly". Similar to how rounding
must introduce a discontinuity on the output side (e.g. rounding to the
nearest integer, 0.5-epsilon is mapped to 0 and 0.5+epsilon to 1), a
voting method would also introduce a discontinuity. So you can't get
around close contests in full generality.
Stochastic methods like random ballot can get around this problem
because a continuous parameter is mapped to another continuous
parameter. You can "win slightly"; it just means that your probability
of being elected, while being low, is nonzero.
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.
The difference is that there isn't just a discontinuity, but that the
change itself is wrong.
If you had a two-candidate election like this:
49: A
50: B
and then two delayed ballots for A arrive, then that would flip the
winner from B to A. That's the discontinuity: a slight change in the
vote counts for A relative to B makes for a great change on the output
side. For something like Random Ballot, there would be no great change;
the probability of B winning would simply go from 50.5% to 49.5%.
However, the problem with a monotonicity failure is that something that
favors B happens, and it makes B lose. It's more like having the
two-candidate election above (where B wins), then two delayed ballots
voting for B (instead of A) arrive, and then the winner switches from
B to A. That would just be bizarre.
Since deterministic ranked voting methods are subject to Arrow's
theorem, we have to live with some measure of bizarre. Just what kinds
of bizarre we can banish entirely is a good question, but very hard to
answer.
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?
There's probably a statistical point to be made here, too. If you have
an election with a close margin like the two-candidate election above,
then it's possible that the winner just got lucky: a few ballots got
miscounted, or some of the voters just had a bad day and crossed off the
wrong candidate by accident.
If we have a model of how often those things happen, then we could
statistically determine whether the election is too close to call - at
least for Plurality elections. I don't know how to do it for more
complex ones like Condorcet.
More complex voting implementations (verifiable ballots, recounts, etc)
can decrease the noise in the process, making closer elections more
certain, but they can't get around any indecision in the voters' minds
themselves. On the other hand, if the result isn't close, it would be
sufficient to ask just a small sample (e.g. as
https://rsvoting.org/whitepaper/white_paper.pdf suggests). Perhaps one
could use deliberative polling if voter ignorance is a big problem, but
it could also have legitimacy and corruption problems if it were
directly used to decide winners rather than just to inform the public.
On 2018-08-16 06:23, VoteFair wrote:
On 8/14/2018 7:28 AM, Kristofer Munsterhjelm wrote:
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.
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.
....
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.
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.
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?
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.
On 9/1/2018 3:41 PM, Kristofer Munsterhjelm wrote:
On 2018-08-16 06:23, VoteFair wrote:
On 8/14/2018 7:28 AM, Kristofer Munsterhjelm wrote:
...
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.
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."
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
9/1/2018 3:41 PM, Kristofer Munsterhjelm wrote:
On 2018-08-16 06:23, VoteFair wrote:
On 8/14/2018 7:28 AM, Kristofer Munsterhjelm wrote:
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.
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.
....
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.
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.
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?
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.