[EM] Condorcet How?

[robert bristow-johnson]

On Apr 8, 2010, at 2:02 PM, Dave Ketchum wrote:

> On Apr 7, 2010, at 8:29 PM, robert bristow-johnson wrote:
>> On Apr 7, 2010, at 6:25 PM, Dave Ketchum wrote:
>>
>>> This is some thought about keeping it simple, yet doable.
>>>
>>> I will lean toward Ranked Pairs with margins,
>>
>> not sure what "with margins" does.  i'll read below...
>
> vs comparing per winning votes - each has backers.

Juho just explained it, so now i know (earlier i had wondered if  
"margins" was a normalized or percentage beat strength).  i've always  
thought that the Tideman RP was *only* framed in terms of margins.  i  
do not know why anyone would back the "winning votes" metric for beat  
strength.

>>> but amending toward other types of Condorcet should be doable.
>>>
>>> Voting:  Voter can rank one or more candidates.  Equal ranking  
>>> permitted.  Counters care only which of any pair of candidates  
>>> ranks higher, not how voter decides on ranking.  Write-ins  
>>> permitted (if few write-ins expected, counters may lump all such  
>>> as if a single candidate - if assumption correct the count  
>>> verifies it; if incorrect, must recount).
>
> My thoughts are that supporting write-ins is worthy and doable, but  
> am not excited about how.

i've thunked about it.  just like supporting third parties and  
independent candidates (who get ballot access) is important (and is,  
indeed, why we are promoting preferential voting in the first place),  
for the same reason, i think the ability to deal with write-ins (but  
just *one* write-in per ballot) is also important.

of course, nearly always, the aggregate "write-in" will not win, and  
then it doesn't matter who the folks are that are written in.  (one  
point about the 2000 Bush v. Gore in Florida is that there were some  
idiots that checked a listed candidate and then also wrote that very  
same name in the write-in slot.  the machine counter rejected these  
ballots as overvotes, but when the media hand-recounted Florida  
statewide and determined that, due to these overvotes, Gore won by 172  
out of 5 million.)  the issue is how to make legal verbiage for how to  
deal with the case where "write-in" wins.  then, of course, a hand  
recount is necessary (perhaps assisted by the scanning machines) and a  
straight-forward procedure must have language that does not *assume*  
at the outset who the winning write-in is, but accomplishes the task.

>>> Counting:  Besides the N*N matrix, I would add an N array to  
>>> optimize this.  Count each ranked candidate in the array.  Later  
>>> the array will be added into the matrix rows as if the ranked  
>>> candidates won in every one of their pairs.  This is correct for  
>>> pairs with no ranking, and for pairs with one ranked.
>>
>> already this is complicated and someone in the "One person, one  
>> vote" crowd (the anti-IRVers) in Burlington would say that you're  
>> trying to pull one over on them.
>>
>> Ranked pairs need not be that complicated.
>
> So far we are just doing counting.  After that, time to think of CW  
> and cycles, and for methods such as ranked pairs mattering.
>
> Think of 10 candidates and a bunch of bullet voters.  For each  
> ballot its candidate needs counting in each of its 9 pairs.  I would  
> have the counters count such in its element in the N array, with all  
> of the N array added into the N*N matrix in one step later.
>
> Try a voter ranking two of the 10 (should be common for those not  
> doing bullet).  Stepping two entries in the N array will get 16  
> entries in the matrix properly stepped.  One entry will get stepped  
> as if each ranked higher, so I have the counters adjusting for this  
> as part of counting that ballot.

>> you don't need to be adjusting any other counts in the N*(N-1)/2  
>> pairs, which is my preference of expressing the "N*N matrix".  i  
>> still find the "N*N matrix" to be a useless visual tool.  i want to  
>> see N*(N-1)/2 pairs of numbers.  that's how you visualize in a  
>> glance how Condorcet decides an election.  this "N*N matrix", such  
>> as it is, is just useless.
>
> Your preference over the matrix is interesting, provided you keep  
> your location of pairs understandable and get the same winner as the  
> matrix would achieve.

