Download The demexp Book - Linux

40.5
Condorcet ambiguity resolution
The first approach to find a winner in an ambiguous pairwise matrix is to drop the weakest (i.e.
smallest magnitude) defeat until one of the candidate is unbeaten. The following code applies
this algorithm, given a pairwise matrix mat.
The used algorithm is as follow:
• we build the ordered list of defeats
• in this list, if we can find a unique candidate (using get unbeaten) which is not beaten by
others, then we have our winner. Otherwise, we remove the head element on the defeat
list (i.e. the weakest defeat) and continue recursively through find winner.
condorcet winner raises Not found exception only if pairwise matrix mat is of zero size.
In that case, no winner can be found.
223
hvoting.ml 219ai+≡
let condorcet_winner ˜mat =
let defeats = pairwise_matrix_to_ordered_defeats ˜mat in
let size = Array.length mat in
assert(size >= 0);
if size = 0 then raise Not_found;
let rec find_winner defeats =
match defeats with
| [] -> assert(false) (* this case should never happen *)
| _ :: defeats_tail ->
match get_unbeaten ˜size ˜defeats with
| [e] -> e
| _ -> find_winner defeats_tail in
find_winner defeats
223
/ 222c 224 .