two variations of Condorcet-Schulze voting algorithms [by Russ Paielli]

readme.md

From http://web.archive.org/web/20050828022239/http://electionmethods.org/Condorcet.py

Condorcet.py

#!/usr/bin/env python

# alpha release 2005-02-04

# This python script by Russ Paielli implements two variations of
# Condorcet-Schulze voting algorithms and provides associated
# input/output utilities. To try it, type

# Condorcet.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. 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 (usually 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.

# 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 CondorcetSchulze ( PairMat, output=stdout, debug=0 ):
    "Condorcet-Schulze voting algorithm"

    # Markus Schulze, "A New Monotonic and Clone-Independent
    # Single-Winner Election Method," Voting Matters, issue 17, p. 9-19,
    # Oct 2003.

    # This function does NOT measure pairwise defeats of equal magnitude
    # by a secondary metric of margin of defeat. Although this function
    # is simpler than the "CondorcetSchulze2" function below, the latter
    # is recommended for small committee elections.

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

    if debug: printPairMat ( PairMat, output, "input matrix:")

    nc = PairMat['nc'] # number of candidates
    pmat = PairMat.copy() # "p" matrix in Schulze paper

    for i in range(nc):
        for j in range(nc):
            pmat[i,j] = PairMat[i,j] - PairMat[j,i]

    if debug: printPairMat ( pmat, output, "p matrix:")

    for i in range(nc):
        for j in range(nc):
            if i == j: continue
            for k in range(nc):
                if i == k: continue
                if j == k: continue

                s = min ( pmat[j,i], pmat[i,k] )
                if pmat[j,k] < s: pmat[j,k] = s

    if debug: printPairMat ( pmat, output, "p after Floyd algorithm:")

    win={} # array for potential winners (plural if tied)

    for i in range(nc):
        win[i] = 1
        for j in range(nc):
            if pmat[j,i] > pmat[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 ( PairMat['cand',i] )

    return winners

def CondorcetSchulze2 ( PairMat, output=stdout, debug=0 ):
    "Condorcet-Schulze voting algorithm"

    # Markus Schulze, "A New Monotonic and Clone-Independent
    # Single-Winner Election Method," Voting Matters, issue 17, p. 9-19,
    # Oct 2003.

    # This function measures pairwise defeats of equal magnitude by a
    # secondary metric of margin of defeat. Although more complicated
    # than the "CondorcetSchulze" function above, this function is
    # preferable for small committee elections.

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

    if debug: printPairMat ( PairMat, output, "input matrix:")

    nc = PairMat['nc'] # number of candidates
    p1 = PairMat.copy() # "p1" matrix in Schulze paper
    p2 = PairMat.copy() # "p2" matrix in Schulze paper

    for i in range(nc):
        for j in range(nc):
            p2[i,j] = PairMat[i,j] - PairMat[j,i]
            if PairMat[i,j] >  PairMat[j,i]: p1[i,j] = PairMat[i,j]
            if PairMat[i,j] <= PairMat[j,i]: p1[i,j] = -1

    if debug: printPairMat ( p1, output, "p1 matrix:")
    if debug: printPairMat ( p2, output, "p2 matrix:")

    for i in range(nc):
        for j in range(nc):
            if i == j: continue
            for k in range(nc):
                if i == k: continue
                if j == k: continue

                s = p1[j,i]
                t = p2[j,i]

                if p1[i,k] <= s and p2[i,k] < t:

                    s = p1[i,k]
                    t = p2[i,k]

                if p1[j,k] <= s and p2[j,k] < t:

                    p1[j,k] = s
                    p2[j,k] = t

    if debug: printPairMat ( p1, output, "p1 after Floyd algorithm:")
    if debug: printPairMat ( p2, output, "p2 after Floyd algorithm:")

    win={} # array for potential winners (plural if tied)

    for i in range(nc):
        win[i] = 1
        for j in range(nc):
            if p1[j,i] >  p1[i,j]: win[i] = 0
            if p1[j,i] == p1[i,j] and p2[j,i] > p2[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 ( PairMat['cand',i] )

    return winners

def readPairMat ( input=stdin ): # read pairwise matrix
    "read pairwise matrix and candidate names"

    PairMat = { '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 "):
            PairMat['title'] = line
            continue

        if line.startswith (".CANDIDATE "):
            PairMat['fullnames'] = 1
            PairMat['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()
            PairMat['cand',k] = cand # store candidate name (or code)
            PairMat['name',k] = name
            PairMat['fullname',cand] = name
            PairMat[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]
        PairMat['cand',i] = cand # store candidate name (or code)

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

        del row[0]

        if nc == 0:
            nc = len(row)
            PairMat['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): PairMat[i,j] = int(row[j])
        if PairMat[i,i] != 0: exit ("error: nonzero diagonal element")
        i += 1

    return PairMat

def printPairMat ( PairMat, output=stdout, label="Pairwise Matrix:"):
    "print pairwise voting matrix"

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

    print label

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

def printResults ( winners, output=stdout ):

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

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

    printPairMat ( PairMat )

    if len(winners) == 1:
        print >> output, ".WINNER", PairMat['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")

    PairMat = readPairMat ( input )

    printResults ( CondorcetSchulze ( PairMat, output, 1 ), output )