is this example (the 2009 Burlington mayoral race) clear enough?:

   M 4064
   K 3477
    < 587>

   M 4597     K 4313
   W 3664     W 4061
    < 933>     < 252>

   M 4570     K 3944     W 3971
   S 2997     S 3576     S 3793
    <1573>     < 368>     < 178>

   M 6263     K 5515     W 5270     S 5570
   H  591     H  844     H 1310     H  721
    <5672>     <4671>     <3960>     <4849>


it's just a visual rearrangement of the N*N matrix.  it comes out as a  
triangle, instead of a square matrix (with a blank diagonal), and you  
can see clearly who beats who, and if the candidates are nicely  
ordered (as they were in 2009, it's unambiguously M>K>W>S>H) in a  
Condorcet sense.

the number in <brackets> is the margin and is the first number that  
Tideman RP looks at to determine which (remaining) pair is committed  
to (and removed) in each scan.  the clearest expression of voter  
preference is that M is preferred over H.  the least clear is that W  
is preferred over S.  what is interesting (and i believe a source to  
the lack of voter confidence in the election result) is that the  
second weakest defeat is what decided the election.  but you can look  
at that triangle and immediately see who beats who and how badly were  
they beaten.

>> the N*(N-1)/2 pairs is all of the numerical information you need,  
>> and all you need to do is compute, for each pair, the abs value of  
>> the difference of vote counts. so you have 3 numbers for each of  
>> the pairs.  then there are N*(N-1)/2 - 1 scans, each identifying  
>> and removing the remaining pair with the highest abs(diff).  then,  
>> with each of these removed pairs in order of their removal,  
>> construct the "who beats who" paths out of nodes starting with the  
>> highest abs(diff), and as Tideman sez, ignoring pairs that are  
>> contradictions, resulting in a cycle after "committing" (i would  
>> use that word instead of "locking") to the race pairs previously  
>> accepted.
>>
>> that is simpler.  both as language of law, and to program into a  
>> computer.
>
> Your many scans are something I would avoid.

seems to me that a computer can deal with the pairwise tallies (and  
computing the margin for each) could do N*(N-1)/2 - 1 scans in a  
hurry.  it's O(N^2) (N is the number of candidates, not voters).  as  
far as scanning ballots at the precinct level, each ballot is scanned  
once and the computer tallies N*(N-1)/2 numbers for each scanned ballot.

>
> For some of this computers vs humans matters - counting the bullet  
> votes is easier for humans to get right by doing a single entry in  
> the N array vs 9 in the matrix for each such ballot, while a  
> computer only needs simple programming.

but can we depend on people doing bullet voting.  in the worst case  
(regarding complexity), every ballot would have every candidate  
ranked, and the right procedure would work the best in the worst case.

>
> In looking for the CW I eliminate a candidate via each carefully  
> selected comparison - 9 comparisons if 10 candidates.  That does not  
> tell if there is a CW, so scan that candidate's pairs - if any  
> losers that is a cycle member and we now know all the cycle members  
> it loses to.  Scan those members' pairs for the other members they  
> lose to, continuing until we know all the interesting pairs.
>
> Most cycles only have three members.  Anyway, we have the pairs that  
> compose the cycle and can use whatever method we choose to sort them  
> out.

in the case of a 3-cycle, it should be obvious which pair race should  
be discounted (the one with the smallest margin), Tideman and Schulze  
agree which pairing is ignored, and once that happens, it's clear who  
the winner is.


>> it sure seems to me that the existing Tideman RP is simpler and at  
>> least as "meaningful" in reflecting voter preference.
>
> Most methods only care about cycle members and their relationships.   
> I find the members and only consider methods interested in such -  
> and do not argue here about which of such methods to actually use.

what's nice about Tideman or Schulze, is that the methods do not care  
about who the Smith set is or even if there *is* a cycle.  the method  
just grinds away and mindlessly picks the winner according to the  
rules (and i think the Tideman rules are more transparent than the  
Schulze rules however both can be given concise language, even though  
i didn't know that about Schulze until Markus posted his proposed  
legislation).

--

r b-j                  rbj at audioimagination.com

"Imagination is more important than knowledge."