#filter_out and PureCondorcet weren't getting along well for sparse elections
[rubyvote] / lib / rubyvote / condorcet.rb
1 # election library -- a ruby library for elections
2 # copyright © 2005 MIT Media Lab and Benjamin Mako Hill
3
4 # This program is free software; you can redistribute it and/or modify
5 # it under the terms of the GNU General Public License as published by
6 # the Free Software Foundation; either version 2 of the License, or
7 # (at your option) any later version.
8
9 # This program is distributed in the hope that it will be useful, but
10 # WITHOUT ANY WARRANTY; without even the implied warranty of
11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 # General Public License for more details.
13
14 # You should have received a copy of the GNU General Public License
15 # along with this program; if not, write to the Free Software
16 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17 # 02110-1301, USA.
18
19 #################################################################
20 ## ==== condorcet.rb ====
21 ##
22 ## This file contains Condorcet election methods. Currently this
23 ## includes a pure condorcet and a CloneproofSSD implementation
24 ## modeled after the Python-based Debian project election code and
25 ## that gives the same results in several tested corner cases.
26 #################################################################
27
28 ##################################################################
29 ## CondorcetVote Classes and SubClasses
30 ##
31 ## The CondorcetVote class is subclassed by the PureCondorcetVote and
32 ## the CloneproofSSDVote classes but should not be used directly.
33
34 class CondorcetVote < ElectionVote
35
36   def initialize(votes=nil)
37     unless defined?(@candidates)
38       @candidates = Array.new
39       votes.each do |vote_row|
40         vote_row = vote_row.flatten if vote_row.class == Array
41         vote_row.each do |vote| 
42           @candidates << vote unless @candidates.include?(vote)
43         end
44       end
45     end
46     super(votes)
47   end
48
49   def tally_vote(vote=nil)
50
51     vote.each_with_index do |winner, index|
52       if vote.flatten.length < @candidates.length
53         implied_losers = @candidates.select { |c| not vote.include?(c) }
54         vote.push(implied_losers)
55       end
56       if vote.length - 1 == index
57         losers = []
58       else
59         losers = vote.flatten.last( vote.flatten.length - index - 1)
60       end
61
62       losers.each do |place|
63         place = [place] unless place.class == Array
64         place.each do |loser|
65           
66
67           @votes[winner] = Hash.new unless @votes.has_key?(winner)
68           @votes[loser] = Hash.new unless @votes.has_key?(loser)
69
70           if @votes[winner].has_key?(loser)
71             @votes[winner][loser] += 1
72           else
73             @votes[winner][loser] = 1
74           end
75
76           # make sure we have a comparable object
77           @votes[loser][winner] = 0 unless @votes[loser].has_key?( winner )
78         end
79       end
80     end
81   end
82
83   def result
84     resultFactory( self )
85   end
86
87   protected
88   def verify_vote(vote=nil)
89     vote.instance_of?( Array ) and
90       vote == vote.uniq
91   end
92
93 end
94
95 class PureCondorcetVote < CondorcetVote
96   def resultFactory(init)
97     PureCondorcetResult.new(init)
98   end
99 end
100
101 class CloneproofSSDVote < CondorcetVote
102   def resultFactory(init)
103     CloneproofSSDResult.new(init)
104   end
105
106   def result
107     top_result = resultFactory( self )
108     until @candidates.empty?
109       aResult = resultFactory( self )
110       top_result.full_results << aResult
111       filter_out(aResult)
112     end
113     top_result
114   end
115
116 end
117
118
119 ##################################################################
120 ## CondorcetResult Classes and SubClasses
121 ##
122 ## The CondorcetResult class is subclassed by the PureCondorcetResult
123 ## and the CloneproofSSDResult classes but should not be used
124 ## directly.
125
126 class CondorcetResult < ElectionResult
127   def initialize(voteobj=nil)
128     unless voteobj and voteobj.kind_of?( CondorcetVote )
129       raise ArgumentError, "You must pass a CondorcetVote array.", caller
130     end
131     super(voteobj)
132   end
133
134   protected
135   def defeats(candidates=nil, votes=nil)
136     candidates = @election.candidates unless candidates
137     votes = @election.votes unless votes
138
139     defeats = Array.new
140     candidates = [candidates] unless candidates.class == Array
141     candidates.each do |candidate|
142       candidates.each do |challenger|
143         next if candidate == challenger
144         if votes[candidate][challenger] > votes[challenger][candidate]
145           defeats << [ candidate, challenger ]
146         end
147       end
148     end
149
150     defeats
151   end
152
153 end
154
155 class PureCondorcetResult < CondorcetResult
156   def initialize(voteobj=nil)
157     super(voteobj)
158     self.condorcet()
159   end
160
161   protected
162   def condorcet
163     votes = @election.votes
164     candidates = @election.candidates
165
166     victors = Hash.new
167     candidates.each do |candidate|
168       victors[candidate] = Array.new
169     end
170
171     self.defeats.each do |pair|
172       winner, loser = *pair
173       victors[winner] << loser
174     end
175
176     winners = @election.candidates.find_all do |candidate|
177         victors[candidate].length == @election.candidates.length - 1
178     end
179
180     @winners << winners if winners.length == 1
181   end
182 end
183
184 class CloneproofSSDResult < CondorcetResult
185   def initialize(voteobj=nil)
186     super(voteobj)
187     @winners = self.cpssd()
188   end
189
190   protected
191   def cpssd
192     votes = @election.votes
193     candidates = *@election.candidates
194
195     def in_schwartz_set?(candidate, candidates, transitive_defeats)
196       candidates.each do |challenger|
197         next if candidate == challenger
198
199         if transitive_defeats.include?( [ challenger, candidate ] ) and
200             not transitive_defeats.include?( [ candidate, challenger ] )
201           return false
202         end
203       end
204       return true
205     end
206
207     loop do
208
209       # see the array with the standard defeats
210       transitive_defeats = self.defeats(candidates, votes)
211
212       candidates = [candidates] unless candidates.class == Array
213       candidates.each do |cand1|
214         candidates.each do |cand2|
215           candidates.each do |cand3|
216             if transitive_defeats.include?( [ cand2, cand1 ] ) and
217                 transitive_defeats.include?( [ cand1, cand3 ] ) and
218                 not transitive_defeats.include?( [ cand2, cand3 ] ) and
219                 not cand2 == cand3
220               transitive_defeats << [ cand2, cand3 ]
221             end
222           end
223         end
224       end
225
226       schwartz_set = Array.new
227       candidates.each do |candidate|
228         if in_schwartz_set?(candidate, candidates, transitive_defeats)
229           schwartz_set << candidate
230         end
231       end
232
233       candidates = schwartz_set
234
235       # look through the schwartz set now for defeats
236       defeats = self.defeats(candidates, votes)
237       
238       # it's a tie or there's only one option
239       break if defeats.length == 0
240
241       def is_weaker_defeat?( pair1, pair2 )
242         votes = @election.votes
243         if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]]
244           return true
245         elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and
246             votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]]
247           return true
248         else
249           false
250         end
251       end
252       
253       defeats.sort! do |pair1, pair2|
254         if is_weaker_defeat?( pair1, pair2 ) 
255           +1
256         elsif is_weaker_defeat?( pair2, pair1 ) 
257           -1
258         else
259           0
260         end
261       end
262  
263       votes[defeats[0][0]][defeats[0][1]] = 0
264       votes[defeats[0][1]][defeats[0][0]] = 0
265       
266     end
267
268     return candidates
269   end
270
271 end

Benjamin Mako Hill || Want to submit a patch?