Hello,
in order to better understand our new voting draft,
I have completed a new version of my implementation of
the voting algorithm.
Changes are:
* New input format: you can now use the same input
file for my and Anthony Towns's implementation.
* The default option seems to be not required to
defeat itself.
* I implemented the mechanism to detect ties.
Did I understand this correctly?
With some (also appended) example input my program generates
the following output:
A B C D X
A - 27 24 29 29
B 22 - 25 29 28
C 25 24 - 30 32
D 21 21 19 - 30
X 21 22 18 18 -
the Schwartz set is { A, B, C }
proposition (A,C) is weakest -> eliminated
proposition (B,C) is weakest -> eliminated
A B C
A - 27 0
B 22 - 0
C 0 0 -
the Schwartz set is { A, C }
A C
A - 0
C 0 -
all options eliminated -> tie between A,C
Is this the outcome we want to have? Or should C be somehow
deleted before the second Schwartz set is calculated?
Comments are welcome,
Jochen
--
Omm
(0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html
#! /usr/bin/env python
# debian-vote - implement the voting mechanism from the Debian constitution
#
# Copyright 2002 Jochen Voss <voss@debian.org>
#
# 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.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
# $Id: debian-vote,v 1.2 2002/11/17 11:47:35 voss Exp $
import sys, fileinput, re
from copy import copy
options=['A', 'B', 'C', 'D', 'X']
default='X'
quorum={}
supermajority={}
# You may set some quorum or supermajority here, e.g.
#quorum['A']=15
#supermajority['B']=2.0/1.0
######################################################################
# 1. Each ballot orders the options being voted on in the order
# specified by the voter. If the voter does not rank some options,
# this means that the voter prefers all ranked options over the
# unlisted options. Any options unranked by the voter are treated
# as being equal to all other unranked options.
votecount={}
for o1 in options:
for o2 in options: votecount[o1+o2]=0
def print_propositions():
"Print the vote counts in tabular form."
print
print " ",
for o2 in options:
print " %3s"%o2,
print
for o1 in options:
print "%4s"%o1,
for o2 in options:
if o1==o2:
print " -",
else:
print " %3d"%votecount[o1+o2],
print
def is_prefered(x,y):
if x=="-": return False
if y=="-": return True
return x<y
def register_vote(str):
"""Feed a single vote into the data structures. STR must be a
string with one letter for each option. Each letter should either be
a digit (the rank for this option) or the character '-' (to place the
option after all ranked options)."""
if len(str)!=len(options):
raise "error: vote length %d does not match options count"%len(str)
for i in range(0,len(options)):
for j in range(0,len(options)):
if is_prefered(str[i],str[j]):
votecount[options[i]+options[j]]+=1
## Read the votes, either from stdin or from file.
vote_pattern=re.compile(r"^V:\s+(\S+)(\s+\S+|)$")
for line in fileinput.input():
m=vote_pattern.match(line)
if not m: continue
register_vote(m.group(1))
print_propositions()
######################################################################
# 2. Options which do not defeat the default option are eliminated.
# Definition: Option A defeats option B if more voters prefer A over B
# than prefer B over A.
def defeats(o1,o2):
return votecount[o1+o2]>votecount[o2+o1]
active=[]
for o in options:
if defeats(o,default) or o==default:
active.append(o)
else:
print "option %s does not defeat default option -> eliminated"%o
options=active
######################################################################
# 3. If an option has a quorum requirement, that option must defeat
# the default option by the number of votes specified in the quorum
# requirement, or the option is eliminated.
# TODO: is this correct?
def matches_quorum(o,q):
return votecount[o+default]>votecount[default+o]+q
active=[]
for o in options:
if (o not in quorum) or matches_quorum(o,quorum[o]):
active.append(o)
else:
print ("option %s does not match "%o
+ "the quorum requirement (%d)"%quorum[o]
+ " -> eliminated")
options=active
######################################################################
# 4. If an option has a supermajority requirement, that option must
# defeat the default option by the ratio of votes specified in the
# supermajority requirement, or the option is eliminated. That is,
# if a an option has a 2:1 supermajority requirement, then there
# must be twice as many votes which prefer that option over the
# default option than there are votes which prefer the default
# option over that option.
def matches_supermajority(o,q):
return votecount[o+default]>votecount[default+o]*q
active=[]
for o in options:
if (o not in supermajority) or matches_supermajority(o,supermajority[o]):
active.append(o)
else:
print ("option %s does not match "%o
+ "the supermajority requirement (%d)"%supermajority[o]
+ " -> eliminated")
options=active
######################################################################
# 5. If one remaining option defeats all other remaining options, that
# option wins.
for o in options:
if reduce(lambda x,o2: x and (o==o2 or defeats(o,o2)), options, True):
print "option %s defeats all other options -> %s wins"%(o,o)
sys.exit(0)
while True:
######################################################################
# 6. If more than one option remains after the above steps, we use
# Cloneproof Schwartz Sequential Dropping to eliminate any cyclic
# ambiguities and then pick the winner. This procedure and must be
# carried out in the following order:
# i. All options not in the Schwartz set are eliminated.
# Definition: An option C is in the Schwartz set if there is no other
# option D such that D transitively defeats C AND C does not
# transitively defeat D.
def is_in_schwartz_set(o):
for o2 in options:
if ((o2+o in transitive_defeats)
and (o+o2 not in transitive_defeats)): return False
return True
# Definition: An option F transitively defeats an option G if F
# defeats G or if there is some other option H where H defeats G
# AND F transitively defeats H.
# TODO: is the implementation correct?
transitive_defeats=[]
for o1 in options:
for o2 in options:
if defeats(o1,o2): transitive_defeats.append(o1+o2)
for i in options:
for j in options:
for k in options:
if (j+i in transitive_defeats
and i+k in transitive_defeats
and not j+k in transitive_defeats):
transitive_defeats.append(j+k)
options=filter(is_in_schwartz_set, options)
print "the Schwartz set is { "+", ".join(options)+" }"
# ii. Unless this would eliminate all options in the Schwartz set, the
# weakest propositions are eliminated.
# Definition: A proposition is a pair of options J and K from the
# Schwartz set which are considered along with the number of
# voters who prefer J to K and the number of voters who prefer K
# to J.
# Definition: The dominant strength of a proposition is the count of
# votes in a proposition which is not smaller than the other vote
# count in that proposition.
plist=[]
for i in range(0,len(options)-1):
o1=options[i]
for o2 in options[i+1:]:
s1=votecount[o1+o2]
s2=votecount[o2+o1]
if s1>s2:
plist.append((o1,o2,s1,s2))
else:
plist.append((o1,o2,s2,s1))
# Definition: a weak proposition is a proposition which has a dominant
# strength greater than zero and no larger than that of any other
# proposition.
# Definition: a weakest proposition is a weak proposition where the
# vote count in the proposition which is not larger than the other
# vote count is also no smaller than that of any other weak
# proposition.
plist=filter(lambda p:p[2]>0,plist)
def weakness(x,y):
res=(x[2]<y[2])-(x[2]>y[2])
if res: return res
return (x[3]>y[3])-(x[3]<y[3])
plist.sort(weakness)
if plist:
a=plist[-1][2]
b=plist[-1][3]
plist=filter(lambda p:p[2]==a and p[3]==b,plist)
# Definition: A proposition is eliminated by treating both of its vote
# counts as zero from this point forward.
for p in plist:
votecount[p[0]+p[1]]=0
votecount[p[1]+p[0]]=0
print "proposition (%s,%s) is weakest -> eliminated"%(p[0],p[1])
print_propositions ()
# iii. If eliminating the weakest propositions would eliminate all
# votes represented in the Schwartz set, a tie exists and the
# person with the casting vote picks from among the options
# represented in this Schwartz set.
if len(options)>1:
total_count=0
for o1 in options:
for o2 in options:
total_count += votecount[o1+o2]
if total_count==0:
print "all options eliminated -> tie between "+",".join(options)
if len(options)<3: sys.exit(0)
sys.exit(1)
# v. If this new set of propositions allows one option to defeat
# all other options in the Schwartz set, that option wins.
for o in options:
if reduce(lambda x,o2: x and (o==o2 or defeats(o,o2)), options, True):
print "option %s defeats all other options -> %s wins"%(o,o)
sys.exit(0)
V: 1--23 something V: 21345 something V: 1243- something V: 12534 something V: 4-123 something V: -4123 something V: 53214 something V: -4312 something V: 342-1 something V: 32-14 something V: 31452 something V: 3124- something V: 45123 something V: -3124 something V: 231-- something V: 23154 something V: 23415 something V: 412-3 something V: 12345 something V: --123 something V: 24351 something V: 15243 something V: 54213 something V: 45213 something V: 15324 something V: 31245 something V: 31524 something V: 25314 something V: 13425 something V: 324-1 something V: 25143 something V: 23--1 something V: -2341 something V: 42351 something V: 42135 something V: -1342 something V: 13254 something V: 45213 something V: 134-2 something V: 123-- something V: 321-4 something V: 32-14 something V: 54213 something V: 2314- something V: 32-14 something V: 1234- something V: 12354 something V: 12534 something V: -1-32 something V: 24153 something
Attachment:
pgpRgzdQ7n7Fv.pgp
Description: PGP signature