The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Voting-Condorcet-RankedPairs-1.01
River stage zero No dependents
++
/ Voting::Condorcet::RankedPairs

NAME

Voting::Condorcet::RankedPairs - Ranked Pairs voting resolution.

SYNOPSIS

  use Voting::Condorcet::RankedPairs;

  my $rp = Voting::Condorcet::RankedPairs->new();

  $rp->add('Alice', 'Bob', 0.7);        # Alice got 70% votes, Bob 30%
  $rp->add('Alice', 'Eve', 0.4);        # Alice got 40% votes, Eve 60%

  my $winner    = $rp->winner;          # The winner, ignores ties.
  my @winners   = $rp->strict_winners;  # All winners, allows ties.

  my @rankings  = $rp->rankings;        # All entries, best to worst.
  my @rankings2 = $rp->strict_rankings; # All entries, allowing ties.

  my @better = $rp->better_than('Alice'); # Entries significantly better
                                          # than Alice.

  my @worse  = $rp->worse_than('Alice');  # Entries significantly worse
                                          # than Alice.

  my $graph  = $rp->graph;              # Underlying Graph object used.
                                        # (Advanced users only)

  $rp->compile;                         # Force graph compilation.
                                        # (Advanced users only)

DESCRIPTION

This module implements a Ranked Pairs Condorcet voting system, as described at http://en.wikipedia.org/wiki/Ranked_Pairs.

Ranked pairs uses a directed graph to determine the winner and rankings from a series of pairwise comparisons.

new

   my $rp  = Voting::Condorcet::RankedPairs->new();
   my $rp2 = Voting::Condorcet::RankedPairs->new(ordered_input => 1);

This method creates a new Ranked Pairs object. The ordered_input option, if set, allows the module to perform a number of time and space optimisations, but requires that data be added in strict most-significant to least-significant order.

add

  $rp->add('Alice','Bob',0.7);  # Alice vs Bob, Alice gets 70% votes
  $rp->add('Bob','Eve',0.4);    # Bob vs Eve,   Bob gets only 40% votes

This method adds the results of a pairwise contest. It always takes exactly three arguments: the two contestants, and a fractional number between 0 and 1 indicating the number of votes in favour of the first contestant.

A score of 0.5 indicates a tie, a score of 1.00 would indicate all votes fell to the first contestant, and a score of 0.00 would indicate all votes fell to the second.

If ordered_input was set when the object was created, then contests must be added in order of most relevance (scores furthest from 0.50) to least relevance (scores closest to 0.50). Adding scores out of order when ordered_input is set will result in an exception.

Scores of exactly 0.5 result in the contestants being added to the graph, but no edge being drawn.

winner

  my $winner = $rp->winner;

This returns the 'winner' of the competition. This always returns a single result, and does not check for draws. Use strict_winners (below) if a draw may exist.

strict_winners

  my @winners = $rp->strict_winners;

In some cirumstances two or more entries can be considered a draw. This method returns an array to all the winners of a contest. In most circumstances this will be a single entry.

rankings

   my @results = $rp->rankings;

This method returns an ordered list of contestents, with the winner in position 0. Ties are ignored; if two or more entries are tied they will be returned adjacent to each other, but in an indeterminate sequence. Use strict_rankings if tie detection is required.

strict_rankings

  my @results = $rp->strict_rankings;

This method returns an ordered list of lists. Each element contains a reference to all contestants at that position. This will usually be a single element, but may contain multiple entries in the case of draws.

better_than

  my @higher_ranked = $rp->better_than("Alice");

This function returns all the nodes that directly beat the given node with significance. In terms of graphs, these are all the nodes that have the given node as its destination (ie, its predecessors).

worse_than

  my @lower_ranked = $rp->worse_than("Alice");

This function returns all nodes that are directly beaten by the given node. In terms of graphs, these are the nodes successors.

compile

  $rp->compile;

This method will construct the underlying graph needed to find results. This method has no effect if the object was created with ordered_input set to true.

Normally there is no need to call this method by hand. It is automatically from any function that needs a compiled graph.

graph

  my $graph = $rp->graph;

Returns the underlying Graph object used. This isn't a copy of the object, it is the object, so be careful if you plan on making changes to it.

BUGS

Calling any method besides from add will cause the graph to be compiled, at which point any significant edges become "locked". Adding edges after this point will result in them being considered less significant than any edges present at the time of the compile, regardless of their majority.

Rankings are obtained by repeatedly removing source nodes from the graph. An alternate (but much slower) way of producing rankings would be to recompile the entire graph without those nodes entirely. In some circumstances this may produce different results for the runner-ups.

This is not a definitive list of bugs.

SEE ALSO

The Graph module.

http://en.wikipedia.org/wiki/Ranked_Pairs - Wikipedia article on Ranked Pairs.

http://condorcet.org/rp/ - Ranked Pairs discussion at Condorcet.org

http://en.wikipedia.org/wiki/Condorcet_method - Description of condorcet methods.

AUTHOR

Paul Fenwick, <pjf@cpan.org>

COPYRIGHT AND LICENSE

Copyright (C) 2007 by Paul Fenwick

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.4 or, at your option, any later version of Perl 5 you may have available.