]> projects.mako.cc - selectricity/blob - lib/rubyvote/condorcet.rb
* Renamed graphs_controller to graph_controller.
[selectricity] / 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 tally_vote(vote=nil)
37
38     vote.each_with_index do |winner, index|
39       # only run through this if this *is* preferred to something
40       break if vote.length - 1 == index
41       losers = vote.last( vote.length - index )
42
43       losers.each do |loser|
44         next if winner == loser
45
46         @votes[winner] = Hash.new unless @votes.has_key?(winner)
47         @votes[loser] = Hash.new unless @votes.has_key?(loser)
48
49         if @votes[winner].has_key?(loser)
50           @votes[winner][loser] += 1
51         else
52           @votes[winner][loser] = 1
53         end
54
55         # make sure we have a comparable object
56         @votes[loser][winner] = 0 unless @votes[loser].has_key?( winner )
57
58         @candidates << loser unless @candidates.include?( loser )
59       end
60
61       @candidates << winner unless @candidates.include?( winner )
62     end
63   end
64
65   protected
66   def verify_vote(vote=nil)
67     vote.instance_of?( Array ) and
68       vote == vote.uniq
69   end
70   
71 end
72
73 class PureCondorcetVote < CondorcetVote
74   def result
75     PureCondorcetResult.new( self )
76   end
77 end
78
79 class CloneproofSSDVote < CondorcetVote
80   def result
81     CloneproofSSDResult.new( self )
82   end
83 end
84
85
86 ##################################################################
87 ## CondorcetResult Classes and SubClasses
88 ##
89 ## The CondorcetResult class is subclassed by the PureCondorcetResult
90 ## and the CloneproofSSDResult classes but should not be used
91 ## directly.
92
93 class CondorcetResult < ElectionResult
94   def initialize(voteobj=nil)
95     unless voteobj and voteobj.kind_of?( CondorcetVote )
96       raise ArgumentError, "You must pass a CondorcetVote array.", caller
97     end
98     super(voteobj)
99   end
100
101   def defeats(candidates=nil, votes=nil)
102     candidates = @election.candidates unless candidates
103     votes = @election.votes unless votes
104
105     defeats = Array.new
106     candidates.each do |candidate|
107       candidates.each do |challenger|
108         next if candidate == challenger
109         if votes[candidate][challenger] > votes[challenger][candidate]
110           defeats << [ candidate, challenger ]
111         end
112       end
113     end
114
115     defeats
116   end
117
118 end
119
120 class PureCondorcetResult < CondorcetResult
121   def initialize(voteobj=nil)
122     super(voteobj)
123     self.condorcet()
124   end
125
126   protected
127   def condorcet
128     votes = @election.votes
129     candidates = @election.candidates
130
131     victors = Hash.new
132     candidates.each do |candidate|
133       victors[candidate] = Array.new
134     end
135
136     self.defeats.each do |pair|
137       winner, loser = *pair
138       victors[winner] << loser
139     end
140
141     winners = @election.candidates.find_all do |candidate|
142         victors[candidate].length == @election.candidates.length - 1
143     end
144
145     @winners = winners if winners.length == 1
146   end
147 end
148
149 class CloneproofSSDResult < CondorcetResult
150   def initialize(voteobj=nil)
151     super(voteobj)
152     @winners = self.cpssd()
153   end
154
155   protected
156   def cpssd
157     votes = @election.votes
158     candidates = *@election.candidates
159
160     def in_schwartz_set?(candidate, candidates, transitive_defeats)
161       candidates.each do |challenger|
162         next if candidate == challenger
163
164         if transitive_defeats.include?( [ challenger, candidate ] ) and
165             not transitive_defeats.include?( [ candidate, challenger ] )
166           return false
167         end
168       end
169       return true
170     end
171
172     loop do
173
174       # see the array with the standard defeats
175       transitive_defeats = self.defeats(candidates, votes)
176
177       candidates.each do |cand1|
178         candidates.each do |cand2|
179           candidates.each do |cand3|
180             if transitive_defeats.include?( [ cand2, cand1 ] ) and
181                 transitive_defeats.include?( [ cand1, cand3 ] ) and
182                 not transitive_defeats.include?( [ cand2, cand3 ] ) and
183                 not cand2 == cand3
184               transitive_defeats << [ cand2, cand3 ]
185             end
186           end
187         end
188       end
189
190       schwartz_set = Array.new
191       candidates.each do |candidate|
192         if in_schwartz_set?(candidate, candidates, transitive_defeats)
193           schwartz_set << candidate
194         end
195       end
196
197       candidates = schwartz_set
198
199       # look through the schwartz set now for defeats
200       defeats = self.defeats(candidates, votes)
201       
202       # it's a tie or there's only one option
203       break if defeats.length == 0
204
205       def is_weaker_defeat?( pair1, pair2 )
206         votes = @election.votes
207         if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]]
208           return true
209         elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and
210             votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]]
211           return true
212         else
213           false
214         end
215       end
216       
217       defeats.sort! do |pair1, pair2|
218         if is_weaker_defeat?( pair1, pair2 ) 
219           +1
220         elsif is_weaker_defeat?( pair2, pair1 ) 
221           -1
222         else
223           0
224         end
225       end
226  
227       votes[defeats[0][0]][defeats[0][1]] = 0
228       votes[defeats[0][1]][defeats[0][0]] = 0
229       
230     end
231
232     return candidates
233   end
234
235 end

Benjamin Mako Hill || Want to submit a patch?