Talk:Kemeny-Young method

From Wikipedia, the free encyclopedia

Contents 1 Example 2 Reply to Henrygb 3 VoteFair ranking moved to Kemeny-Young method 4 Relationship between VoteFair ranking and Kemeny-Young method 5 Cleanup 6 Arrow's Theorem 7 Corrections 8 Wording 9 Table reorganization 10 Characteristic table 10.1 Reply to CRGreathouse and Markus Schulze 11 VoteFair cleanup 12 Reinforcement? 13 Condorcet method? 14 Similarity to ranked pairs? 15 Polynomial runtime 16 Is K-Y NP-complete? 17 Runtime section 18 Some modifications 19 Reliable sources 20 Is Kemeny-Young even in NP? 21 Schulze conflict of interest 22 Characteristics 23 Reversal symmetry

[edit] Example

This needs an example. I am not certain how this works so let's try:

• 5 voters prefer A then B then C
• 4 voters prefer B then C then A
• 2 voters prefer C then A then B

So the A/B tally is 7/4, the B/C tally is 9/2, and C/A tally is 6/5. So:

• ABC gets 7+9+5=21
• BCA gets 4+9+6=19
• BAC gets 4+9+5=18
• CAB gets 7+2+6=15
• ACB gets 7+2+5=14
• CBA gets 4+2+6=12

So ABC wins, so A is preferred to B and to C. This fails the independence of irrelevant alternatives criterion since if B was not a candidate, C would be preferred to A. So the article is wrong when it says "A voting theory named Arrow's impossibility theorem is commonly misinterpreted to imply that a fair and full order-of-preference result cannot be achieved, but this theorem only applies to vote-aggregation methods (how vote counts are distributed), so it does not apply to VoteFair ranking nor the Condorcet method". Asumming I have understood. --Henrygb 23:09, 29 May 2006 (UTC)

[edit] Reply to Henrygb

You interpreted the method correctly. Here are the calculation details for your example.

You are correct in saying that VoteFair ranking does not achieve independence of irrelevant alternatives for the example you present, and this is a significant point, so I will edit the entry to make this clarification.

However, your example does not contradict my statement that Arrow's impossibility theorem does not apply to VoteFair ranking nor the Condorcet method. Do you agree? (The qualification that limits Arrow's theorem is expressed with the words "which aggregates voters' preferences" in the WikiPedia formal statement of the theorem.)

Based on your insightful feedback I have revised the paragraph to say:

