Monday, May 01, 2006

Condorcet Voting

Recently I have been interested in the Condorcet method of counting votes. More specifically the Schulze method. I find ranking based systems that can produce a clear winner in a single round of voting interesting. I'll let you do most of the background reading on Condorcet himself. What I really wanted to write about is my progress in making a condorcet vote counter in Common Lisp.

If you've been reading you may have noticed I've been learning lisp recently. This means I've spent more time figuring out something pretty simple and my coding style may leave somewhat to be desired. That said, on to the code...

(setf elections '(:ab (:a 0 :b 0 :label :ab) :ac (:a 0 :c 0 :label :ac)
:bc (:b 0 :c 0 :label :bc)))

(defmacro election-pair-label (elec var1 var2)
`(getf (car (remove-if-not
(lambda (x)
(and (not (atom x))
(not (eq (getf x ,var1) nil))
(not (eq (getf x ,var2) nil )))) ,elec)) :label))

(defun incvote (list winner loser)
(let ((lbl (election-pair-label list winner loser)))
(setf (getf (getf list lbl) winner) (1+ (getf (getf list lbl) winner)))))
Please forgive the indentation. If anyone knows how to get blogger to accept the HTML to do code listings please tell me. The obvious ones don't seem to work.

The first thing to look at is the elections list. This is where my style must be called into question. I don't know how to use remove-if-not such that it returns a setf-able place in the main struct.

The macro and function are pretty straight forward. I use the macro to get the label (:ab, :ac, or :bc). I then reference by the label to get a setf-able place in the elections list for doing the setf on the vote count.

It's a good first step. Presently I can just do (incvote elections :[winner] :[loser]) and it will increment the vote count for the winner candidate.

My next step will be to take a list in the form of (:b :c :a) and apply the votes to the pairwise elections in the elections list by way of Condorcet counting.

Stay tuned for more fun.



Zach Beane said...

Why not make election-pair-label a regular function? It doesn't do anything that requires it to be a macro.

Shaun said...

You're very correct. Admittedly, I'm still just practicing the use of macro syntax. I have yet to think of something that can't be handled by a function. I'll start using them better when I understand better what lends itself to using macros. Either way, more Practical Common Lisp reading is in order.