Hello,
I spent some time implementing the voting mechanism as described
in Rauls draft. Maybe this is useful for somebody who wants to
play with the new voting system.
I append a preliminary version of the program here. The second
attachment is an example input file. The program is modelled
closely after the voting mechanics draft. It not meant to be
fast or efficient. My priority was to correctly implement the
behaviour as described by the current draft.
Some code is missing (see my other mails to this list). Questions,
which come into mind are:
1) Did I understand the voting draft correctly?
2) Is my implementation correct.
3) What should I fill in for the missing pieces.
I would be glad to receive comments about the program.
Jochen
--
Omm
(0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html
#! /usr/bin/env python
# vote.py - implement the voting mechanism form 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
import sys, fileinput
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 register_vote(str):
"""Feed a single vote into the data structures.
STR must be a word, composed of option letters.
The value AB, for example indicates that A is prefered
over everything, B is prefered over all unlisted options,
and all unlisted options are equal."""
for o in str:
if not o in options: raise "invalid option '%s'"%o
for i in range(0,len(str)-1):
o1=str[i]
for o2 in str[i+1:]: votecount[o1+o2]+=1
for o2 in options:
if o2 in str: continue
for o1 in str: votecount[o1+o2]+=1
## Read the votes, either from stdin or from file.
for line in fileinput.input():
if line[0] == "#": continue
register_vote(line.strip())
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):
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 -> wins"%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 Schartz 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 ()
# TODO: something is missing here (ties and such)
# 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 -> wins"%o
sys.exit(0)
ADB BC CBXD BD XADC DXBAC ABDC BXDC AXDB BXDA CABD DBCXA ADBC DXA ACBD BC CADB XBDC ACBXD BCA ADCB BCA DACXB CAB DB DABXC CAB BC CXDBA ACXDB BCD ACB ACB XCA CAD CBAXD ADCB DBAC AXD BD DCXA DBCXA DBCA XBAD DAB CAD DBXCA AXCDB CABD CDAB
Attachment:
pgpi2hO8GBkd6.pgp
Description: PGP signature