Re: Sponsor this

["Norman Petry" <npetry@accesscomm.ca>]

Raul Miller wrote:

>Drats.
>
>I guess that means I should either change the name (pull out smith)
>or change the mechanism.  Straw poll (mostly I'm interested in hearing
>what people who have sponsored the proposal think): should I go for the
>quick fix (change name from Smith/Condorcet to Condorcet, limit ballots
>to less than five distinct options), or should I go for the real fix
>(supplement step the new A.6(6) with smith criteria)?
>

This shows clearly why it is risky to invent new voting methods.  They're
hard to get right, so it is a good idea to adopt a method which is well
studied, and has known properties.

The problem isn't a shortage of good methods; if anything, there are too
many of them.  However, the number of bad methods out there is infinitely
greater.  Please work with us on the committee to choose a good method.  The
problem with voting systems is that there are an *infinite* number of
possible systems.  This whole area can become a morass to wade into, if you
don't have a clearly defined set of properties that you'd like the method to
satisfy.  We discovered a long time ago on EM that the only way to have a
rational discussion about the merits of one method over another was to
define "criteria", which are precise yes/no tests of some property or other,
and then see which methods pass or fail the criteria.  Then, a method can be
chosen by deciding what criteria are important, and picking the method which
satisfies most of them.  In the final report our committee will be making to
debian, we will list the criteria the proposed method(s) satisfy, and why
they may be important.  This will give voters a set of guarantees that they
can rely upon when voting and sponsoring motions.

I think it is better if the method described in the constitution is defined
in functional terms, rather than in the form of an algorithm.  Not only is
that form of description briefer and easier to understand, but it allows the
bugs in the implementation to be fixed.  If every bug in the algorithm used
to implement the voting method requires a constitutional amendment to
change, it's going to be a real PITA to maintain.  For example, the Smith
criterion can be unambiguously stated in one or two sentences.  If you want
to use Smith as a voting method, rather than just a criterion the method
satisfies (which would be better, imho), if you define it in the
constitution then a later discovery that your algorithm doesn't actually
implement smith could easily be fixed.

I wouldn't worry about implementation at this stage -- most pairwise methods
require under 100 lines or so to implement, and there are algorithms that
are already available for Smith* and Schwartz set calculations, as well as
many complete methods.  I have implemented a large number of these methods
in Python (GPLed code) in order to carry out simulations of their
properties, and these could easily be adapted to carry out the counting of
future votes in an automated way.

--
Norm Petry

p.s. *As an aside, one way to implement Smith that was proposed on EM a long
time ago is to begin by creating a list of (n) candidates.  Find the
candidate(s) with the fewest number of defeats, and place them at the
beginning of the list, since they are guaranteed to be members of Smith.
Then scan through the (n-1) candidates remaining, and if a candidate
pairwise beats or ties any member of the current smith set, move it to the
next position at the beginning of the list.  Keep scanning through the
remaining candidates until none of them beat or tie any member of the
current smith set, and then you're done.  Here's my Python implementation:

def smithWinners(p):
 "Given a pairwise matrix, return the list of candidates in the Smith Set"
 # Based on Steve Eppley's elegant Smith set algorithm from EM 28AP96
 candidates = len(p[0])
 candidateList = range(candidates)
 minDefeats = candidates
 for row in range(candidates):
  defeats = 0
  for col in range(candidates):
   if (p[row][col] < p[col][row]):
    defeats = defeats+1
  if (defeats <= minDefeats):
   if (defeats < minDefeats):
    minDefeats = defeats
    smithSetSize = 0
   candidateList[row] = candidateList[smithSetSize]
   candidateList[smithSetSize] = row
   smithSetSize = smithSetSize+1
 c1 = 0
 while (c1 < smithSetSize):
  row = candidateList[c1]
  for c2 in range(smithSetSize,candidates):
   col = candidateList[c2]
   if (p[row][col] <= p[col][row]):
    temp = candidateList[smithSetSize]
    candidateList[smithSetSize] = candidateList[c2]
    candidateList[c2] = temp
    smithSetSize = smithSetSize+1
  c1 = c1+1
 result = candidateList[0:smithSetSize]
 result.sort()
 return result

However, you can see that writing out this algorithm in the Constitution is
going to be a lot more cumbersome than simply defining what the Smith set
*is* in one or two sentences.