<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 14 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
font-family:"Calibri","sans-serif";}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal>I always thought the “Condorcet is like a round-robin athletic tournament” analogy was weak, because individual voters don’t get to go through the round-robin and make their pairwise preferences explicit. (As a voter, I’d find a “better/worse” pairwise choice for all pairs easier than filling out a ranked ballot, but that just may be because I’ve been making pairwise choices between the <em><span style='font-family:"Calibri","sans-serif";font-style:normal'>ophthalmologist’s</span></em><i> </i>lenses since I was six.) N x (N-1) “A or B” choices is an easier way to fill out a ballot than “rank A1,A2,A3…” so no matter what method you use to translate my ranked ballot into pairwise comparisons I have no way to know if you counted my A<>B preferences the way I would have.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>The sports analogy caught my attention because one of my main interests for a decade or so has been analyzing why and how college sports rating systems work. They EXIST precisely because there ISN’T a round-robin that a voting system can be compared to. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>What (US) college sports ratings systems do to account for the fact that the games-played pairwise matrix is “sparse” is to apply some algorithm to the directed games graph based upon the number of one-way connections A[i] -> … -> A[j] compared to the number of A[j] -> … -> A[i] paths for some number of “->”s. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>What is called here the “pairwise matrix” (call it PM) is PM[I,j]= the number of ballots where alternative i is ranked better than alternative j and PM[j,i] is the number of ballots where alternative j is ranked better than alternative i. In sports ratings, the beginning point is an “incidence matrix” where IM[i,j] is the number of wins by team i over team j and IM[j,i] is the number of wins by team j over team i.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>The PM and IM count the number of edges in a graph where points (alternatives/teams) are connected to other points (alternatives/teams) by an arrow from point A to B representing a “win” by A against B. In sports it’s an actual win in a game, in the PM it’s a ballot that has A ranked above B.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>“Cycles” are common in sports. Team A beat B and team B beat team C and team C beat team A. Ratings systems routinely sort that A>B>C>A chain by comparing how A, B and C performed against their common opponents, which is analogous to comparing alternatives in a PM “loop” by how each compares to the alternatives that are included on the same ranked ballots they are.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>The way sports ratings systems use a very sparse PM to come up with an ordered list of teams is to begin with that directed graph that counts the number of “->”s and then look at how every team-pair compares based upon number of ->-> paths that relate each vertex (team/alternative) to each other, then the number of ->->-> paths that do so, and continuing in that fashion until their algorithm “converges” to an ordered list that doesn’t change.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>This is easy to do: the number of paths from Alternative i to Alternative j that are two steps long is PM^2[i,j]. What that’s counting is the number of paths i has with k’s that have winning paths against j.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>If there is some m such that PM^m results in a Condorcet winner when paths of length m are counted that could be a simple way to break Cycles.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>When applied to the example in <a href="http://en.wikipedia.org/wiki/Schulze_method">http://en.wikipedia.org/wiki/Schulze_method</a> (the Wikipedia explanation of Schultze) you find a Condorcet winner when paths of length 2 are counted:<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> A B C D E<o:p></o:p></p><p class=MsoNormal>A 0 20 26 30 22<o:p></o:p></p><p class=MsoNormal>B 25 0 16 33 18<o:p></o:p></p><p class=MsoNormal>C 19 29 0 17 24<o:p></o:p></p><p class=MsoNormal>D 15 12 28 0 14<o:p></o:p></p><p class=MsoNormal>E 23 27 21 31 0<o:p></o:p></p><p class=MsoNormal>PM(i,j)-PM(j,i):<o:p></o:p></p><p class=MsoNormal> A B C D E<o:p></o:p></p><p class=MsoNormal>A 0 -5 7 15 -1<o:p></o:p></p><p class=MsoNormal>B 5 0 -13 21 -9<o:p></o:p></p><p class=MsoNormal>C -7 13 0 -11 3<o:p></o:p></p><p class=MsoNormal>D -15 -21 11 0 -17<o:p></o:p></p><p class=MsoNormal>E 1 9 -3 17 0<o:p></o:p></p><p class=MsoNormal>finding PM^2<o:p></o:p></p><p class=MsoNormal>2 done. Elapsed=.000000 seconds.<o:p></o:p></p><p class=MsoNormal>A 1950 1708 1622 1784 1404<o:p></o:p></p><p class=MsoNormal>B 1213 1846 1952 1580 1396<o:p></o:p></p><p class=MsoNormal>C 1532 1232 1938 2271 1178<o:p></o:p></p><p class=MsoNormal>D 1154 1490 876 1756 1218<o:p></o:p></p><p class=MsoNormal>E 1539 1441 1898 1938 1930<o:p></o:p></p><p class=MsoNormal>PM^2(i,j)-PM^2(j,i): <o:p></o:p></p><p class=MsoNormal>A 0 495 90 630 -135<o:p></o:p></p><p class=MsoNormal>B -495 0 720 90 -45<o:p></o:p></p><p class=MsoNormal>C -90 -720 0 1395 -720<o:p></o:p></p><p class=MsoNormal>D -630 -90 -1395 0 -720<o:p></o:p></p><p class=MsoNormal>E 135 45 720 720 0<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Now, I don’t think it’s a coincidence that JUST looking at PM^2 gives the same winner (E) as Schultze does, since it’s counting the x->y->z chains, giving extra credit to x >> z based upon x’s wins over alternatives that themselves have {}->z wins, and that’s explicitly part of the motivation for Schultze.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>But <b>if</b> that is equivalent to Schultze (I’ll leave that test to people who know better than I how it works) I find it more cosmetically appealing than the Schultze definition.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>There’s no “eliminate candidate based upon…” which has always rubbed me the wrong way – too IRVish. All ballots and all alternatives are directly involved in the final count.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I’d be interested in any further analysis of my observation. I’m not proposing anything, just offering an area of research that I’m surprised hasn’t been explored here (afaik) as much as in the sports market for rating systems.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p></div></body></html>