Cloneproof Condorcet SSD [by Mike Ossipoff and Russ Paielli]

readme.md

From http://web.archive.org/web/20041211074628/http://electionmethods.org/CondorcetSSD.py

CondorcetSSD.py

#!/usr/bin/env python

# Copyright (C) 2002 by Mike Ossipoff and Russ Paielli

# version 1.0 - released 2002-02-14
# version 1.01 - released 2002-08-24 -- comments revised slightly
# version 1.02 - released 2004-02-14 -- comments revised slightly

# See http://ElectionMethods.org/CondorcetSSD.py for updates.
# See http://ElectionMethods.org for related informatioin.

# This python script implements the Cloneproof Condorcet SSD (Schwartz
# Sequential Dropping) voting algorithm and provides associated
# input/output utilities. The Condorcet SSD algorithm is known to be
# equivalent to the Condorcet Beatpath Winner algorithm, and we consider
# it the state of the art single-winner voting algorithm. Mike Ossipoff
# provided the algorithm, and Russ Paielli programmed it. To use it,
# type

# CondorcetSSD.py <input> <output>

# where <input> is the input file, and <output> is the output file. The
# command-line arguments are optional. If <output> is omitted, the
# output will go to the standard output. If <input> is omitted, the
# input will come from the standard input. A valid input file specifies
# the pairwise voting matrix in the following format:

# .SUM  Smith:   0  44  83
# .SUM  Jones:  49   0  29
# .SUM  Brown:  93  75   0

# Note that the ".SUM" keyword must start in the first column, otherwise
# spacing and column alignment is arbitrary. The column ordering
# corresponds to the row ordering, of course. For example, Smith got 44
# votes over Jones, and Brown got 93 votes over Smith in the example
# above. This format is the standard output format of GVI: The Graphical
# Voter Interface <http://ElectionMethods.org/GVI.htm>. This script can
# also handle the standard GVI format for full candidate names and
# parties.

# This script can be used interactively by omitting the input file and
# entering the pairwise matrix from the standard input (the keyboard).
# In that case, the .SUM keywords must be omitted, and the completed
# pairwise matrix is entered by typing "<control>-d" (hold down the
# "control" key and type "d", without quotes).

# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or (at
# your option) any later version. See "license" file for details or see
# <http://www.gnu.org/licenses/gpl.txt>.

# This program is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# General Public License for more details.

from sys import exit, argv, stdin, stdout

def CondorcetSSD ( Pmat, debug=0, output=stdout ): # Condorcet voting
    # algorithm with Schwartz Sequential Dropping (SSD)

    # Pmat: pairwise voting matrix (input)
    # Pmat[i,j]: number of votes ranking candidate i over candidate j

    nc = Pmat['nc'] # number of candidates

    # Initialize the defeats matrix: Def[i,j] gives the magnitude of i's
    # defeat of j. If i doesn't defeat j, then Def[i,j] == 0.

    Def = Pmat.copy()

    for i in range(nc):
        for j in range(i):
            if Pmat[i,j] >  Pmat[j,i]: Def[j,i] = 0
            if Pmat[i,j] <  Pmat[j,i]: Def[i,j] = 0
            if Pmat[i,j] == Pmat[j,i]: Def[i,j] = Def[j,i] = 0

    if debug: print ("\n--- begin CondorcetSSD debug printout ---")
    if debug: printPairMat ( Def, output )

    # Determine "beatpath" magnitudes array: Def[i,j] will be the
    # maximum beatpath magnitudes array. The i,j entry is the greatest
    # magnitude of any beatpath from i to j. A beatpath's magnitude is
    # the magnitude of its weakest defeat.

    def min ( x, y ):
        if x < y: return x
        else: return y

    changing = 1

    while changing:

        changing = 0

        for i in range(nc):
            for j in range(nc):
                for k in range(nc):

                    dmin = min ( Def[i,j], Def[j,k] )

                    if Def[i,k] < dmin:
                        Def[i,k] = dmin
                        changing = 1

                        if debug:
                            print >> output, "i,j,k =", i,j,k
                            printPairMat ( Def, output )

    win={} # an array for marking the winner (or winners if tied)

    for i in range(nc):
        win[i] = 1
        for j in range(nc):
            if Def[j,i] > Def[i,j]: win[i] = 0

    winners=[] # a list containing the winner (or winners if tied)

    for i in range(nc):
        if win[i] == 1: winners.append ( Pmat['cand',i] )

    if debug: print ("--- end CondorcetSSD debug printout ---\n")

    return winners