A voting theory named Arrow's impossibility theorem is commonly misinterpreted to imply that a fair and full order-of-preference result cannot be achieved, but this theorem only applies to vote-aggregation methods (how vote counts are distributed), so it does not apply to VoteFair ranking nor the Condorcet method. VoteFair ranking achieves all the desired criteria that Arrow's theorem proves are simultaneously unavailable to vote-aggregation voting methods, except that VoteFair ranking can fail to achieve independence of irrelevant alternatives when a circular ambiguity is involved. (Note that this rare unfairness is not due to Arrow's theorem.)

VoteFair 06:40, 30 May 2006 (UTC)

I would not agree that it is "misinterpreted". Arrow's theorem does apply to Condorcet methods (of which this is one particular type). And with several candidates and multi-dimensional issues, circular ambiguities are not rare. The only cases where I think Arrow's theorem is not really meaningful are approval voting and range voting. --Henrygb 13:21, 30 May 2006 (UTC)

And something is wrong with your link at [1] as the IRV result should be a win for A, by 7 votes against 4 for B in the second round. --Henrygb 13:26, 30 May 2006 (UTC)

You are right that my software's IRV calculations produce the wrong result for your example, so I will find and fix that bug.

Speaking of examples, I will convert one of the VoteFair ranking examples from my book into HTML and add it to the VoteFair ranking page.

Although I do not believe that Arrow's theorem applies to either VoteFair ranking or the Condorcet method, I will adjust the wording to accommodate your objections.

My statement that Arrow's theorem is "commonly misinterpreted" refers to the mistaken belief that Arrow's theorem applies to all possible voting methods. In turn, this leads to the mistaken belief that all voting methods -- including VoteFair ranking and every future method that will ever be created -- have to be limited in their ability to satisfy all the desired criteria (unrestricted domain, non-imposition, non-dictatorship, monotonicity, and independence of irrelevant alternatives).

I'll expand the explanation of VoteFair ranking to include a section that explicitly addresses each of the following criteria: unrestricted domain, non-imposition, non-dictatorship, monotonicity, and independence of irrelevant alternatives. After all, that's what's really important.

I agree that circular ambiguities are not rare. My statement is intended to say that the occurrence of an irrelevant alternative altering the ranking is rare, and that (as far as I know) such an alteration only occurs when a circular ambiguity is involved. I'll improve the wording to make this clearer.

Thank you for your valuable feedback. I appreciate finally getting to communicate with someone who really understands voting!

VoteFair 19:33, 30 May 2006 (UTC)

[edit] VoteFair ranking moved to Kemeny-Young method

I moved the article "VoteFair ranking" to "Kemeny-Young method" because this is the name which is used in the literature for this method. Actually, already in 2004, I have told the author of this article that this method is usually known as "Kemeny-Young method". Markus Schulze 11:04, 3 June 2006 (UTC)

[edit] Relationship between VoteFair ranking and Kemeny-Young method

I am the person who created the VoteFair ranking page. The contents of the VoteFair ranking page (and its discussion) was moved (and tagged as a "minor edit"!) without first discussing the change, so this is my opportunity to explain why I created a new page, and how this change might be accommodated.

I created VoteFair ranking back in 1991 or 1992, without any knowledge of the Kemeny-Young method. After creating VoteFair ranking, but before I gave it a name, I looked for descriptions of such a voting method. I found none.

An e-mail message from Markus Schulze in 2004 claimed that VoteFair ranking overlapped the Kemeny-Young method. I could not find any indication as to when the Kemeny-Young method was created, so as far as I knew that method was derived from VoteFair ranking. The only description of the method I found made it clear that the Kemeny-Young calculations differ from VoteFair ranking calculations. Specifically, VoteFair ranking seeks to maximize a function, whereas Kemeny-Young seeks to minimize the inverse function.

Markus Schulze and Henrygb are two voting-method experts who agree that my VoteFair ranking description is suitable as a description of the Kemeny-Young method, so I am willing to trust their judgment regarding the suitability of my description for the Kemeny-Young method. Note that I still haven't yet found a full description of the method. The move of the VoteFair ranking page wiped out the previous contents for the Kemeny-Young method page, but as I recall the description was the same brief four-sentence paragraph I've seen elsewhere.

The existing Kemeny-Young method page clearly did not apply to the method used for VoteFair calculations. That's why I created the VoteFair ranking page.

Another reason I created a new page is that the important information about which voting criteria is met by the Kemeny-Young method does not apply to the VoteFair ranking method. As an example, VoteFair ranking meets the Condorcet criteria, but descriptions of the Kemeny-Young method indicate that it does not meet the Condorcet criteria. Rather than assume the methods were equivalent, and make corrections on that basis, I created the new page with VoteFair-ranking-specific information.

The fact that the pre-existing Kemeny-Young-method description is now gone suggests that we can expand the information to account for any differences between VoteFair ranking and the Kemeny-Young method.

VoteFair 07:21, 5 June 2006 (UTC)

[edit] Cleanup

I did a major cleanup on this page today, changing "VoteFair" to "Kemeny-Young" when it was used to refer to the system in general. The Kemeny-Young method, as such, has no implementation details; the two implementations are the classic Kemeny-Young implementation and the VoteFair method. I distinguish between these in the text -- for example, the VoteFair method advocates (correctly!) treating unranked alternatives as tied for last place; this is not a part of the general Kemeny-Young method, so stays "VoteFair".

I also removed many POV/advocacy phrases. I like Kemeny-Young, but this isn't the place for that.

I added a Dodgson matrix for the example. Here, again, I distinguish between the "tally table" implementation of VoteFair and the matrix, which is pretty standard in voting methods. (The tally table has length n(n-1) for n candidates, and this is prohibitively long for more than, ay, five candidates.)

Most importantly, I changed the table. Claiming it meets all criteria (except when there's a circular ambiguity) is POV; other methods describe this as not meeting criteria. Still, I kept the comment that it meets the criteria when there is a Condorcet winner in a * comment. While this may seem harsh, I actually strengthened the claims of the table -- I changed a "yes, but" answer on the Majority Criterion to a "Yes", since as a Condorcet method Kemeny-Young cannot fail to elect a majoriy winner. CRGreathouse (talk • contribs) 18:09, 28 July 2006 (UTC)

[edit] Arrow's Theorem

Kemeny-Young is subject to Arrow's Theorem, there's no doubt. It is a SWF and meets Pareto and non-dictatorship, so it doesn't meet IIA. No Condorcet method is IIA. CRGreathouse (talk • contribs) 18:09, 28 July 2006 (UTC)

[edit] Corrections

Thank you CRGreathouse for the clarifications about the origins of the Kemeny-Young method. Now I finally know that the Kemeny-Young method predates VoteFair ranking, and by how much. Also thank you for making other improvements.

I suggest that someone knowledgeable add to the John George Kemeny and Peyton Young pages a link to this Kemeny-Young page. (I'm an expert about VoteFair ranking, but I know nothing about the Kemeny-Young origins beyond what is here.)

Today I improved the correctness and clarity of this article. I also corrected grammar mistakes and improved the formatting.

Here are clarifications about changes that might be questioned:

• Please note that "VoteFair" is an adjective, not a noun.

• I reinserted the phrase "In all cases that do not involve circular ambiguity" into the appropriate "comments" entries (in the "criterion" table). Without this qualification those statements were not valid. The fact that this qualification appears in a footnote was not sufficient to clarify that the unqualified statements described the ideal criterion. Now the statements describe the Kemeny-Young/VoteFair characteristics.

• Based on the information in List of matrices I removed the word "Dodgson" for referring to the (square) matrix.

• I removed references to a "tally table" where it was more appropriate to refer to pairwise comparison counts. This way the wording fits both the Kemeny-Young method and VoteFair ranking. (Note: If sequence scores were not involved there would be no need to even mention tally tables.)

VoteFair 07:25, 3 December 2006 (UTC)

[edit] Wording

There are a few places in the table of characteristics that I think should be reworded.

For independence of clones:

The addition of a similar candidate decreases a candidate's chance of winning.

I think the statement should distinguish the candidate losing because the clone wins (which essentially all neutral voting methods violate) and losing to a third candidate which would have otherwise been defeated. Thoughts?

For non-dictatorship:

A single voter cannot control the outcome beyond what can be achieved by any other voter.

This is anonymity, right? Non-dictatorship states that no single voter can impose his will on the outcome in all cases; anonymity states that all voters are treated equally.

CRGreathouse (t | c) 16:39, 11 February 2007 (UTC)

[edit] Table reorganization

Thank you CRGreathouse and Schulze for your improvements.

I reorganized the fairness-criteria table. I added a column to clarify which fairness criteria are met for cases that do not involve circular ambiguity.

Please note: pointing out that the Kemeny-Young method achieves important fairness criteria when circular ambiguity is not involved is not POV! The difference between a voting method that never achieves an important fairness criteria and another voting method that achieves the fairness except in cases that involve circular ambiguity is very significant. As now clarified in the article, real-life elections seldom involve circular ambiguity in a way that affects who wins an election. Of course the distinction is important for academic and mathematical purposes, hence the use of two columns.

I also reworded the descriptions to apply to the ideal criteria rather than applying to the Kemeny-Young method.

VoteFair 08:16, 12 February 2007 (UTC)

Well, you wrote about "cases that do not involve circular ambiguity". However, it is not clear what a "case that does not involve circular ambiguity" is. Do you mean a "case that does not involve circular ambiguity according to the sincere preferences"? When we talk about criteria where preferences are modified or where the set of candidates is modified, does "cases that do not involve circular ambiguity" mean "cases that do not involve circular ambiguity in the original situation" or does it mean "cases that do not involve circular ambiguity in the modified situation"? Markus Schulze 10:10, 12 February 2007 (UTC)

To MarkusSchulze, the "modified situations" and "sincere" versus insincere issues you refer to involve the addition, removal, or modification of a single ballot. Whether that single-ballot change causes the overall results to cross the threshold between a case that involves circular ambiguity and a case that does not involve circular ambiguity is rather insignificant. Yet, to accomodate your concern I'm willing to adjust the wording to clarify this issue.

To CRGreathouse, you offer no explanation of why you undid my recent edits. They involve many improvements. As one example I didn't list earlier, the "runtime" criteria does not involve an fairness issue, which is what this table conveys, so I moved it outside the table. The reversion restored numerous mistaken and confusing wordings, so I'll restore the correction. In the future, please make specific edits if there is something you don't agree with.

VoteFair 20:15, 13 February 2007 (UTC)

Which of your recent edits did I undo? CRGreathouse (t | c) 03:31, 14 February 2007 (UTC)

Dear VoteFair, you wrote: "The 'runtime' criteria does not involve an fairness issue, which is what this table conveys." Well, the original text said: "The following table summarizes the desired criteria achieved by the Kemeny-Young method." You inserted the term "fairness" afterwards. Markus Schulze 16:54, 14 February 2007 (UTC)

In fairness, the term "desired" should probably be removed. I don't think that either polynomial runtime or IIA is necessarily desirable, though I like them being in the table. CRGreathouse (t | c) 18:25, 14 February 2007 (UTC)

[edit] Characteristic table

VoteFair, in your version you have Schwartz: unknown for cases without circular ties. If there are no circular ties, then there is a unique Condorcet winner, coincident with the Schwartz set. So this should be No in general but Yes in the case without circular ambiguities.

The problem I have with that column is that it is not special. Every Condorcet method shares there characteristics, and most other methods are similar, populated with mostly "yes" answers. This is the simplest case, and is not a good basis for comparing K-Y to other methods. It seems that it would be better suited to a Condorcet method(s) article.

What does everyone else think?

CRGreathouse (t | c) 14:05, 14 February 2007 (UTC)

Suppose the sincere preferences are 45 A > B > C, 35 C > B > A, 20 B > A > C. Then candidate B is the Condorcet winner.

However, if the 45 A > B > C voters had voted A > C > B instead (i.e. if they had "buried" candidate B), then the winner would have been candidate A. This demonstrates that the Kemeny-Young method is vulnerable to "burying" strategies even when there is no circular tie in the sincere situation.

If the 45 A > B > C voters had voted A > B = C instead, then the winner would have been candidate A. This demonstrates that the Kemeny-Young method violates later-no-harm even when there is no circular tie in the sincere situation.

So, whatever VoteFair wants to say, I guess that it is either false for the Kemeny-Young method or true for all Condorcet methods. Markus Schulze 16:54, 14 February 2007 (UTC)

Additionally, I'd like to comment on this new sentence:

The ability of the Kemeny-Young method to achieve fairness criteria in situations that do not involve circular ambiguity is indicated because real-life elections among political candidates seldom involve circular ambiguity in ways that affect who wins an election.

I don't think that this is true. Not much attention is given to such situations in "real-life elections" because most election methods aren't designed in a way that makes them apparent (e.g. FPTP in the US). In elections using Condorcet methods, such problems are fairly common, I'd say -- wasn't there coverage about one such case a few years back?

In any case it's hard to say because much of the way an election goes is shaped by the campaigning, which is in turn shaped by the voting system used. Surely Condorcet methods would be exploited just as plurality is currently exploited? CRGreathouse (t | c) 21:22, 14 February 2007 (UTC)

[edit] Reply to CRGreathouse and Markus Schulze

To CRGreathouse, I failed to notice that Markus Schulze made the major changes and used your name in his description: "Revision ... by CRCreathouse." I apologize for mistakenly attributing the changes to you.

To Markus Schulze, please limit your changes to the "Characteristics" section, instead of reverting the entire article. Also please limit your changes to the specific wording you object to -- instead of overwriting numerous wording improvements.

To CRGreathouse, as you requested I removed the word "desirable", and I changed "unknown" to "yes" as you suggested. I also tried to move the calculation-time issue inside the table as you requested, but it just doesn't fit as a meaningful yes-or-no criteria, and requires explanation beyond a single word. Also, every other row in the table refers to the characteristics of the results. I did move the calculation-time issue before the table so that it is clearer as to why the method has been slow to be appreciated.

To Markus Schulze, I have changed the "yes" items you object to; they are now indicated as "[see discussion page]" until we have resolved this issue.

According to the information on the tactical voting page, the "compromising", "burying", and "push-over" criteria refer to the effect of a single voter changing their ballot. In contrast, your example refers to a large number of voters changing their ballot. Is the information on the tactical voting page incorrect?

If some of the fairness-table information is also applicable to all Condorcet methods, you are certainly free to copy relevent portions to the Condorcet page. However, please note that the full-ranking nature of the Kemeny method requires different wordings from winner-only methods. Especially, some of the criteria refer to changes in popularity ranking, so they don't apply to the single-winner Condorcet method.

To CRGreathouse regarding your just-posted comment. You make a good point about "real-life" elections, so I'll reword that sentence.

Once again, thank you both for your feedback.

VoteFair 21:51, 14 February 2007 (UTC)

Regarding tactical voting: There's no difference between the two types. If a number of voters can change an election by compromising, burying, etc. then a single one can do the same. Consider the original situation and change the votes one at a time toward the compromised situation, noting which vote changes the outcome. Then consider the situation in which the votes just before the last voter are sincere: the single voter can now make the change.

Single-winner methods can usually be analyzed in the same fashion as ranking (weak-order) methods, since the former is simply a special case of the latter in which the remaining information is discarded. Which parts of the table do you feel need rewording?

As for the table's no circular ambiguities portion, I'm not sure that I like it. I'd like to see an analysis of which parts can differ within Condorcet methods. One example is clone immunity: K-Y is not immune to clones, but some Condorcet methods like Tideman's Ranked Pairs are. Which others are independent of the Condorcet criterion?

CRGreathouse (t | c) 22:27, 14 February 2007 (UTC)

Dear VoteFair, you wrote: "I have changed the 'yes' items you object to; they are now indicated as '[see discussion page]' until we have resolved this issue." Original research doesn't belong to Wikipedia articles. Markus Schulze 22:33, 14 February 2007 (UTC)

Doubtless there are sources for this, like the Condorcet.org website? CRGreathouse (t | c) 23:07, 14 February 2007 (UTC)

[edit] VoteFair cleanup

First, I'd like to thank Marcus for much of his recent cleanup; the article had many small problems which he corrected. Important among those was his change from VoteFair to Kemeny-Young. Here's the terminology I've tried to use:

• Kemeny-Young for the general voting method in this article, implementation aside.
• Kemeny for the particular K-Y implementation as discussed by Kemeny in his original paper.
• VoteFair for the particular K-Y implementation of Richard Fobes.

This sentence was removed in the edits:

To minimize invalid hand-marked order-of-preference ballots, the VoteFair method interprets unmarked choices as least-preferred, and more than one preference level can be indicated for the same choice, but only the highest-marked preference level (for each choice) is used.

Now in my mind choosing how to deal with ballots is not a part of the general method, but of the implementation.† I don't recall offhand if Kemeny's paper discusses this—I'll reread and see what I find. (Marcus no doubt already knows, as he's more broadly familiar with this field than I am.) VoteFair in particular requires the treatment mentioned above. A voting system that counts this differently (say, requiring voters to fill a full/linear order) would be a Kemeny-Young method, but I wouldn't call it a VoteFair method.

In short, I think that this sentence, or something like it, should be included in the article.

† Another implementation issue is the tallying, which in Kemeny is done negatively and in VoteFair is done positively. Other examples are welcome; if there are enough ot might merit a (sub)section.

CRGreathouse (t | c) 23:34, 14 February 2007 (UTC)

Thank you, CRGreathouse for your involvement! I agree that the separation of ballot-marking from ranking calculation makes sense. Keep in mind that I originally wrote this article as an entry under the name "VoteFair ranking" and Schulze commandeered it as the description of the Kemeny-Young method.

Clarification: I corrected the VoteFair references and changed "candidate" to "choice" (as appropriate) without realizing I wasn't logged in, so my edits today are probably signed with an IP address.

I removed the "runtime" criteria from the table because it is redundant information, already explained in an earlier paragraph.

At a later time we can deal with the issue of identifying the fairness achieved when circular ambiguity is not involved. Note to Schulze: This is not an issue of opinion; rather it clarifies important characteristics of the Kemeny-Young method.

VoteFair 18:30, 15 February 2007 (UTC)

I've already mentioned my thoughts on that table extension, so I won't bore you by repeating them. For the time, though, why don't you put the table as you would like it on your userspace (perhaps at User:VoteFair/KYTable) so you can edit it and put all needed clarifiers/caveats/etc. on it without being reverted? Then when you think it's ready, just put a link here on the Talk page so the rest of us can discuss it. CRGreathouse (t | c) 23:48, 15 February 2007 (UTC)

Dear VoteFair, you wrote: "In 1991 Richard Fobes independently created a mathematically equivalent variation of the original Kemeny calculation method and developed it under the name VoteFair ranking." Saying that this method was "independently created" would make sense only if the Kemeny-Young method wasn't yet published in 1991 or if it was still completely unknown in 1991 or if Richard Fobes discovered something new about this method. A person cannot claim credit for not reading academic publications.

You wrote: "In the VoteFair variation, each sequence score equals the sum of the pairwise counts that apply to the sequence, and the sequence with the highest score is identified as the overall ranking, from most popular to least popular. The original Kemeny method uses pairwise counts of voters who oppose each pairwise order, and the lowest sequence score is identified." It is easy to see that it makes no difference whether you use the supporting votes and maximize the score or whether you use the opposing votes and minimize the score. Therefore it makes no sence to treat this as two different methods.

You wrote: "I removed the 'runtime' criteria from the table because it is redundant information, already explained in an earlier paragraph." Well, one task of tables is to summarize what has already been said in the plain text. Markus Schulze 11:31, 16 February 2007 (UTC)

VoteFair ranking includes more than the part described here. The overlapping part is "VoteFair popularity ranking". VoteFair ranking also includes "VoteFair representation ranking", "VoteFair party ranking", "VoteFair cross-district partial-proportional representation", and ballot-marking and ballot-interpretation conventions, all of which are described in my book (and on my website).

I agree that lacking an awareness of published works does not allow someone to claim ownership or naming rights, but I don't claim ownership or naming rights. In my book, which I wrote before I discovered the mathematical equivalence to the K-Y method, I indicate that it's unlikely that such a great idea would go unnoticed by other people. So, to make you happier I'll change the word to "discovered" instead of "create" -- even though I created the idea in my mind without outside assistance. (Specifically I used the creative-problem-solving skills I described in my first book to create a solution to the world's biggest problem: unfair election results.)

If you want redundancy regarding "runtime", OK. I did correct the description to refer to the unsatisfied criteria -- so that it follows the convention of the other descriptions in the table.

VoteFair 19:59, 16 February 2007 (UTC)

[edit] Reinforcement?

First chapter says "this is only method which satisfies x, x and reinforcement", but nowhere it is explained what this reinforcement means, but it is rather important, as for example Schulze method satisfies first 2 as well, so this reinforcement is something which could make this method unique. Please explain what does that means and if there are other methods fulfilling it as well. —The preceding unsigned comment was added by 85.21.179.44 (talk) 16:29, 15 May 2007 (UTC).

Does your question refer to the word "reinforcement" in the second paragraph? I've written much of the content for this article -- because it also applies to VoteFair popularity ranking -- but I don't know what "reinforcement" refers to. I think Markus Schulze wrote that sentence. As you suggest, the Kemeny-Young method is unique and offers significant advantages, and "reinforcement" may be another one worth knowing about. Note that universality is another particularly important advantage. VoteFair 17:36, 18 May 2007 (UTC)

I believe "reinforcement" refers to Woodall's mono-add-top. In other words, adding ballots whose first preference is the previous winner, will never change the winner to somebody else. I think it is most likely incompatible with Smith. KVenzke 23:15, 20 May 2007 (UTC)

No, "reinforcement" doesn't refer to Woodall's mono-add-top. "Reinforcement" says that, when the same complete ranking of all candidates is chosen both in situation 1 and in situation 2, then the same complete ranking must also be chosen when situation 1 is added to situation 2. Thus, "reinforcement" is like "consistency", but for methods that produce a complete ranking of the candidates. Markus Schulze 12:35, 21 May 2007 (UTC)

[edit] Condorcet method?

Hard to quickly see WHAT this method is doing, but from tables seems like a categorical Condorcet method anyway. How come this isn't stated? I guess it is indirect as Category:Monotonic Condorcet methods Tom Ruen 01:22, 19 May 2007 (UTC)

As explained in the first sentence, this method "identif[ies] the most popular choice, and also identif[ies] the second-most popular choice, the third-most popular choice, and so on down to the least-popular choice." In other words it fully ranks all the choices. The characteristics table indicates that it satisfies the Condorcet criterion, and that means it is categorized as one of the "Condorcet methods." As explained in this article and the Condorcet article, it does not first do pairwise comparisons to see if a choice wins all the pairwise contests. Instead the calculations fully rank all the choices and if there is only an interest in who is the most popular, then the other rankings are ignored. Would it be helpful to add a second sentence saying "it fully ranks all the choices" or is that concept adequately conveyed by the statement in the first sentence? VoteFair 20:27, 20 May 2007 (UTC)

Some people consider the term "Condorcet" to be an euphemism. Some people (including Richard Fobes) consider the term "Condorcet" to be pejorative. See here. Therefore, the second group of people tries to avoid using this term wherever possible. Markus Schulze 12:35, 21 May 2007 (UTC)

Well, that would explain why I suppose. I'm no expert on Condorcet methods, but given 99% of elections will have a Condorcet winner, it seems senseless to not focus on this commonality. I'd put it in the first sentence. Tom Ruen 18:49, 21 May 2007 (UTC)

As suggested I've added the Condorcet reference to the first paragraph. The reason for not emphasizing this as a "Condorcet method" in the first sentence is that the Condorcet (methods, plural) category is easily mistaken for the Condorcet (calculation) method, and both terms tend to be associated with starting out by looking for a Condorcet winner. Also note that both Condorcet terms deal with a single winner, whereas this method fully ranks all the choices (and the Condorcet criteria only applies to the most popular choice).

Your figure of 99% is misleading because presumably it includes general elections, most of which involve only two viable/popular candidates. Many U.S. primary elections, especially Presidential primary elections, involve more than two viable candidates and many of those elections would not yield a Condorcet winner. Of course this is difficult to prove because we use single-mark ballots instead of preferential/ordinal ballots, which are needed for both the Condorcet and Kemeny-Young calculations. VoteFair 05:16, 22 May 2007 (UTC)

Well, I still must hope 99% of rank elections will have CW. :) Glad for the change. Thanks. Tom Ruen 19:18, 23 May 2007 (UTC)

