Condorcet votes can now properly handle votes expressing equivalency
[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   attr_accessor :results
37
38   def initialize(votes=nil)
39     unless defined?(@candidates)
40       @candidates = Array.new
41       votes.each do |vote_row|
42         vote_row = vote_row.flatten if vote_row.class == Array
43         vote_row.each do |vote| 
44           @candidates << vote unless @candidates.include?(vote)
45         end
46       end
47     end
48     super(votes)
49     @results = Array.new
50   end
51
52   def tally_vote(vote=nil)
53
54     vote.each_with_index do |winners, index|
55       if vote.flatten.length < @candidates.length
56         implied_losers = @candidates.select { |c| not vote.flatten.include?(c) }
57         vote.push(implied_losers)
58       end
59       if vote.length - 1 == index
60         losers = []
61       else
62         losers = vote.flatten.last( vote.flatten.length - index - 1)
63       end
64
65       losers.each do |place|
66         place = [place] unless place.class == Array
67         place.each do |loser|
68           
69           winners = [winners] unless winners.class == Array
70           next if winners.include?(loser)
71           winners.each do |winner|
72             @votes[winner] = Hash.new unless @votes.has_key?(winner)
73             @votes[loser] = Hash.new unless @votes.has_key?(loser)
74
75             if @votes[winner].has_key?(loser)
76               @votes[winner][loser] += 1
77             else
78               @votes[winner][loser] = 1
79             end
80
81             # make sure we have a comparable object
82             @votes[loser][winner] = 0 unless @votes[loser].has_key?( winner )
83           end
84         end
85       end
86     end
87   end
88
89   def results
90     if @results.size < 2 && (not @candidates.empty?)
91       tabulate
92     end
93     @results
94   end
95
96   def result
97     find_only_winner unless @winner
98     @winner
99   end
100
101   protected
102
103   def verify_vote(vote=nil)
104     vote.instance_of?( Array ) and
105       vote == vote.uniq
106   end
107
108   def tabulate
109     find_only_winner unless @winner
110     until @candidates.empty? 
111       aResult = resultFactory( self )
112       @results << aResult.winners
113       filter_out(aResult)
114     end
115   end
116
117   def find_only_winner
118     @winner = resultFactory( self )
119     @results << @winner.winners
120     filter_out(@winner)
121   end
122
123 end
124
125 class PureCondorcetVote < CondorcetVote
126   def resultFactory(init)
127     PureCondorcetResult.new(init)
128   end
129 end
130
131 class CloneproofSSDVote < CondorcetVote
132   def resultFactory(init)
133     CloneproofSSDResult.new(init)
134   end
135
136 end
137
138
139 ##################################################################
140 ## CondorcetResult Classes and SubClasses
141 ##
142 ## The CondorcetResult class is subclassed by the PureCondorcetResult
143 ## and the CloneproofSSDResult classes but should not be used
144 ## directly.
145
146 class CondorcetResult < ElectionResult
147   def initialize(voteobj=nil)
148     unless voteobj and voteobj.kind_of?( CondorcetVote )
149       raise ArgumentError, "You must pass a CondorcetVote array.", caller
150     end
151     super(voteobj)
152   end
153
154   protected
155
156   def defeats(candidates=nil, votes=nil)
157     candidates = @election.candidates unless candidates
158     votes = @election.votes unless votes
159
160     defeats = Array.new
161     candidates = [candidates] unless candidates.class == Array
162     candidates.each do |candidate|
163       candidates.each do |challenger|
164         next if candidate == challenger
165         if votes[candidate][challenger] > votes[challenger][candidate]
166           defeats << [ candidate, challenger ]
167         end
168       end
169     end
170
171     defeats
172   end
173
174 end
175
176 class PureCondorcetResult < CondorcetResult
177   def initialize(voteobj=nil)
178     super(voteobj)
179     self.condorcet()
180   end
181
182   protected
183
184   def condorcet
185     votes = @election.votes
186     candidates = @election.candidates
187
188     victors = Hash.new
189     candidates.each do |candidate|
190       victors[candidate] = Array.new
191     end
192
193     self.defeats.each do |pair|
194       winner, loser = *pair
195       victors[winner] << loser
196     end
197
198     victory_margin = 1
199     while true
200       winners = @election.candidates.find_all do |candidate|
201         victors[candidate].length == @election.candidates.length - victory_margin
202       end
203       if winners.length > 0
204         @winners = winners
205         return @winners
206       else
207         victory_margin += 1
208       end
209     end
210   end
211 end
212
213 class CloneproofSSDResult < CondorcetResult
214   def initialize(voteobj=nil)
215     super(voteobj)
216     @winners = self.cpssd()
217   end
218
219   protected
220
221   def cpssd
222     votes = @election.votes
223     candidates = *@election.candidates
224
225     def in_schwartz_set?(candidate, candidates, transitive_defeats)
226       candidates.each do |challenger|
227         next if candidate == challenger
228
229         if transitive_defeats.include?( [ challenger, candidate ] ) and
230             not transitive_defeats.include?( [ candidate, challenger ] )
231           return false
232         end
233       end
234       return true
235     end
236
237     loop do
238
239       # see the array with the standard defeats
240       transitive_defeats = self.defeats(candidates, votes)
241       defeats_hash = Hash.new
242       transitive_defeats.each { |td| defeats_hash[td] = 1 }
243
244       candidates = [candidates] unless candidates.class == Array
245       candidates.each do |cand1|
246         candidates.each do |cand2|
247           unless cand1 == cand2
248             candidates.each do |cand3|
249               if not cand2 == cand3 and 
250                   not cand1 == cand3 and 
251                   defeats_hash[[cand2, cand1]] and
252                   defeats_hash[[cand1, cand3]] and
253                   not defeats_hash[[cand2, cand3]] 
254                 transitive_defeats << [cand2, cand3]
255                 defeats_hash[[cand2, cand3]] = 1
256               end
257             end
258           end
259         end
260       end
261
262       schwartz_set = Array.new
263       candidates.each do |candidate|
264         if in_schwartz_set?(candidate, candidates, transitive_defeats)
265           schwartz_set << candidate
266         end
267       end
268
269       candidates = schwartz_set
270
271       # look through the schwartz set now for defeats
272       defeats = self.defeats(candidates, votes)
273       
274       # it's a tie or there's only one option
275       break if defeats.length == 0
276
277       def is_weaker_defeat?( pair1, pair2 )
278         votes = @election.votes
279         if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]]
280           return true
281         elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and
282             votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]]
283           return true
284         else
285           false
286         end
287       end
288       
289       defeats.sort! do |pair1, pair2|
290         if is_weaker_defeat?( pair1, pair2 ) 
291           +1
292         elsif is_weaker_defeat?( pair2, pair1 ) 
293           -1
294         else
295           0
296         end
297       end
298  
299       votes[defeats[0][0]][defeats[0][1]] = 0
300       votes[defeats[0][1]][defeats[0][0]] = 0
301       
302     end
303
304     return candidates
305   end
306
307 end

Benjamin Mako Hill || Want to submit a patch?