def readPairMat ( input=stdin ): # read pairwise matrix

    Pmat = { 'title': None, 'nc': 0, 'fullnames': 0 }
    nc = 0 # number of candidates (to be determined)
    i = 0 # pairwise matrix row index
    k = 0 # candidate name index

    while 1:

        line = input.readline()
        if len(line) == 0: # end of file
            if i == 0: exit ("error: data (or .SUM keyword) not found")
            if i < nc: exit ("error: more columns than rows")
            break

        if line.startswith (".TITLE "):
            Pmat['title'] = line
            continue

        if line.startswith (".CANDIDATE "):
            Pmat['fullnames'] = 1
            Pmat['candidate',k] = line
            line = line.replace ( ".CANDIDATE ", "", 1 ) # strip ".CANDIDATE"
            row = line.split(":",1)
            if len(row) != 2:
                exit ("error: missing colon after candidate name")
            cand = row[0].strip()
            name = row[1].strip()
            Pmat['cand',k] = cand # store candidate name (or code)
            Pmat['name',k] = name
            Pmat['fullname',cand] = name
            Pmat[cand] = k
            k += 1
            continue

        if input.name != "<stdin>":
            if not line.startswith (".SUM "): continue

        row = line.split() # split line into a list

        if row[0] == ".SUM": del row[0] # delete ".SUM" keyword
        if row[0][-1:] != ":":
            exit ("error: missing colon after candidate name")
        cand = row[0][:-1]
        Pmat['cand',i] = cand # store candidate name (or code)

        if Pmat['fullnames']:
            if not Pmat.has_key(cand):
                exit ("error: data given for unlisted candidate")
            if Pmat[cand] != i:
                exit ("error: candidate listed out of order")
        else: Pmat['fullname',cand] = cand

        del row[0]

        if nc == 0:
            nc = len(row)
            Pmat['nc'] = nc
        else:
            if len(row) != nc: exit ("error: wrong number of columns")

        if i >= nc: exit ("error: more rows than columns")

        for j in range(nc): Pmat[i,j] = int(row[j])
        if Pmat[i,i] != 0: exit ("error: nonzero diagonal element")
        i += 1

    return Pmat

def printPairMat ( Pmat, output=stdout ): # print pairwise matrix

    nc = Pmat['nc'] # number of candidates

    for i in range(nc):
        print >> output, ""
        print >> output, "%12s: " % Pmat['cand',i],
        for j in range(nc):
            print >> output, "%4i " % Pmat[i,j],
    print >> output, "\n"

def printResults ( winners, output=stdout ):

    if Pmat['title']: print >> output, Pmat['title']

    if Pmat['fullnames']:
        for i in range(Pmat['nc']):
            print Pmat['candidate',i],

    printPairMat ( Pmat )

    if len(winners) == 1:
        print >> output, ".WINNER", Pmat['fullname',winners[0]]
    else:
        for winner in winners: print >> output, ".TIE", winner
    print >> output

if __name__ == '__main__': # test driver

    input = stdin
    output = stdout

    if len(argv) > 1: input = open ( argv[1] )
    if len(argv) > 2: output = open ( argv[2],"w")

    Pmat = readPairMat ( input )

    printResults ( CondorcetSSD ( Pmat, 0, output ), output )