[EM] Summability - time

[Dave Ketchum]

On Thu, 24 Jul 2003 19:56:33 +0200 (CEST) Kevin Venzke wrote:

>  --- Markus Schulze <markus.schulze at alumni.tu-berlin.de> a écrit : 
> 
>>... that when V is the number of voters and C is the number of candidates
>>    then the runtime to calculate the pairwise matrix is O(V*C*C) while
>>    the runtime to calculate the IRV winner is only O(V*log(C)) so that
>>    while the Condorcet supporters are still summing their matrices the
>>    IRV winner is already preparing his inaugural speech.
>>
> 
> But wait a minute...  With the IRV count, you have to know what happens earlier
> (e.g., the first elimination) to know what to count later.  With Condorcet,
> you're always counting everything, so the task could be divided up among a number
> of computers, couldn't it?
> 

Most of the time is spent getting the ballots together.  Doing whatever 
math might be required is, using computers and by comparison, trivial with 
either method.

Further, whatever is doable at precinct level with polls open is basically 
free time, for each ballot can be looked at when the voter files it as 
completed (not while the voter is still considering amending it).

For Condorcet the ballots only need looking at a single time, for all the 
information is summed into the matrix then, publishable as soon as the 
polls close, and the matrix forwarded toward wherever district totals are 
handled if the district is more than a precinct.
      Wherever totals are handled cycles must be considered, but this 
needs no vote information other than the district total matrix.

For IRV a similar matrix could be filled out, based on each voter's first 
and second ranks, and forwarded.  This would often identify the winner as 
quickly as Condorcet.
      When this is not enough, IRV needs patterns.  These could have been 
forwarded from each precinct or, when more details are needed, we could 
ask each precinct to retrieve ballots for A>B and return counts as to what 
these voters voted as third rank.  Taking New York State as an example, 
there could be ten candidates for governor and 5,000,000 ballots.  With 10 
candidates and bullet voting permitted, I count 10*10*9*8*7*6*5*4*3 
possible patterns - a LOT of data to accumulate at a central facility, or 
a BIG nuisance to try to retrieve from precincts.

Note also that we have absentee voting in NY, with these voters having to 
mail in their votes before election day, but being acceptable if received 
by a few days later.
      No big deal for Condorcet, for these are trivial additions to the 
matrices and change nothing unless already close to a tie.
      For IRV these can change the order of discarding losers and that can 
result in lots of Relooking and BIG surprises.

> 
> 
>>The main question is whether summability is a desirable or an undesirable
>>property. I am aware that there are scientists who consider this property
>>undesirable (e.g. Nurmi, Bartholdi, Bowler) since compliance with this
>>property means that it is easier to get the information you need to run
>>a strategy. But I don't know any scientist who considers this property
>>desirable.
>>
> 
> I'm surprised to read this.  I thought "simple strategy" was a virtue for an
> electoral method.  Surely runtime isn't considered a serious issue for summable
> methods...?


I thought discouraging strategy games was an advantage to Condorcet - that 
doing sincere voting being a voter's best bet was desirable - look at what 
came up in the recent turkey discussions, in which the games tended to 
hurt those who got suckered in to playing them.

> 
> Kevin Venzke
> stepjak at yahoo.fr

-- 
davek at clarityconnect.com  http://www.clarityconnect.com/webpages3/davek
  Dave Ketchum   108 Halstead Ave, Owego, NY  13827-1708   607-687-5026
            Do to no one what you would not want done to you.
                  If you want peace, work for justice.