[EM] pseudocode for Woodall's DSC method

[Kevin Venzke]

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