Algorithm::Voting::Sortition - implements RFC 3797, "Publicly Verifiable

Algorithm-Voting documentation Contained in the Algorithm-Voting distribution.

Index

Code Index:

NAME

Top

Algorithm::Voting::Sortition - implements RFC 3797, "Publicly Verifiable Nominations Committee (NomCom) Random Selection"

SYNOPSIS

Top

To choose two of our favorite Hogwarts pals via sortition:

    use Algorithm::Voting::Sortition;

    # choose a list of candidates
    my @candidates = qw/
        Harry Hermione Ron Neville Albus
	Severus Ginny Hagrid Fred George
    /;

    # the results of our predetermined entropy source
    my @keysource = (
        [32,40,43,49,53,21],  # 8/9/08 powerball numbers
        "W 4-1",              # final score of 8/8/08 Twins game
    );

    # use sortition to determine the winners
    my $race = Algorithm::Voting::Sortition->new(
        candidates => \@candidates,
        source     => \@keysource,
        n          => 2,
    );
    printf "Key string is: '%s'\n", $race->keystring;
    print $race->as_string;

DESCRIPTION

Top

Sortition is an unbiased method for "drawing straws" or "casting lots". This package implements the Sortition algorithm as described in RFC 3797, "Publicly Verifiable Nominations Committee (NomCom) Random Selection" (http://tools.ietf.org/html/rfc3797):

This document describes a method for making random selections in such a way that the unbiased nature of the choice is publicly verifiable. As an example, the selection of the voting members of the IETF Nominations Committee (NomCom) from the pool of eligible volunteers is used. Similar techniques would be applicable to other cases.

METHODS

Top

Algorithm::Voting::Sortition->new( %args )

Constructs a new sortition object.

Example:

    my $s = Algorithm::Voting::Sortition->new(
        candidates => [ 'A' .. 'Z' ],
        n          => 3,
        source     => [ $scalar, \@array, \%hash ],
    );

$obj->candidates

Returns a list containing the current candidates.

$obj->n

Returns the number of candidates that are to be chosen from the master list. If n is unspecified when the sortition object is constructed, the total number of candidates is used, i.e. the sortition will return a list containing all candidates.

$obj->source()

Mutates the entropy source to be used in the sortition.

Example:

    $obj->source(@entropy); # sets the entropy value
    my @e = $obj->source;   # retrieves the entropy

$obj->keystring()

Uses the current value of $self->source to create and cache a master "key string".

$obj->make_keystring(@source)

Creates a "key string" from the input values in @source.

$obj->stringify($thing)

Converts $thing into a string. $thing can be a scalar, an arrayref, or a hashref. If $thing is anything else, this method die()s.

$class->_sort(@items)

Returns a list containing the values of @items, but sorted. Sorts numerically if @items contains only numbers (according to Scalar::Util::looks_like_number()), otherwise sorts lexically.

$obj->digest($n)

Calculates and returns the nth digest of the current keystring. This is done by bracketing $obj->keystring with a "stringified" version of $n, then calculating the MD5 digest of the result.

The value returned is a 32-character string containing the checksum in hexadecimal format.

$obj->seq

Returns a list of integers based on the dynamic keystring digest. These integers will be used will be used to choose the winners from the candidate pool.

$obj->result

Returns a data structure containing the contest results. For sortition, the structure is a list of candidates, with the first winner at list position 0, etc.

$obj->as_string

Returns the election results, formatted as a multiline string.

Algorithm-Voting documentation Contained in the Algorithm-Voting distribution. 
# $Id: Sortition.pm 60 2008-09-02 12:11:49Z johntrammell $
# $URL: https://algorithm-voting.googlecode.com/svn/tags/rel-0.01-1/lib/Algorithm/Voting/Sortition.pm $

package Algorithm::Voting::Sortition;

use strict;
use warnings;
use Scalar::Util qw/reftype looks_like_number/;
use Digest::MD5;
use Math::BigInt;
use Params::Validate 'validate';
use base 'Class::Accessor::Fast';


sub new {
    my $class = shift;
    my %valid = (
        candidates => 1,
        n          => { default => -1 },
        source     => 0,
        keystring  => 0,
    );
    my %args = validate(@_, \%valid);
    return bless \%args, $class;
}


sub candidates {
    return @{ $_[0]->{candidates} };
}


sub n {
    my $self = shift;
    if ($self->{n} < 1) {
        $self->{n} = scalar($self->candidates);
    }
    return $self->{n};
}


sub source {
    my $self = shift;
    if (@_) { $self->{source} = \@_; }
    return @{ $self->{source} };
}


sub keystring {
    my $self = shift;
    unless (exists $self->{keystring}) {
        $self->{keystring} = $self->make_keystring($self->source);
    }
    return $self->{keystring};
}


sub make_keystring {
    my ($self,@source) = @_;
    return join q(), map { $self->stringify($_) . q(/) } @source;
}


sub stringify {
    my ($self, $thing) = @_;
    if (reftype($thing)) {
        if (reftype($thing) eq 'ARRAY') {
            return join q(), map { "$_." } $self->_sort(@$thing);
        }
        elsif (reftype($thing) eq 'HASH') {
            return join q(),
                map { $_ . q(:) . $thing->{$_} . q(.) }
                $self->_sort(keys %$thing);
        }
        else {
            die "Can't stringify: $thing";
        }
    }
    else {
        return "$thing.";
    }
}


sub _sort {
    my ($class, @items) = @_;
    if (grep { !looks_like_number($_) } @items) {
        return sort @items;
    }
    else {
        return sort { $a <=> $b } @items;
    }
}


sub digest {
    my ($self, $n) = @_;
    my $pre = pack("n",$n);     # "n" => little-endian, 2-byte ("short int")
    return Digest::MD5::md5_hex($pre . $self->keystring . $pre);
}


sub seq {
    my $self = shift;
    return map {
        my $hex = $self->digest($_);
        my $i = Math::BigInt->new("0x${hex}");
        if ($i->is_nan) {
            die("got invalid hex from digest($_): '$hex'");
        }
        $i;
    } 0 .. $self->n - 1;
}


sub result {
    my $self = shift;
    my $n = $self->n;
    my @seq = $self->seq;
    my @candidates = $self->candidates;
    my @result;
    while ($n) {
        my $j = shift @seq;
        $j->bmod(scalar @candidates);   # modifies $j
        # splice() out the chosen candidate into @result
        push @result, splice(@candidates, $j, 1);
        $n--;
    }
    return @result;
}


sub as_string {
    my $self = shift;
    my $i = 0;
    my $str = qq(Keystring: "@{[ $self->keystring]}"\n);
    $str .= join q(), map { $i++; "$i. $_\n" } $self->result;
    return $str;
}

1;