[EM] pseudocode for Woodall's DSC method
Kevin Venzke
stepjak at yahoo.fr
Wed Jan 3 19:00:30 PST 2007
Hello,
Douglas Woodall's Descending Solid Coalitions method is a method that
satisfies clone independence, majority for solid coalitions, Plurality,
Later-no-harm, monotonicity, and participation. I don't know of any other
method which satisfies this combination of properties.
Because DSC works by assigning scores to sets of candidates, it isn't
necessarily obvious how to implement it. So here is some pseudocode I've
written. I hope it will be useful to someone.
I don't believe this code can be easily modified to perform DAC. The
"ballot analysis" section would be more complicated.
Kevin Venzke
Pseudocode implementation of DSC. Ties in set or candidate strength are
resolved randomly.
variables:
nc: the number of candidates
nv: the number of voters
sc(0 to (2^nc)-1, 1 to 3): two-dimensional integer array
dqd(1 to nc): boolean array
v(1 to nv, 1 to nc): two-dimensional integer array
cr(1 to nc): integer array
v contains the ballots. v(1,1) must hold the first preference of the first
voter. v(nv,nc) holds the last preference of the last voter. A preference
is a number from 1 to nc inclusive, representing a candidate. The final
preferences on a ballot may be 0, to indicate truncation.
Equal ranking isn't implemented, but it is not good strategy under DSC
anyway.
// Initialization:
FOR i=1 TO nc
dqd(i) = false
cr(i) = rnd
NEXT i
FOR i=0 TO (2 ^ nc) - 1
sc(i,1) = i
sc(i,2) = 0
sc(i,3) = rnd
NEXT i
Suppose above that "rnd" generates random integers.
// Ballot analysis:
FOR i = 1 TO nv
currentset = 0
FOR j = 1 TO nc
IF v(i,j) > 0 THEN
currentset += 2 ^ (v(i, j) - 1)
sc(currentset, 2)++
ENDIF
NEXT j
NEXT i
Insert a sort of sc here, such that in the result
sc(i,2) >= sc(i+1,2)
and
sc(i,2) <> sc(i+1,2) or sc(i,3) >= sc(i+1,3)
where of course i is less than (2^nc)-1.
// Coalition analysis:
FOR i = 0 TO (2 ^ nc) - 1
FOR j = 1 TO nc
IF dqd(j) = false AND (sc(i, 1) / (2 ^ (j - 1))) % 2 = 1 THEN
FOR k = 1 TO nc
IF (sc(i, 1) / (2 ^ (k - 1))) % 2 = 0 THEN dqd(k) = true
NEXT k
END IF
NEXT j
NEXT i
Above, / means integer division, and % takes the remainder of a division.
//Go back and find who won:
bestc = 0
bestr = 0
FOR i = 1 TO nc
IF dqd(i) = false THEN
IF bestc = 0 OR cr(i) > bestr THEN
bestc = i
bestr = cr(i)
END IF
END IF
NEXT i
bestc is the winner of the method.
A tie in the above section is probably impossible, but I left in a
tiebreaker in case a different approach to breaking ties in coalition
strength were implemented.
(end)
__________________________________________________
Do You Yahoo!?
En finir avec le spam? Yahoo! Mail vous offre la meilleure protection possible contre les messages non sollicités
http://mail.yahoo.fr Yahoo! Mail
More information about the Election-Methods
mailing list