The term "Condorcet method" has certainly been used to talk about methods that "fully ranks all the choices" -- what is known in Wikipedia as the Smith criterion is often referred to in the literature as the (generalized) Condorcet criterion. In any case I wouldn't know what the "Condorcet (calculation) method" is, especially since there are so many ways of finding the Condorcet winner.

CRGreathouse (t | c) 14:09, 23 May 2007 (UTC)

More popular Condorcet methods such as Ranked pairs or Schulze method do not start out by checking for a Condorcet winner. They also either form a complete ranking of the candidates, or offer a clear way to do this if one desired. KVenzke 17:44, 23 May 2007 (UTC)

If I understand the ranked pairs and Schulze methods correctly, these methods (after creating the same pairwise-comparison numbers that all these methods use) start out by identifying a winner, and then optionally they can go on to identify a second-place winner, third-place winner, and so on. In contrast, the Kemeny-Young method starts calculating sequence scores and identifies a full ranking sequence and never explicitly looks at any pairwise contests.

The original Condorcet calculation method identifes the Condorcet winner as the choice that wins every pairwise contest in which that choice is involved. As you point out, the methods being discussed here identify this same winner in different ways.

My point is that the Kemeny-Young method cannot calculate the Condorcet winner without also fully ranking all the choices. VoteFair 20:36, 24 May 2007 (UTC)

