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

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