First of all, the standard method for ranked pairs creates a ranking first, and then a winner (if one is needed) is chosen by taking the top candidate in the ranking. (I'm less familiar with Schulze.)

Second, any method that creates the same ranking is the same method—Wikipedia doesn't have separate articles for different ways of calculating the same method. There are plenty of ways to calculate the Smith set, for example, but only one Smith set; many ways of getting the K-Y winner but only one K-Y method. I wouldn't be surprised at all if an algorithm for calculating the K-Y winner was devised that didn't give a complete ranking (though it would still take superpolynomial time).

CRGreathouse (t | c) 22:47, 24 May 2007 (UTC)

When the Schulze method is being used, then the beatpath tournament matrix p defines a complete ranking of all candidates (or, to be more concrete, an asymmetric, irreflexive, and transitive binary relation > over the candidates). There is no need to calculate the first-place winner, the second-place winner, the third-place winner, etc. one after the other. Markus Schulze 13:04, 25 May 2007 (UTC)

Yes, in fact you can't just get such an order by calculating the winner, removing, and generating a new list, right? (Minor note: asymmetric → irreflexive in your list.) CRGreathouse (t | c) 13:35, 25 May 2007 (UTC)

Exactly, you cannot get such an order by calculating in this manner. Markus Schulze 15:07, 25 May 2007 (UTC)

Thank you (all) for your clarifications. Now I can better appreciate your objections to my earlier statement that other Condorcet methods "[start] out by looking for a Condorcet winner."

Now that I better understand the ranked pairs and Schulze methods, I see a possible wording improvement regarding the Schulze method. Both the ranked-pairs and Schulze-method articles say the method "can also be used to create a sorted list of winners." For the Schulze method this could be strengthened by saying something like the method "produces a path from the winner to the weakest candidate and this path can be used to rank all the candidates from most popular to least popular." As computers now make the use of preferential ballots and ranking calculations easier, I think this clarification might be useful.

As for the ranked pairs method, the article states "[t]o create a sorted list, repeatedly use RP to select a winner, remove that winner from the list of candidates, and repeat (to find the next runner up, and so forth)." This seems to contradict the above assertion that the method "creates a ranking first, and then a winner (if one is needed) is chosen by taking the top candidate in the ranking." I can see that a future alternative calculation procedure might be able to produce the same results without successively identifying the next-most popular choice, which means the iterative characterization only applies to the currently described method.

Again, thanks for the clarifications. VoteFair 19:53, 28 May 2007 (UTC)

I think you are right that that commentary on RP is misguided. As far as Schulze, what happens is that when you've constructed the beatpath matrix, defeats on that matrix are transitive. That is, the winner beats everyone on that matrix. And there is a candidate who beats everyone except the first candidate. And so forth. KVenzke 17:53, 29 May 2007 (UTC)

[edit] Similarity to ranked pairs?

On another note, can someone tell me a situation in which ranked pairs and this method do not produce the same result? Let me show my reasoning with an example:

5 votes: A>B>C 4 votes: B>C>A 2 votes: C>A>B

A def. B 7-4, B def. C 9-2, C def. A 6-5.

Under ranked pairs, the strongest two defeats are chosen, so B>C and A>B (A wins). Under Kemeny-Young, A>B gets 7 points, A>C gets 5 points, B>A gets 4 points, B>C gets 9 points, C>A gets 6 points, and C>B gets 2 points.

The similarity to ranked pairs should already be apparent, as the strongest sequence score will go to the pairs with the largest margins or what would be considered winning votes. (Which is it? More on that later.) For example, consider the A>B>C order, and compare it to another logical order, C>A>B. A>B>C would get votes for A>B (7), B>C (9), and A>C (5). C>A>B trades out the losing number from A>C for a winning number, but the tradeoff is that another winning number must be traded out for the equivalent losing number. In this case, 5 becomes 6, but 9 becomes 2. The effect of the change from B>C to C>B outweighs that from A>C to C>A - for the exact same reason it does in ranked pairs and Schulze.

Let's add another candidate and do an example intended to include a tie, as well as a cycle:

7 votes: A>C>B>D 5 votes: B>D>A>C 4 votes: C>B>D>A 2 votes: D>C>A>B

In the table below, everything reads left side-top row.

	A	B	C	D
A	X	9-9	12-6	7-11
B	9-9	X	5-13	16-2
C	6-12	13-5	X	11-7
D	11-7	2-16	7-11	X

C>B, B>D, D>A, A>C. A=B but C>D. C>B>D seems obvious, but do we stick on A>C or D>A at the end?

According to ranked pairs, first we consider B>D 16-2, then C>B 13-5, then A>C 12-6, then discard D>A 11-7. Under Kemeny-Young, for C>B>D>A we consider C>B=13, C>D=11, C>A=6, B>D=16, B>A=9, and D>A=11. For A>C>B>D, all the ones that don't involve A are the same. The ones that do are flipped, so the 6 becomes a 12 and the 11 becomes a 7. Again, larger margins of victory are favored.

Here's a vote that produces different results under winning votes and margins:

7 votes: A>D 5 votes: B>C 4 votes: C>A 2 votes: D>B

A>B 11-7. C>A 9-7. A>D 11-2. B>C 7-4. D>B 9-5. C=D 9-9. Under ranked pairs-winning votes, A>B and D, then C>A and D>B, so C>A>D>B. Under ranked pairs-margins, the biggest beatdown is A>D by 9, then A>B 11-7 and D>B 9-5 are both wins by 4, so A>D>B. Of the two remaining, 9-7 wins by 2 while the weaker-on-winning-votes 7-4 wins by 3, so A>D>B>C.

Under Kemeny-Young, C>A>D>B includes a 9 from C>A and a 4 from C>B. A>D>B>C swaps out the 9 for a 7 and the 4 for another 7. Note how the margins applies. The first trade subtracted 2 from the score, while the second added 3.

All of which is basically a long-winded way of asking, how is this a different way of calculating ranked pairs under margins? Morgan Wick 02:35, 16 July 2007 (UTC)

One place to look for differences between Ranked Pairs and Kemeny-Young results is in situations in which the results involve three or more choices being tied at the same preference level. I don't know how -- or if -- the Ranked Pairs method produces tied results, so I can't offer any insight there.

As a related point I haven't seen any examples in which the K-Y method violates the independence of clones criterion, yet according to the information in the K-Y characteristics table at least one such case should exist. In contrast, the information in voting systems indicates the Ranked Pairs method does not violate the independence of clones criteria, so such a case would answer your question. VoteFair 20:32, 19 July 2007 (UTC)

[edit] Polynomial runtime

To Markus Schulze: You reverted the entire article even though you are only objecting to one part of one sentence within the new "computing methods" section. Once again I must ask you to please respect the rules of Wikipedia and just change the wording you object to. This isn't the first time you've done a full reversion involving lots of changes even though you object to only one sentence or phrase, so if this persists I will consider contacting the appropriate Wikipedia authorities.

Although you do not know how to identify the winning Kemeny sequence within a polynomial runtime, that does not mean it cannot be done. I have figured out how to do it. Surely you've noticed that the subtitle of my first book is "A Complete Course in the Art of Creating Solutions to Problems of Any Kind." This isn't the first time I've done what "experts" thought was impossible.

Obviously, as stated in the article, it is not necessary to calculate every Kemeny score in order to identify the sequence with the highest score. If you need proof that VoteFair ranking software identifies the sequence with the highest Kemeny score within a polynomial runtime then I can set you up with a survey at VoteFair.org where you can confirm that the calculations for a twelve-choice case--with complex ballot preferences of your choice--are completed within about two seconds. Note that during those two seconds (or less) the software also calculates the results for several other voting methods (Borda count, IRV, VoteFair representation ranking, etc.), translates the results into a dynamic web page, and the computations are done on a server that is shared with other websites. (Note that when the VoteFair.org website is accessed after not having been accessed for awhile, there is a several-second delay while the entire website is loaded from disk into memory connected to a currently available processor. I'm assuming the delay between the United States and Germany is only a fraction of a second.) Note that if all the Kemeny scores were calculated (to find the largest score), a twelve-choice case would require at least several hours of computation time, even on a fast dedicated CPU. VoteFair 05:52, 9 October 2007 (UTC)

Dear Richard, Wikipedia demands reliability. It is not sufficient that you claim that you had a polynomial algorithm to calculate the Kemeny-Young winner, you must also provide reliable sources. Markus Schulze 11:39, 9 October 2007 (UTC)

VoteFair: If you can compute the Kemeny ranking for any number n of candidates, given a vote matrix, in polynomial time, then I suggest you pay more attention to the paper you'll write for the $1 million Clay Institute prize you're eligible to win [2]. The press coverage you'll get will surely suffice for the verifiability Markus Schulze wants. CRGreathouse (t | c) 12:29, 9 October 2007 (UTC)

Alas, I'm not eligible to publish in academic journals because I didn't complete my graduate studies (for a Masters degree in Atmospheric Science, where my development of an innovative way to mathematically model the atmosphere led to software development projects in other areas, including voting). Publishing the polynomial-runtime method elsewhere would lead to someone else getting credit for being the first to publish the solution in an academic journal. A factor that decreases the likelihood of meeting the prize requirements is that the prize appears to be for _all_ P (polynomial) versus NP (non-polynomial) mathematical problems, and the solution I discovered isn't necessarily applicable to all such problems (such as the college-admissions problem on the page to which your link points). I'm open to possibilities, but the academic world appears to be very resistant to outsiders -- as evidenced in Schulze's (academically funded) efforts to weaken the description of the Kemeny-Young method so that "his" self-named Schulze method appears to be better. VoteFair 06:41, 11 October 2007 (UTC)

Solving any NP-hard problem in polynomial time means that any problem in NP can be solved by in polynomial time, by using polytime-reductions with the polynomial solution to this problem as an oracle. I admit I'm quite skeptical of your claim, since this is a major problem -- in my view, possibly one of the top two open problems in all mathematics construed broadly (second only to the Riemann hypothesis).

I agree, though, that everyone has an agenda. Schultze wants to show that his method is the best, the McDougall Trust's "Voting matters" is an STV/IRV advocacy group, Dr. Saari spews propaganda about the supremacy of the Borda count, and Warren Smith writes excellent arguments (with which I do not agree) in favor of range voting. I'm not sure (1) what you propose to do about it, here or broadly, or (2) how that shows that the academic world is resistant to outsiders.

CRGreathouse (t | c) 15:42, 11 October 2007 (UTC)

As far as not being able to publish a paper because you don't have a master's or doctorate: weren't Kayal and Saxena undergraduates when they published the AKS primality test with Agrawal in 2002? For a smaller paper, Nielsen was still in school (working on his master's, I think) when he published his 2003 paper on OPNs.

Also, you wrote: "Note that if all the Kemeny scores were calculated (to find the largest score), a twelve-choice case would require at least several hours of computation time, even on a fast dedicated CPU." This seems slow to me. Perhaps I'll write a program for this and compare times; this should help put things in perspective. Maybe one program for top score and a second for a complete ranking?

CRGreathouse (t | c) 19:10, 11 October 2007 (UTC)

My ego tells me to "go for the prize." My heart and intuition and my desire for fairness tell me to "keep on creating solutions to the big unsolved problems I'm working on." My wallet tells me I'll be better off providing "technical innovations on demand" through my new Fovationz, Inc. venture. Although others may follow their ego, that's not what motivates me. I'll continue to do what my heart, wallet, and intuition tell me to do. Yet I'll also continue reading the 12-page official description of the P vs NP problem and continue imagining translating my software solution into mathematical terms in case an appropriate collaborator comes along. I very much appreciate you telling me about the prize, which I didn't know about (although I knew that what I had done was a subset of solving the P vs NP problem). VoteFair 21:20, 12 October 2007 (UTC)

About the computation time: The software I wrote back in the 1990's computed all the Kemeny scores (when needed), and that was adequate for up to 10 choices. Then the American Idol contest started having 12 choices (12 females and 12 males instead of three groups of 8 each), and I discovered (based on logging the progress and extrapolating the completion time) that the full calculations for 12 choices (and a circular ambiguity in the preferences) were going to consume about 10 to 12 hours on my Pentium 4 processor. (For comparison, 10 choices takes just a few minutes, and the difference is a factor of 12x11=132.) That's when I again attempted to figure out a faster approach. I finally succeeded. And I can tell you it was very, very challenging! The knowledge that it's possible may now make it easier (but not easy) for someone else to figure out, and publish, the solution.

In the meantime, as time allows, I will continue developing a fair method of voting within legislatures, the current limits of which are being revealed by the Iraqi Parliament where the Shiite majority easily outvotes the Sunni and Kurdish minorities. (As for the fair election of representatives to a legislature, my recently published book titled "Ending The Hidden Unfairness In U.S. Elections" explains how to do that, with such elections involving VoteFair representation ranking, which can be thought of as a much fairer form of multi-seat STV.) VoteFair 21:20, 12 October 2007 (UTC)

[edit] Is K-Y NP-complete?

After learning more about the P (polynomial) versus NP (nondeterministic polynomial) problem, I see that—as I originally suspected—my polynomial-runtime method (for calculating the winning Kemeny sequence) does not apply to solving every NP problem in P time. Specifically, the Kemeny problem is not "NP-complete", which is necessary for solving the P versus NP problem.

Viewed another way, in order to solve the P versus NP problem, the problem must be of a type in which a correct answer can be quickly (in P time) verified as correct. But the correctness of a Kemeny solution cannot be confirmed just by calculating one score. (It's irrelevant that any incorrect "Kemeny" sequence can be proved as incorrect just by calculating one score.)

Yes, the Kemeny problem is considered to be NP-hard, but that's not as difficult to solve. In contrast, as far as anyone can tell, any NP-complete problem is impossible to solve. This difference explains why I was able to create a computation method that identifies the winning Kemeny sequence (for all cases) within a polynomial runtime. VoteFair 23:38, 26 October 2007 (UTC)

First, a disclaimer: I have not read a paper proving that determining the K-Y winner is NP-hard, but I believe this to be the case because papers have been written claiming such. I agree with you, VoteFair, that it is not even a priori obvious that the problem is in NP -- but then again it's not obvious that PRIMES is in NP, either, but PRIMES is in NP (as shown by Pratt), and in fact PRIMES is even in P (as shown by APR).

Having said that, your claim is incorrect: solving any NP-hard problem in polynomial time does allow one to solve any NP problem in polynomial time. The brute force method would be through reduction of the NP problem to SAT and oracle queries to the NP-hard problem.

Further, NP-complete problems are not, as you claim, impossible to solve. In fact, even very difficult instances of NP-complete problems can be solved; here are two long optimals TSP tours (10,000-cities and 25,000-cities): [3][4]

In fact, NP-complete problems are the easiest NP-hard problems. 2-EXP-complete problems are NP-hard, but are vastly harder than any problems in NP, NP-complete problems included.

CRGreathouse (t | c) 03:35, 27 October 2007 (UTC)

Dear CRGreathouse, you wrote: "I have not read a paper proving that determining the K-Y winner is NP-hard." In mathematical publications, the Kemeny-Young method is usually known under other names. So if you have some books on combinatorial optimization, then you should look very carefully whether one of the discussed problems could be equivalent to the calculation of the Kemeny-Young winner. For example, in many books the Kemeny-Yound method is called "linear ordering problem" (LOP). Markus Schulze 17:14, 27 October 2007 (UTC)

I have seen a paper that referred to the Feedback Arc Set problem and mentioned that it was equivalent to finding the K-Y winner. But I didn't really read that paper, just skimmed it. I didn't want to wrongly claim knowledge I didn't have.

Of course if you have a reference handy I might read it just so I could better discuss the issue. CRGreathouse (t | c) 15:34, 28 October 2007 (UTC)

First off, I have read most of this discussion page, and I would like to say that my hat is off you guys for the hard work that has been put into this page.

To FairVote, do you still believe that you have a polynomial time algorithm to compute the optimal Kemeny ranking?

Bender2k14 (talk) 07:43, 7 December 2007 (UTC)

[edit] Runtime section

Markus wrote:

Deleted confusing section. It is not true that the runtime of the Kemeny-Young method was super-polynomial only when all sequence scores were calculated.

It wasn't my intent to give that impression. My understanding is that the only superpolynomial runtimes are known and that any polynomial algorithm would prove that P = NP. But there are still efficient algorithms, just like the simplex method is an efficient (but still exponential) algorithm. Of course the simplex algorithm solves a problem in P, but still...

While admitting that the runtime of a voting system isn't usually considered a major characteristic, is there a good reason to remove the section entirely?

CRGreathouse (t | c) 17:07, 27 October 2007 (UTC)

Well, the section was completely confusing. It said:

Calculating all sequence scores requires time proportional to N!, where N is the number of choices. This is significantly more time than required for most other voting methods. This calculation time is superpolynomial in the number of choices, so it does not meet the polynomial runtime criteria. Not every sequence score needs to be calculated to identify the Kemeny ranking. Fast calculation methods, including those based on linear programming, allow the computation of the Kemeny ranking for as many as 40 choices.

The problem is not that this calculation time is superpolynomial. The problem is that every known algorithm to calculate the Kemeny-Young winner is superpolynomial. The fact that not every sequence score needs to be calculated to identify the Kemeny ranking doesn't change the fact that there is no known polynomial algorithm. Markus Schulze 17:24, 27 October 2007 (UTC)

I agree. We can say that the naive calculation method takes O(n!) time, and that all known methods are superpolynomial. We can't say that all known methods take O(n!) time (not true: O(2ⁿ) is easily possible, and I suspect O(2^n/2) is possible) or that all possible times are superpolynomial (this would prove P ≠ NP).

CRGreathouse (t | c) 17:59, 27 October 2007 (UTC)

I recommend the following formulation: "There is no polynomial algorithm to calculate the winner of the Kemeny-Young method (unless P=NP)." Markus Schulze 10:14, 28 October 2007 (UTC)

That's fine, but I'd want more information than just that sentence. CRGreathouse (t | c) 15:35, 28 October 2007 (UTC)

I've edited the section to meet the desires you both have. VoteFair 19:24, 28 October 2007 (UTC)

To Schulze: Why do you repeatedly remove the "calculation methods" section when you have never expressed any disbelief that there are multiple ways to calculate the Kemeny sequence? The article even contains a journal reference that states that not all sequence scores need to be calculated. When you object to the wording in a new section, PLEASE follow Wikipedia rules and edit the objectionable wording instead of entirely removing the section. Thank you. VoteFair 19:24, 28 October 2007 (UTC)

Actually, I didn't see that explicitly in the article -- although certainly I agree that calculating all of the sequence scores is not needed. CRGreathouse (t | c) 20:26, 28 October 2007 (UTC)

(de-indent) Alright, I edited the paragraph again. Here are my changes:

• Removed the line "The calculation time can be reduced by not calculating scores for sequences that are clearly not the winning sequence." This is certainly not in the reference linked -- and I've never seen this claim in print. All fast calculation methods I've seen (and I note that I've never seen User:VoteFair's method) simply avoid using "sequence scores" entirely.
• Re-added the table entry. I'm not sure why VoteFair keeps removing it, but it seems appropriate for the table. I'm not terribly attached to it, nor do I like the term "polynomial runtime criteria" (should be criterion, anyway) used to describe it, but I certainly prefer it to having the sentence "This calculation time is superpolynomial in the number of choices, so it does not meet the polynomial runtime criteria." to which I object for a variety of reasons.
• Strengthened "there is no known polynomial-time algorithm" to "any algorithm finding the winner requires superpolynomial time (unless P=NP).". It's not that there's one just out there for us to find, but that if one is found athe major problem in theoretical computer science will be solved.

Comments and improvements, as always, are welcome.

CRGreathouse (t | c) 20:50, 28 October 2007 (UTC)

Your wording in the Calculation Methods is acceptable. It clarifies (contrary to what Schulze wants to imply) that the calculation time is not an issue in real-life voting situations. (Having a preferential ballot with 40 or more choices would be impractical.) At a future time, when a polynomial-time calculation method has been published in a peer-reviewed journal, we can make corrections.

The reason I removed the runtime criterion from the table is that the table describes the characteristics of the Kemeny results, which are not affected by how the winning sequence is identified. Since both of you want the redundancy, I'll go along with your desires.

To CRGreathouse: Thank you so much for your involvement in these edits. I greatly appreciate your fairness and your lack of bias. Thanks!

VoteFair 20:32, 29 October 2007 (UTC)

I did intend to show that K-Y voting was practical for real-life voting, as indeed it is. I intend to write a program myself that will calculate K-Y winners (along with a boatload of other data, like Shapley value, the core, bargaining points, etc.) to see, firthand, how difficult it is. But as to practical -- if a 40-candidate election is practical, there should be no real troubles in real political elections. (Sometimes it's desirable to run certain automatic processes, like web page ranking, as 'elections' in which case thousands of 'candidates' could be typical. In these cases good approximations to Kemeny's method are probably all that could be hoped for.)

CRGreathouse (t | c) 13:09, 30 October 2007 (UTC)

Dear VoteFair, you wrote: "The characteristics of the Kemeny results are not affected by how the winning sequence is identified." That's exactly what I always tried to explain to you. The fact, that the calculation of the Kemeny-Young winner is NP-hard, is a characteristic of the Kemeny-Young method and not of the used algorithm. Markus Schulze 20:56, 29 October 2007 (UTC)

Huh? Perhaps you misunderstood my words "Kemeny results". Kemeny results refers to the ranking RESULTS (which choice is ranked first, which is second, etc.), rather than which way those Kemeny ranking results are calculated. Stated another way, there is more than one way to calculate the results for "your" Schulze method (as you point out in Talk:Schulze method), yet the results are the same (regardless of which way they are calculated). VoteFair 23:28, 29 October 2007 (UTC)

Good, we all agree. Let's form a circle and sing Kum Ba Yah. CRGreathouse (t | c) 13:06, 30 October 2007 (UTC)

VoteFair: I've tried to be as fair as possible in working with this and other contentious edits. I have to say I like working on this article with the two of you because even though we seem to have little that we agree on we all work together to improve the article. I wish we had half as much agreement over at Hugo Chavez as we have here.

Markus: Thank you as well for bearing with us; I appreciate you lending your expertise.

CRGreathouse (t | c) 13:06, 30 October 2007 (UTC)

[edit] Some modifications

I have deleted the following sentence: "In 1991 Richard Fobes independently rediscovered the method, calling it 'VoteFair popularity ranking'." The reason: In 1991, the Kemeny-Young method was already well known so that it is rather improbable that Fobes discovered this method independently.

I have deleted the long excerpt from Fobes' book because of the following reasons: (a) This was blatant advertising for Fobes' book. Whatever Fobes wanted to say, he could say this without posting such a long verbatim excerpt from his book. (b) That part of Fobes' book that is available via the Internet shows that Fobes' book is not a scientific book, but only an advertising brochure for the Kemeny-Young method [5]. (c) The excerpt didn't give additional insight into the Kemeny-Young method.

I have deleted the following sentence: "In the VoteFair variation, each sequence score equals the sum of the pairwise counts that apply to the sequence, and the sequence with the highest score is identified as the overall ranking, from most popular to least popular. The original Kemeny method uses pairwise counts of voters who oppose each pairwise order, and the lowest sequence score is identified." The reason: When you calculate the scores, it makes no difference whether you use the number of voters who agree or the number of voters who oppose. Markus Schulze 15:23, 6 November 2007 (UTC)

To Schulze: It's clear that you are impressed by the fairness of the Kemeny-Young method or else you wouldn't be trying to push aside my contributions to the method. (You would just ignore this article.) It's ironic that you believe that I'm promoting my books when, as you stated, what I promote is the calculation method. (Don't you see the irony of your accusation inasmuch as you use your academically funded time to promote "your" Schulze method?) I prefer to state the facts (all the facts) and let others make their own judgments.

The facts about the K-Y method include my contributions, which include a published--and therefore academically important--description of the method in my book titled "Ending The Hidden Unfairness In U.S. Elections." The book uses the name VoteFair popularity ranking because I've been using that name long before I learned that part of VoteFair ranking is mathematically equivalent to what is academically known as the Kemeny-Young method. It's true that I write in a clear, easy-to-understand style rather than using an academic writing style, but contrary to your claim, the book does explain lots about what here is known as the Kemeny-Young method.

Before you again contend that the name "VoteFair popularity ranking" should not be used in this article, notice that this usage is the same as the introduction of many voting articles--including the Schulze method--that indicate well-known alternative names--such as "beatpath" being an alternative name for the Schulze method. Also your claim that it's unlikely that I could have independently created an equivalent method overlooks the fact that I'm an internationally known expert in creative problem solving, and that I have a degree in Physics that proves I'm adept at mathematics.

You've made edits in areas of this article that could be improved, so I've done so. The long "legaleze" wording you removed was inserted long ago, before there were any examples in this article, so that part of its purpose is no longer needed. Yet (contrary to your desires) some people will be interested in knowing how to word their organization's rules to describe the method, so I've added an external link to the removed wording. (Of course you removed it because you don't want the method used in organizations, but it's too late for that.)

I've moved the historic information to a new "History" section that explains the "historical" relationship between the original Kemeny method and VoteFair popularity ranking.

Thank you for helping make this a stronger article. VoteFair 21:30, 7 November 2007 (UTC)

Dear Richard Fobes, Wikipedia demands reliability.

When you claimed that you had found a polynomial algorithm to calculate the Kemeny-Young winner and I asked you for a reliable source, you only replied arrogantly: "Although you do not know how to identify the winning Kemeny sequence within a polynomial runtime, that does not mean it cannot be done."

When you claimed that there was an "increasing use of the Kemeny-Young method" and I asked you for a concrete example, you only replied arrogantly: "Your lack of knowledge about the use of the Kemeny-Young method does not constitute a lack of use."

The problem is not that you try to "impress the readers by the fairness of the Kemeny-Young method". The problem is that you use untrue assertions to impress them. Markus Schulze 14:02, 8 November 2007 (UTC)

Taken out of context I can see that these two quotes might seem arrogant to someone who doesn't know me. Simply out of context these comments might seem insulting, and for that I apologize. As for the context, you aren't understanding that something can be true and yet not supported with proof.

Of course, as you point out, proof is needed for assertions in Wikipedia. I have adhered to that rule! (There was one accidental exception when I mistakenly used the wrong definition for a term, but that was corrected long ago.) The two issues you bring up here are both worded with statements that are both true and supported. VoteFair 23:40, 9 November 2007 (UTC)

[edit] Reliable sources

The content in this article about "VoteFair" has no reliable, independent sources, only things written by Richard Fobes himself. I am removing them.

Richard, please be aware of the conflict of interest policy. You should not re-add material that promotes you when that material is disputed. rspeer / ɹəədsɹ 22:28, 8 November 2007 (UTC)

I did not add my name--Richard Fobes--to this article. My name was added by CRGreathouse--without any suggestion from me that it be added. Clearly the addition of my name--by someone else--is not a conflict of interest.

As required in the [conflict of interest] policy, I have disclosed that I have "a close connection with [the] subject". Furthermore I have taken "great care not to edit in a manner that may be perceived as controversial, promotional or agenda-driven".

As for why my name was added to this article, note that prior to my involvement:

* The Kemeny-Young method was mistakenly categorized as a non-Condorcet method.

* The Kemeny method was always described as using an inverse scoring method, in contrast to the method (still) described in this article. The difference is neutrally stated in part of what you removed.

* The below-mentioned book was published prior to the Kemeny-Young method being described in Wikipedia, or anywhere else on the Internet that I could find, aside from four brief and ambiguous sentences that did not explain the method. Much of what appears in this article I wrote as the beginning of a description of VoteFair ranking and Schulze commandeered the article as a description of the Kemeny-Young method.

As for why VoteFair popularity ranking is named in the article, note that VoteFair ranking software was the first readily accessible software to calculate Kemeny-Young results, and it is still the only publicly accessible software that calculates Kemeny-Young results.

My book titled "Ending The Hidden Unfairness In U.S. Elections" describes VoteFair popularity ranking, and you can use this link (referred to above by Schulze) to verify that the book's description of VoteFair popularity ranking matches what is mathematically equivalent to the Kemeny-Young method. (Part of what you removed explains the difference.)

As additional proof that VoteFair popularity ranking results are mathematically equivalent to the Kemeny-Young method, every results page produced at www.FullRanking.com and www.VoteFair.org (whose links you removed) provides numeric details that identify which pairwise comparisons add up to produce the largest Kemeny score, the winning score is presented, and that score can be validated as being the largest score.

Am I right in guessing that Schulze has enlisted your assistance in making this edit? If so, that is a conflict of interest. Schulze has too often reverted this entire article even when he objects to only a few words in the changed version.

Schulze has a clear conflict of interest because he wants to downplay the benefits of the closest competitor to his self-named Schulze method. Until you clarify otherwise, I am assuming that you have a conflict of interest of your own.

For a neutral perspective, please ask CRGreathouse. You should consulted here before you obliterated the improvements the three of us (CRGreathouse, Schulze, and I) have been negotiating on this talk page.

If I were not allowed to edit this article then, by the same logic, Schulze would not be allowed to edit the Schulze method article. He edits that page as if it were his, unlike the neutral way in which I edit this page. And if you were to try to remove his name I can assure you he would directly or indirectly restore his name to the article. As for the referenced published information about the Schulze method, note that Schulze is the author of those writings.

My point is that Wikipedia demands neutrality and I have observed that rule in all the statements made in this article.

In the meantime, unless CRGreathouse agrees with your recent reversion, I'm restoring the article to what the three of us (CRGreathouse, Schulze, and I) had negotiated prior to your arrival. VoteFair 00:56, 10 November 2007 (UTC)

I think that Rspeer was called in to mediate between VoteFair and Markus Schulze. I don't have any reason to think he's less neutral than I am. But I for one would be happy with more eyes on this page -- so if you want to bring someone else in, VoteFair, feel free to do so.

Unfortunately I'm a WP:0RR devotee, and with the bad taste in my mouth from revert wars in Hugo Chavez I'd really like to avoid such a conflict here. I'm more likely to sneak in improvements between the worst of the edit warring than directly intervene.

I do feel that both Schulze and VoteFair have WP:COI issues to work with in voting articles, but I'll have to trust that they will act as gentlemen in this regard.

CRGreathouse (t | c) 02:55, 10 November 2007 (UTC)

Look, the whole reason I did this is because of reliable sources, one of the core policies of Wikipedia. In your lengthy response, VoteFair, you have not provided a single reliable source. I don't care about the politics behind how it got this way, but we can't have content on Wikipedia that has no reliable sources.

If there are factual inaccuracies in the version of the article that is not about VoteFair, then fix them (with sources, of course!) But your claims about how you thought of things first, put things on the Internet first, or implemented things slightly differently, simply have no bearing on the issue.

By the way, reverting to a version that promotes you is "controversial", to say the least, so it is a conflict of interest. rspeer / ɹəədsɹ 09:16, 10 November 2007 (UTC)

Dear Richard Fobes, you inserted the following sentence to the Kemeny-Young method article:

The original Kemeny method uses scores based on counts of how many voters oppose each pairwise preference and the sequence with the lowest score determines the Kemeny ranking sequence. This article uses the VoteFair convention in which the scores are based on counts of how many voters support each pairwise preference and the sequence with the highest score determines the result.

It is absolutely the same whether you use the number of voters who support and then you maximize the score or whether you use the number of voters who oppose and then you minimize the score. Therefore, this sentence should be removed. I believe that the only reason, why you insist that we should differ stricly between these two definitions of the Kemeny score, is that you try to make the readers mistakenly believe that you had invented a new variation of the Kemeny-Young method, the "VoteFair popularity ranking method". Markus Schulze 15:13, 10 November 2007 (UTC)

[edit] Is Kemeny-Young even in NP?

I'm questioning the article's assertion that the Kemeny-Young method can be calculated in NP time. (Remember that NP means "nondeterministic polynomial", not "exponential".) It's intuitively plausible, but I don't see a reference for it. This assertion is implied by the qualifier "unless P=NP". But it's also possible that Kemeny-Young is harder than NP, and would require superpolynomial time regardless of whether P=NP.

To back up this statement, we'd need a reliable source with a proof that either a nondeterministic computer can calculate Kemeny-Young in polynomial time, or that a standard computer can verify the result of a Kemeny-Young election in polynomial time (those are equivalent).

In the absence of such a source, the best way to describe the complexity would be "There is no known algorithm that calculates the result of a Kemeny-Young election in polynomial time."

rspeer / ɹəədsɹ 21:49, 9 November 2007 (UTC)

I ordered (via interlibrary loan) the paper "Voting schemes for which it can be difficult to tell who won the election" a few days ago. This may shed some light on the matter. But regardless, the statement "any algorithm finding the winner requires superpolynomial time (unless P=NP)" is true: if P ≠ NP then all K-Y algorithms take superpolynomial time. The statement is neutral on the issue of P = NP -- it doesn't clai8m that in that case there is a polynomial algorithm for it.

If you'd like to research this, perhaps you can find "Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP" (1997: Hemaspaandra, Hemaspaandra, and Rothe). This may shed light on the issue.

CRGreathouse (t | c) 21:59, 9 November 2007 (UTC)

If it doesn't depend on whether P=NP, the clarification "(unless P=NP)" is misleading. I think it would be better to talk only about known algorithms, so if we don't know whether Kemeny-Young is in NP, we shouldn't bring it up. If we do know it, we should mention it more clearly.

I'll try looking into the paper about Dodgson and NP sometime. I assume this isn't the sum-of-defeats method we know as Dodgson's method, since that has an obvious polynomial-time algorithm. rspeer / ɹəədsɹ 22:18, 9 November 2007 (UTC)

Dear Rob, in the mathematical literature, the Kemeny-Young method is usually called "linear ordering problem" (LOP). I guess that you will find more reliable sources on possible implementations, when you search for the term "linear ordering problem" rather than for the term "Kemeny-Young method". Markus Schulze 22:09, 9 November 2007 (UTC)

Rspeer, I'm fairly sure K-Y is in FNP, but I'll not add anything to that effect until I have a decent citation. I can't answer questions about the paper I suggested since I just pulled it from the references from another paper -- if I had read this paper, I wouldn't need to ask you to read it. :) CRGreathouse (t | c) 02:41, 10 November 2007 (UTC)

OK, I have the paper, which does talk about Kemeny-Young in addition to Dodgson. It proves that the decision problem "Is the Kemeny score of candidate c less than or equal to K?" is NP-complete (by a reduction to the feedback arc set problem) and that the decision problem "Is candidate c a Kemeny winner?" is NP-hard. It unfortunately does not address the question of whether the latter is in NP; the proof is simply by padding with candidates, using the NP-completeness result, and so does not show that the question is outside of NP, but does not show it to be inside either.

The author notes that Orlin and Wakabayashi have previously proved results relating to the hardness of the Kemeny method. The former is listed as "(private correspondance)" and the latter is a Ph.D thesis. It looks like Wakabayashi did publish more on it later, under the name "median problem", a generalization beyond social choice. I'll try to look into this.

CRGreathouse (t | c) 14:50, 15 November 2007 (UTC)

Further research shows that it's complete for Θ₂P = P^∥NP = P^NP[log]. Unfortunately it's an open question as far as I know whether these classes are distinct from NP or not. The more I read the less I know. CRGreathouse (t | c) 16:32, 15 November 2007 (UTC)

[edit] Schulze conflict of interest

To Rspeer: Markus Schulze has mislead you as to the nature of the conflict here. I found on User_talk:Rspeer that Schulze wrote: "This conflict is about whether Fobes should be listed as an independent inventor of the Kemeny-Young method." That is not the issue.

The real issue is that Schulze wants to eliminate any mention of VoteFair ranking (or VoteFair popularity ranking) because he doesn't want people to know that Kemeny-Young results can be calculated (for free) at VoteFair.org and FullRanking.com. This is a conflict of interest based on his desire to downplay competition for "his" Schulze method.

Something important that Schulze failed to mention is that the VoteFair ranking page ([6]) redirects here. More than a year ago Schulze tried to get that page deleted, but another contributor pointed out that Internet search results revealed that there were significantly more matches for "VoteFair" than for "Kemeny-Young". That page still redirects here. Schulze's failure to inform you of this important fact reveals that he is not being straightforward in his claims that the VoteFair references should be removed.

As I've already said, I did not add my name to the Kemeny-Young article; someone else did that. Although I like the fact that someone added my name, I am fine with my name not being mentioned in this article. Months ago Schulze and CRGreathouse and I had already revised the wording regarding my having independently conceived of what I call VoteFair popularly ranking, and Schulze did not object to that compromise, yet now he wants to use that as an excuse to eliminate all VoteFair references.

Recently Schulze removed all the VoteFair references that had been in the article from its beginning more than a year ago, and then I restored the historical information into a new "history" section, continuing to use the same consensus-approved wording about the connection to VoteFair ranking. (Previously the historical information had been growing within the introduction.) Since you joined in at that point, you apparently got the mistaken impression that I had recently added that text. Your recent statement that you removed the "addition of large quantities of unreferenced content" suggests this misunderstanding. Instead, Schulze (once again) is trying to remove all VoteFair references. He has repeatedly attempted to use a minor wording issue as an excuse to make such major removals.

Schulze has never expressed any doubt that VoteFair representation ranking and the Kemeny-Young method produce the same results. In fact Schulze repeatedly claims they are the same. Yet he implies to you that there are no published references that support their equivalence. The reference you/Rspeer removed, "Ending The Hidden Unfairness In U.S. Elections" (pages of which can be viewed at Google Books), describes VoteFair popularity ranking, and Schulze has claimed from that and other information that the methods are mathematically equivalent.

If you are in any doubt about what is really going on, please ask CRGreathouse. He has been neutrally facilitating the edits on the Kemeny-Young page. As he points out, he prefers not to get involved in reversions, which is a wise choice. Nevertheless he has helpfully spoken up here on the discussion page many times, and can give you an unbiased perspective.

Schulze suggests that he is bothered that the Kemeny-Young method can have more than one name. Yet as you/Rspeer know from your involvement with other Wikipedia voting articles, many voting concepts have alternate names or aliases. (For example, a "preferential" ballot is the same as an "ordinal" ballot, "first-past-the-post" is the same as "plurality" voting, and "instant runoff voting" is called the "single alternative vote" and many other names.) Note that the sentence you/Rspeer removed from the introduction -- 'The Kemeny-Young method is also known as VoteFair popularity ranking '-- uses the wording I got from the Schulze method (which says 'The Schulze method is also known as Schwartz Sequential Dropping (SSD), Cloneproof Schwartz Sequential Dropping (CSSD), Beatpath Method, Beatpath Winner, Path Voting, and Path Winner.'), so clearly aliases belong in Wikipedia voting articles. (Presumably Schulze doesn't like those aliases either.)

We can easily reword the history section to clarify that a portion of VoteFair ranking produces the same results as the Kemeny-Young method, but Schulze has not requested such a wording change. He insists (in spite of his conflict of interest) that there be no mention of VoteFair ranking at all.

Schulze even wants to remove the statement that there are two different ways to calculate Kemeny-Young results, one of which seeks a maximum Kemeny score and the other seeks a minimum Kemeny score. Yet this fact is very important because there are online references, including one on the Schulze method page, about seeking a maximum Kemeny score, yet the academically published references explain the calculation method that seeks a minimum score. This clarification can be reworded without using the word VoteFair, but Schulze never asked for it to be reworded, he just wants it entirely removed.

Here in Wikipedia, the academic world and the real/non-academic world intersect, so it's important to clarify links between the two worlds. Specifically every reasonable reader of this online encyclopedia would expect this article to include not just academic information but also information about real-world software that calculates voting results that match Kemeny-Young results. Only Schulze's conflict of interest accounts for his desire to remove the VoteFair references.

I see that you are a Wikipedia administrator so I am requesting that you/Rspeer either revert the article to restore the VoteFair references that Schulze recently removed, or allow me (or CRGreathouse) to restore the information you and Schulze have removed. Then, with your assistance, we can refine the wordings that Schulze actually objects to.

From your user page I see that you embrace neutrality in your moderations, so in advance I thank you for your help in moderating Schulze's overzealous desire to eliminate evidence about real-world voting methods that compete with "his" Schulze method. VoteFair 06:53, 12 November 2007 (UTC)

Dear Richard Fobes, I checked the archives and found that it was you who added the claim that you invented the Kemeny-Young method. On 3 June 2006, you added the claim that your book "contains the first published description of VoteFair ranking" [7]. Markus Schulze 12:09, 12 November 2007 (UTC)

Richard, all the information about VoteFair you mention should be removed, because it is not attributable to a reliable source. The honest truth is that nobody cares where Kemeny-Young results can be calculated for free, and it is not Wikipedia's job to advertise that to people. Your bizarre theories about Markus trying to suppress your software are first of all quite unconvincing, and second of all have nothing to do with the requirement for reliable sources. Please stop bringing up irrelevant side issues about who edited what when, and please stop trying to shift the blame to Markus Schulze when you cannot follow the policies of Wikipedia.

I am disappointed that CRGreathouse allowed you to put the article into the state you prefer. The policies of Wikipedia shouldn't be something to compromise and negotiate over. rspeer / ɹəədsɹ 16:43, 12 November 2007 (UTC)

To Rspeer and Schulze: Apparently I tried to cover too many issues at once, so let's get to the main point.

I am requesting approval from Rspeer (as a Wikipedia administrator) to restore the sentence that says "The Kemeny-Young method is also known as VoteFair popularity ranking." Of course that needs a published reference, and here are some:

The description of VoteFair popularity ranking appears in 10 published editions of "The Creative Problem Solver's Toolbox" -- under different titles for each edition, which includes editions in Chinese, Korean, Indonesian, English for India, English for Southeast Asia, Polish, Russian, Czech, and Spanish. Inasmuch as we are in the English-language edition of Wikipedia, the three English editions published in the U.S., Singapore, and India are the most relevant. I recommend that a footnote refer to the U.S. edition, which is in the content that Schulze removed.

The description of VoteFair popularity ranking also appears in "Ending The Hidden Unfairness In U.S. Elections," and I recommend adding that as a second footnoted reference proving that VoteFair popularity ranking is equivalent to the Kemeny-Young calculation method described here.

If you feel that two references are excessive, feel free to pick either one.

Keep in mind that VoteFair ranking is well-known throughout the Internet (and has been since long before this article appeared), and an encyclopedic entry that fails to mention the equivalence weakens the credibility of Wikipedia as relevant to the real world.

Notice that Schulze does not dispute the fact that VoteFair popularity ranking produces the same results as the Kemeny-Young method, so please don't get distracted by his other issues.

Remember that the Wikipedia entry "VoteFair ranking" redirects here, so of course the mention of VoteFair popularity ranking is appropriate to clarify the connection.

(Notice that I'm not asking to be credited in the history section, which was a distraction from the real issue of Schulze's objections to VoteFair references.)

I agree that you should be vigilant against the many self-promoting people who attempt to promote agendas that are not in line with encyclopedic content, yet in this case the equivalence of VoteFair popularity ranking and the Kemeny-Young method is true, relevant, and fully supported. VoteFair 20:47, 12 November 2007 (UTC)

• Sorry, no, that's not a reliable source. "The Creative Problem Solver's Toolbox" was written by you and apparently self-published. rspeer / ɹəədsɹ 21:24, 12 November 2007 (UTC)

I do seem to remember VoteFair getting a lot of Google hits -- I think it once had more than Kemeny-Young itself. VoteFair, do you know of any third-party references to your system? Those might help, if there are any.

I don't think anyone disputes that the two are the same (you say "produces the same results") as voting systems. CRGreathouse (t | c) 03:27, 13 November 2007 (UTC)

Try this search to find ones that Richard himself is not responsible for: votefair -richard -fobes -"solutions through innovation" -wikipedia -"ranking service that calculates". It gets only 21 unique hits, and not all of them are meaningful. rspeer / ɹəədsɹ 03:50, 13 November 2007 (UTC)

One person who has read "Ending The Hidden Unfairness In U.S. Elections" has a web page at [8] where he recommends my VoteFair.org website with the words: "A website that seems to have figured out the fairest way of counting preferential votes. I haven't found a better site on this subject." If it becomes necessary I can ask him to sign up as a Wikipedia user and add the missing sentence to this article, but that seems silly since all three of you (Rspeer, Schulze, and CRGreathouse) agree that VoteFair popularity ranking and the Kemeny-Young method are equivalent.

Note that any three of you can add the missing sentence about "VoteFair popularly ranking" being an alias. The fact that the book is self-published would only be an issue if I, as the author, were the one adding the reference, correct? (If self-publication were an issue, there are foreign translations of "The Creative Problem Solver's Toolbox" that are not self-published and that describe the method.)

Do we have agreement that CRGreathouse can add the sentence about the alias? I can supply you/CRGreathouse with a free copy of the book, or you may be able to download the online PDF portion (19MB). Chapter 12, which begins on page 237, describes VoteFair popularity ranking. It will be easy to see that the described method matches the method described on this Kemeny-Young page.

If this approach is not acceptable, there are other possibilities, but first I want to find out if this approach is acceptable. VoteFair 06:54, 13 November 2007 (UTC)

This would not be acceptable. Unless the book gained some source of authoritativeness as it was translated -- for instance, if it were peer-reviewed in another language, or if it were printed by a significant publisher (the kind that expects to make a profit by selling the book, not by being paid to print it) -- then it's not a reliable source, and thus there are no reliable sources that call the Kemeny-Young method "VoteFair". Also, you're playing with Wikipedia rules. It doesn't make a conflict of interest go away if you get someone else to add something for you. rspeer / ɹəədsɹ 08:28, 13 November 2007 (UTC)

OK, that criteria disqualifies one of the two books, namely "Ending The Hidden Unfairness In U.S. Elections."

The other book that describes VoteFair popularity ranking--"The Creative Problem Solver's Toolbox"--does qualify as a heavily peer-reviewed reference. Although the U.S. edition of it is self-published, every one of the other 9 editions that contain the VoteFair popularity ranking description--including the editions in Chinese, Korean, Indonesian, English for India, English for Southeast Asia, Polish, Russian, Czech, and Spanish--are each published by a different established publisher. This means the book was carefully reviewed by editors before each publisher negotiated a contract and paid me for the right to publish it in their language or region. Furthermore, the cost of translating the book into each foreign language was paid by that foreign publisher. These costs were paid based on a clear expectation of profitability by established businesses. Obviously the book was carefully reviewed before each publisher chose to publish their edition of the book known in the U.S. as "The Creative Problem Solver's Toolbox."

There is even credibility for the self-published U.S. edition because it has been used as a required textbook in classes at several colleges and universities.

Surely "The Creative Problem Solver's Toolbox" qualifies as an acceptable reference, right? VoteFair 21:43, 13 November 2007 (UTC)

Okay, that's not what I expected. I'll take your word for it that the book was taken up by major publishers. CRGreathouse has also talked to me and explained what he's looking for in the article. Given this, I would be okay with a few mentions of VoteFair:

• Adding CRGreathouse's suggested wording to the intro: "Since 1991, this method has been promoted by Richard Fobes under the name VoteFair ranking." (CRGreathouse had a wikilink to User:VoteFair in there, but that would be a self-reference, which Wikipedia is supposed to avoid.)
• Referencing that statement with "The Creative Problem Solver's Toolbox".
• Having VoteFair.org be an external link -- if we're mentioning VoteFair, then it is relevant.

On the other hand, I don't want to restore claims of "independent discovery" (it could be true, but there's no way to state it reliably) or details about how VoteFair is implemented or described.

I think you'll find this plan acceptable, based on what you've said, so I'm going to make these changes. rspeer / ɹəədsɹ 00:28, 14 November 2007 (UTC)

(de-indent) That's acceptable to me. I agree on the "independent discovery" line: I don't doubt it, but including it in the article opens up a big can of worms.

Also, credit where due: that line, including its link, is from Markus. [9]

CRGreathouse (t | c) 02:03, 14 November 2007 (UTC)

Thank you, Rspeer, for restoring the very relevant VoteFair information to this Kemeny-Young article! Your resolution is quite acceptable.

Although I'm a little flattered that my name appears in the introduction, I actually think my name and the year 1991 belong down in the "History" section, below where the names of Kemeny and Young appear. So I propose using the following sentence in the introduction ...

The Kemeny-Young method is also known as VoteFair popularity ranking.

... and then putting your existing introductory wording into the "History" section ...

Since 1991 this method has been promoted by Richard Fobes under the name VoteFair ranking.[ref]

... and of course the link to VoteFair.org would remain as-is (restored).

If, for consistency, you want the introductory reference to say "VoteFair ranking" instead of "VoteFair popularity ranking," that's acceptable. (In case you care, while writing the "Ending the Hidden Unfairness in U.S. Elections" book I created a voting method for multi-seat elections called "VoteFair representation ranking" and a voting method for ranking political parties called "VoteFair party ranking" and a PR-related voting method, so I expanded the term "VoteFair ranking" to include all these variations, which use VoteFair popularity ranking at their core.)

If you want to adjust the words "is also known as" to something else, that's fine; I'm just suggesting what Schulze uses on "his" Schulze method page.

Thank you so much (!) for finally resolving this conflict between Schulze and I. VoteFair 02:45, 14 November 2007 (UTC)

You're right that the History section is a better place for that sentence. I moved it, and worked "VoteFair ranking" into the list of names in the intro Markus gave. rspeer / ɹəədsɹ 15:31, 14 November 2007 (UTC)

[edit] Characteristics

The table in the "Characteristics" section is problematic. To the ordinary reader it isn't clear whether, in those cases where the Kemeny-Young method violates a given criterion, the column "Description" says what it means to satisfy this criterion or what it means to violate this criterion. Actually, in the rows "Independence of irrelevant alternatives" and "Polynomial runtime", the column "Description" says what it means to satisfy this criterion. And in the rows "Consistency", "Independence of clones", "Invulnerability to burying", "Later-no-harm", "Invulnerability to compromising", "Invulnerability to push-over", "Participation", and "Schwartz", the column "Description" says what it means to violate this criterion. I recommend that the table should be replaced by a linear text. Markus Schulze 16:25, 16 November 2007 (UTC)

Actually I was going to post the same complaint, and suggest standardizing the table. I tend to think that a table is easier to read, especially with so many criteria. CRGreathouse (t | c) 18:48, 16 November 2007 (UTC)

Thank you Schulze for identifying which descriptions in the "characteristics" table are inconsistent.

Before I edit the descriptions in the table to make them consistent, only to see them entirely removed by Schulze as he prefers, let's get some agreement about whether to maintain the table format.

I wrote the descriptions in this "characteristics" table because the Wikipedia descriptions of most of these criteria elsewhere in Wikipedia, including their defining articles, are not clear. In particular, most of those articles have no clear and brief (single-sentence) description presented in the introduction. In the meantime that situation has improved in the Voting systems article, but only for some of the criteria.

If there were clear explanations elsewhere, as there are here, then we could do as Schulze suggests (and does in Schulze method), namely we could list the satisfied and failed criteria in a "linear text."

If the descriptions remain, I agree with CRGreathouse that the table format is much easier to follow.

Ideally the descriptions of the criteria in the articles where they are explained should be improved. I would be happy to see some of these explanations moved to where they should have been in the first place, namely where each criteria is described. However, I realize this approach may be overly ambitious and/or impractical.

Another alternative is to move some of the corrected (consistent) descriptions into a higher-level article (but which one?) and then this Kemeny-Young article can refer to the appropriate section of that article (because the descriptions will no longer be needed here).

I suspect that Schulze regards the existing descriptions (outside this K-Y article) to be adequate, but I don't know how other voting-method contributors feel about the quality of the brief descriptions in the introductions of those articles. Yet with Rspeer involved (thank you!) it's worth mentioning as a possibility.

What approach would be best? VoteFair (talk) 02:17, 17 November 2007 (UTC)

For the time being I have updated the table to make it consistent. If the table is deleted later, no harm done. But I don't see a good reason to delete the table -- it seems informative and useful. I'd prefer to halve the election walkthroughs here (and on pages like Schulze method which has something like a dozen tally tables) before removing the tables; the examples seem excessive and at least as redundant as the information rehashed in the table.

But I'd be curious to see what Rspeer thinks. Also, it might be useful to get the opinion of someone not familiar with voting theory -- maybe what's obvious to all of us isn't so obvious to general readers. Perhaps the examples that I feel are excessive are needed just to communicate the method, who knows?

CRGreathouse (t | c) 04:15, 17 November 2007 (UTC)

From a stylistic point of view, I find the table totally unnecessary. A definition list would do much better -- in fact, this is exactly what definition lists are meant for.

A definition list

is written like this.

You alternate terms

and definitions.

I'd suggest conveying the "yes" and "no" answers by breaking it up into sections for satisfied and unsatisfied criteria.

The list also suffers from the same problem that most sections about voting criteria suffer from: an utter lack of references. Even in the main criteria table on Voting system, entries flip back and forth without references to back them up. I think that this is the most important thing to fix about voting system articles.

Making the table consistent was a good move. It gives us something to work from. And if the definitions of criteria come from well-referenced articles, there's no reason they need to be removed. When we have disagreement between this article and others on how to define a criterion, we should choose a definition and back it up with sources... a lengthy task, I realize.

However, any criteria which only appear in mailing list discussions and personal websites, not in published sources, should be removed. That's kind of what Electowiki is for. I suspect there are some of these in the list, but I don't know which ones they are. rspeer / ɹəədsɹ 06:22, 17 November 2007 (UTC)

You're just looking for ones that doesn't match their articles or have articles, right? Okay, then, we have three tasks:

1. Changing the table to a definition list.
2. Deciding which criteria don't need references here, since they're covered sufficiently in their own articles.
3. Finding references for the remaining criteria.

I have a pretty good collection of social choice papers, so I can help with #3. Of course I'm sure Markus could do the same if he was asked. Any of us could do #1, and that could be before or after the others. But #3 relies on #2. Who wants to do that?

CRGreathouse (t | c) 15:56, 17 November 2007 (UTC)

I've converted the table to two definition lists, satisfied and failed.

Is it necessary to find clearly worded descriptions themselves in academic papers, or can what's written here be translations of academic jargon? VoteFair (talk) 01:11, 18 November 2007 (UTC)

(de-indent) Certainly reword. Rewording is good because (1) it makes the article easier to understand for those not familiar with the field, and (2) avoid copyright concerns. CRGreathouse (t | c) 04:46, 18 November 2007 (UTC)

Okay, I've briefly gone through the criteria. Universality, the Condorcet criterion, Pareto efficiency, non-imposition, non-dictatorship, independence of clones, the consistency criterion, and the Schwartz criterion are all properly sourced in their articles. The remainder:

• Participation: Sourced to Voting Matters, hardly a notable publication (but probably fine). There may be other sources out there, though be careful (tricky wording could make something similar wrongly seem to be the same).
• Polynomial runtime: No voting article written, general link only. Voting articles I've seen give this different names. Also probably fine.
• Majority criterion: Unsourced, but a reference could easily be found. Perhaps D. Black 1948, On the Rationale of Group Decision-Making?
• Monotonicity: Unsourced, but there are lots of references. Arrow 1950 and/or 1951 would be my choice, but I have dozens of other sources and there are probably hundreds.
• Local independence of irrelevant alternatives: Oddly, it doesn't reference A. Levenglick and H. Young 1978, A consistent extension of Condorcet's election principle.
• Invulnerability to burying, later-no-harm, invulnerability to compromising, and invulnerability to push-over aren't sourced, likely because no peer-reviewed publication has accepted a paper using them. Maybe that's not fair; I think I heard of one of these making it into the big leagues. I'll look further into it. If someone came by and deleted one of these (citing WP:V) I probably wouldn't re-add it.

CRGreathouse (t | c) 05:53, 18 November 2007 (UTC)

There is a characteristic that is missing, the one called "reinforcement," which is mentioned in the history section. Earlier in this talk page Schulze says:

"Reinforcement says that, when the same complete ranking of all candidates is chosen both in situation 1 and in situation 2, then the same complete ranking must also be chosen when situation 1 is added to situation 2. Thus, "reinforcement" is like "consistency", but for methods that produce a complete ranking of the candidates."

I was not able to find any Wikipedia references to this characteristic. (The reinforcement article applies to the field of psychology.)

I suggest adding this characteristic to the "satisfies" list, with this description:

If all the ballots are divided into separate races and the overall ranking for the separate races are the same, then the same ranking occurs when all the ballots are combined.

Of course we would need a reference before we can justify adding this characteristic. VoteFair (talk) 00:08, 19 November 2007 (UTC)

Please re-add it; I removed it but should not have. As for a reference, the Young/Lev reference mentions it so we should be fine since we already cite that. CRGreathouse (t | c) 00:33, 19 November 2007 (UTC)

Done. Now I notice two more satisfied criteria that are missing: reversal symmetry and Smith criterion. Those have well-written brief descriptions, so I don't need to create a translation.

This brings up a question. Do the references that Rspeer wants apply to whether the K-Y method satisfies each criterion, or that each brief description here is valid, or that the criterion is widely accepted among academics? VoteFair (talk) 01:24, 19 November 2007 (UTC)

Of course I can't. and won't, speak for Rspeer, but I'll say what I want. I think that only widely-accepted criteria should be included, and that general references for these should go in their own articles (put them here only if there is no article for that criterion). References showing that K-Y has the criteria would be welcome here when it's not clear that the method satisfies it -- for example, I would personally appreciate a reference for reversal, since I can't recall reading one at the moment. As for Smith... how could we have missed that?

For now I think we'll have to live with consensus to determine that the short descriptions are valid, since we want to write them in an 'encyclopedic' way that may not match the academic prose.

CRGreathouse (t | c) 02:29, 19 November 2007 (UTC)

I indicated which failed criteria apply to all Condorcet methods (according to other Wikipedia pages). I wasn't sure if the "invulnerability to push-over" fails for all Condorcet methods, so I didn't add the note there, but my guess is that the note applies and should be added.

I removed the example from the IIA criterion because any Condorcet result (not just circular ambiguities) apparently can cause such violations. VoteFair (talk) 01:30, 20 November 2007 (UTC)

I think it's obvious that Reversal symmetry applies to the Kemeny-Young method because reversing the preference order on every ballot is equivalent to swapping the numbers in the left and right columns of the tally table. That change causes the lowest Kemeny score to become the highest, and vice versa. (Also, the K-Y method is very symmetrical.) Here is what I propose adding for its description:

If the preferences on every ballot are inverted, then the previously most popular choice must not remain the most popular choice.

Here is a proposed description for the Smith criterion:

The most popular choice is a member of the Smith set, which is the smallest set of choices such that every member of the set is pairwise preferred to every choice not in the Smith set.

Any objections to adding these in the "satisfied" criteria list? VoteFair (talk) 01:47, 20 November 2007 (UTC)

[edit] Reversal symmetry

No objections to those additions, though until we get a reference I'll add a {{cn}} tag to the reversal symmetry claim. I see your logic, but if the Smith set is the whole set of candidates it's not obvious to me that the winner would change. CRGreathouse (t | c) 05:50, 20 November 2007 (UTC)

I've added these two criteria with a citation needed for the Reversal symmetry criterion, as you've requested. I'm not sure of the implications of the Smith set being all the candidates, but I'm aware that if all the candidates are tied then there is no winner and then the wording "the previously most popular choice must not remain the most popular choice" is satisfied because there is no "previously most popular choice." Although we could add a conditional phrase such as "if there is a most popular choice," I think the existing description would not be misunderstood for the case of a tie. VoteFair (talk) 22:49, 20 November 2007 (UTC)

I don't mean a literal tie, I mean that all alternatives are in the Smith set. For example, A > B > C with 10 votes, B > C > A with 11 votes, and C > A > B with 12 votes. There is a Kemeny winner even though all alternatives are in (what you call) a circular tie. CRGreathouse (t | c) 00:57, 21 November 2007 (UTC)

I agree we are probably talking about two different kinds of ties. If I understand the Smith set correctly then I see that in your example all the choices are in the Smith set. To understand this example better I plugged in the numbers to calculate the intermediate results, which are accessible at [10] In this example the highest Kemeny score--for the sequence C > A > B--is from the three numbers in the left column of the tally table (23+12+22). The lowest Kemeny score is the sequence B > A > C which has a score summed from the numbers in the right column of the tally table (10+21+11). If all the voter preferences are reversed, the new highest score is for the sequence B > A > C, which previously had the lowest score.

Perhaps the kind of tie I was talking about (A=B=C, which would occur if there were 10 votes for each of your three ballot sequences) so obviously does not change the winner that maybe I shouldn't have mentioned it. VoteFair (talk) 23:00, 21 November 2007 (UTC)

I might start looking at the simplest nontrivial case (3 alternatives, linear ballots, no pairwise ties between distinct alternatives) to see if reversal symmetry holds there. That might give support (or a counterexample). In the meantime, keep your eyes open (Rspeer, Marjus, VF) for any results on this in 'the literature'. CRGreathouse (t | c) 02:12, 23 November 2007 (UTC)

It's intuitively clear to me that K-Y has reversal symmetry. Circular ties are confusing the issue, because the method never makes note of circular ties, only complete rank orders. Each point gained in the Kemeny score of a particular rank order is a point lost by its reversal. I recognize, though, that my intuition is different from a reliable source saying so. rspeer / ɹəədsɹ 17:50, 7 December 2007 (UTC)

My intuition agrees with yours, but until I see either a mathematically rigorous proof or a published paper with the claim I'll be wary. I've made claims that were intuitively obvious to me but were wrong -- and social choice has its fair share of counterintuitive results. I hope, rspeer, that you'll take no offense at my stubbornness here. :) I'd just hate to add something wrong to the page. CRGreathouse (t | c) 02:58, 8 December 2007 (UTC)

In the interest of removing the "citation needed" tag for the reversal symmetry criteria, here is an informally worded proof of reversal symmetry for the Kemeny-Young method. Keep in mind that reversal symmetry only requires that a winner not remain the winner if all the preferences are reversed.

1. Calculate the sequence with the highest Kemeny score, and based on that sequence identify the winner. (If there is no single winner, then reversal symmetry is undefined.)

2. Within the tally table, identify which counts are summed to produce the Kemeny score for the winning sequence.

3. Leaving the numbers in the tally table where they are, change the heading "Prefer X over Y" to "Prefer Y over X" and change the heading "Prefer Y over X" to "Prefer X over Y". This revised tally table now represents the effect of reversing all the preferences of all the voters. (If this is not clear, study how the tally table is created.)

4. Using the revised pairwise counts, calculate the sequence with the highest Kemeny score. It will be the same sequence score as before, and will be the sum of the same tally numbers in the same positions of the tally table. (If a higher sequence score were possible, it would have been found in the original computations.)

5. View the labels that apply to the counts that contribute to the new winning sequence score, and recognize that the new winning sequence is fully symmetrically reversed from the original sequence. For example, if the original winning sequence was B (first), C and D tied (in second place), and A (third), then the winning sequence based on the reversed preferences will be A (first), C and D tied (in second place), and B (third).

6. In this reversed sequence, notice that the first-place winner becomes the last-place loser. Obviously this satisfies the less-stringent "reversal symmetry" requirement that the original first-place winner cannot be the winner after the preference reversal.

Notice that the Kemeny-Young method has even more reversal symmetry than required by the criteria named "reversal symmetry". Specifically if the Kemeny-Young method identifies choice X as being preferred over choice Y, then a complete reversal of preferences results in choice Y being preferred over X, and this applies to all combinations of X and Y.

Although I'm not offering a proof, I suspect that no other single-seat voting method has this higher level of reversal symmetry, which goes way beyond what is currently called reversal symmetry.

CRGreathouse, do you still have an objection to removing the "citation needed" tag? (Rspeer already said "It's intuitively clear to me that K-Y has reversal symmetry.") VoteFair (talk) 18:50, 12 March 2008 (UTC)

I want to remove the tag eventually, but I do still object to its removal at this point. I find your informal proof rather more reason to keep the tag. Here's why: If you have more than two candidates (for two candidates, your proof works fine) the 'sequence scores' aren't reversed. This is because X>Y votes go from X to Y, but X>Z votes go from X to Z, so there is no one-to-one relationship between the votes for original candidates and the new ones.

The order may always reverse itself -- I haven't experimented to see if this is always the case even for small numbers of candidates and voters -- but the scores will vary. And since we're really only concerned with the case of a really gnarled election with lots of cyclic ties, it's not evident to me that such a pathological case could be constructed.

And since there are enough complications in the issue, I'd much prefer a citation to an assertion. Has someone checked that rag, Voting Matters, to see if it had a proof or claim of this? That could short-circuit the whole issue.

CRGreathouse (t | c) 19:54, 12 March 2008 (UTC)

You refer to "votes" going somewhere (e.g. X to Z), but remember that the Kemeny method doesn't shift votes the way IRV shifts votes; and it doesn't look for a path like in the Schulze method; it just calculates sequence scores for all possible sequences.

An example helps to clarify the reversals we're talking about. Let's use the article's Tennessee example. Here are the original preferences for the 42% of voters who live close to Memphis:

1. Memphis

2. Nashville

3. Chattanooga

4. Knoxville

After reversing the preferences of all these voters, the same 42% of voters now have this preference:

1. Knoxville

2. Chattanooga

3. Nashville

4. Memphis

All the reversed preferences can be arranged in a reversed tally table, which is the same arrangement of numbers (as in the article's example), but with the column headings renamed (swapping "X" and "Y", but not also swapped in the left label column):

All possible pairs of choice names	Number of votes with indicated preference
	Prefer Y over X	Equal preference	Prefer X over Y
X = Memphis Y = Nashville	42%	0	58%
X = Memphis Y = Chattanooga	42%	0	58%
X = Memphis Y = Knoxville	42%	0	58%
X = Nashville Y = Chattanooga	68%	0	32%
X = Nashville Y = Knoxville	68%	0	32%
X = Chattanooga Y = Knoxville	83%	0	17%

With the table having the same arrangement of numbers, the new winning sequence score (393) is the same as before, and it is the sum of the same numbers (in what are visually the same locations).

The new winning sequence produces this result, which is the reverse of the article's result ranking:

1. Memphis

2. Knoxville

3. Chattanooga

4. Nashville

Note that the previous winner, Nashville, is now least-popular.

The only kind of situation that might seem to lack this full, complete, reveral symmetry is one in which there is a tie in first place, but in that case the "reversal symmetry" criteria is undefined.

Now let's consider a "really gnarled" case. Suppose there is circular ambiguity in the form of everyone in a meeting pointing to the person on their right as their first choice, pointing to the person at the head of the table as their second choice, pointing to the person on their left as their third choice, and then pointing to the person at the foot of the table as their fourth choice. In this example the Kemeny method would identify the person at the head of the table as the most popular (the single-seat winner), and after reversing preferences that same person would become the least popular (biggest loser).

Even in such "gnarled" cases the tally table for the reversed preferences is the same arrangement of numbers with the column headings swapped, so how could the first-choice winner (if there is only one) be anything other than least-popular in the reversed-preferences case?

If you think there might be room for doubt, we might also want to reconsider whether finding the lowest sequence score of opposition preferences — as in the original Kemeny method — is equivalent to finding the highest sequence score of supporting preferences — which is what VoteFair popularity ranking has always used. Obviously they are equivalent, which is closely related to my claim here. VoteFair (talk) 00:06, 13 March 2008 (UTC)

To me the equivalence of the 'two' methods is far more obvious. But hey, I'll listen to consensus: if MarkusSchultze or rspeer removes the tag, I won't put it back. Until then maybe I'll be able to find a paper to attribute the result to. CRGreathouse (t | c) 03:49, 13 March 2008 (UTC)

(de-indent) Markus Schultze knows that the Kemeny-Young method satisfies the reversal symmetry criteria, but of course he doesn't want the strengths of the Kemeny-Young method to overshadow "his" Schultze method, so of course he won't be removing the "citation needed" tag. Note that if the Kemeny method failed the reversal symmetry criteria, you can be sure that Schultze would have indicated that fact long ago. If he had uncertainty about whether the Kemeny method satisfies reversal symmetry, he would have said so. (For perspective, the Kemeny method is completely symmetrical with respect to preference reversals, but the Schultze method is not completely symmetrical because it identifies a path starting with the largest pairwise win, yet the Schultze method still meets the criteria named reversal symmetry.)

Rspeer has stated that the Kemeny-Young method obviously satisfies reversal symmetry, but his role is to moderate among Schultze, you/CRGreathouse, and me/VoteFair, so he isn't likely to remove the tag.

That leaves you, CRGreathouse, as the only recently active contributor who is uncertain as to whether the Kemeny-Young method satisfies the reversal symmetry criteria. For that reason I'll again try to convince you that the criteria is met.

CRGreathouse, you said you agree that finding the highest sequence score based on supporting preferences is equivalent to finding the lowest sequence score based on opposing preferences, so let's start with that concept.

Looking at the article's Tennessee example, notice that the lowest (not the highest) sequence score is 207 and it corresponds to the sequence Memphis first, Knoxville second, Chattanooga third, and Nashville forth. This sequence is a complete reversal of the sequence with the highest score, which is the sequence Nashville first, Chattanooga second, Knoxville third, and Memphis forth.

This inverse characteristic—the sequence with the highest Kemeny score is a complete reversal of the sequence with the lowest Kemeny score—applies to all cases! To understand why, consider the tally table for the 26% of the voters in the Tennessee example who prefer Nashville first, Chattanooga second, Knoxville third, and Memphis fourth. The tally table looks like this.

All possible pairs of choice names	Number of votes with indicated preference
	Prefer X over Y	Equal preference	Prefer Y over X
X = Memphis Y = Nashville	0%	0	26%
X = Memphis Y = Chattanooga	0%	0	26%
X = Memphis Y = Knoxville	0%	0	26%
X = Nashville Y = Chattanooga	26%	0	0%
X = Nashville Y = Knoxville	26%	0	0%
X = Chattanooga Y = Knoxville	26%	0	0%

Now consider a reversal in preference for these voters. (Originally, for these voters, Nashville was first, so now it's last, Memphis was last and is now first, and Knoxville and Chattanooga are in third and fourth places respectively.) The revised tally table now looks like this.

All possible pairs of choice names	Number of votes with indicated preference
	Prefer X over Y	Equal preference	Prefer Y over X
X = Memphis Y = Nashville	26%	0	0%
X = Memphis Y = Chattanooga	26%	0	0%
X = Memphis Y = Knoxville	26%	0	0%
X = Nashville Y = Chattanooga	0%	0	26%
X = Nashville Y = Knoxville	0%	0	26%
X = Chattanooga Y = Knoxville	0%	0	26%

Notice that the numbers in the "Prefer X over Y" column have simply moved to the "Prefer Y over X" column, and the numbers in the "Prefer Y over X" column have moved to the "Prefer X over Y" column. (The vertical symmetry that happens to apply to these voters is not significant because the vertical sort order does not affect the calculation results.) This column swapping occurs for any single voter, for any group of voters, and for any set of voters for any case when the preferences are reversed. (It also applies when there are voter-preference-based ties because the numbers in the equally preferred column do not change with a preference reversal, which is because if someone indicates no preference between two choices, then a reversal also has no preference between those two choices.)

Consider that the swapping of columns represents a symmetry that can be thought of as having the dividing line being the "Prefer X and Y equally" column. This is the same symmetry that causes the sequence with the highest Kemeny score for supporting counts to always be the same sequence as the one with the lowest Kemeny score for opposing counts. It occurs because any voter's count that increases the highest score (in one side of a row) causes one less count in the lowest score (in the other side of the same row).

In other words, finding the lowest score based on counting how many voters oppose each pairwise preference (as done in the original method described by Kemeny) is equivalent to asking "What happens if the preferences of every voter are reversed?" Do you recognize that the two concepts—one that you agree with and one that you have doubts about—are mathematically the same?

To further appreciate the symmetry of the tally table, consider that each Kemeny sequence score consists of a summation of numbers where each (and every) tally-table row contributes one—and only one—number to the summation. This reveals that an alternate way to identify the highest sequence score is to pick one number from each row and calculate the sum of those numbers for all possible picked numbers, and then remove the summations that do not correspond to a valid sequence. (Obviously this is not an efficient calculation method; it just serves to emphasize that each Kemeny sequence score uses one number from each and every row of the tally table.)

With this symmetry of the tally table in mind, please re-read my above (informally worded) proof showing that the Kemeny method meets the reversal symmetry criteria. (As you do so, again notice that your concept of votes getting shifted from X to Z instead of Y does not apply to the Kemeny method.)

Do you still have objections to removing the "citation needed" tag? Based on my having read scientific publications back when I was getting a degree in physics, I question whether someone would bother to write a published peer-reviewed academic article for such a trivial proof, so I doubt you will find one in the literature. Also consider that with multiple names for what Wikipedia calls the Kemeny-Young method, such a proof would be very difficult to find. I'm not saying that such an article doesn't exist. I'm saying that three out of four of us agree that finding such an article is unnecessary.

Of course if you see any flaw in the above (step-numbered) proof, please point it out. After all this discussion page is the peer-review part of Wikipedia. VoteFair (talk) 18:47, 26 March 2008 (UTC)

Apparently there are no longer any objections to removing the "citation needed" tag, so I've removed it. VoteFair (talk) 03:53, 29 April 2008 (UTC)