|
Re: Generalizations...
|
Bram Cohen
|
Apr 12, 2002 23:16 PDT
|
Stéphane Rouillon wrote:
| | I have read your archives (yes all of it !) and I am
particulary interested by the weighted version of ranked
pairs proposed by Mr. Bram Cohen, if I am not wrong.
1) Could someone summarize how it works with words
not with the code to help me understand it better?
|
I've actually got a better method than the last one I described, so I'll
take a stab at summarizing it now.
You elect candidates one at a time, each time choosing the next winner out
of the remaining set by ranked pairs.
The first candidate is picked by ordinary ranked pairs. The second
candidate is again picked by using the ranked pairs algorithm on pairwise
scores, but the calculation of pairwise scores is altered based on the
already selected candidates and where they appear in everybody's ballots.
Let us say that there are N candidates to be selected, using V votes. Each
already selected candidate will weaken existing votes by V/(N+1). Let us
say that we are comparing candidates P and Q, after A has already
been selected. To do this, we figure out all votes for which A is ranked
higher than both P and Q, say there are x of them. We then reduce the
strength of each of these votes by x/(V/(N+1)). We then repeat for all
other already elected candidates. In the end, each vote will have some
remaining strength, and we can add up the strength of all of those which
ranked P first and all of those which ranked Q first and see which is
greater.
Note that the strength of each vote can be different for each pair
comparison after every candidate is elected.
So far, I've written an implementation of this using minmax instead of
ranked pairs, because that was easier and I haven't gotten around to doing
it properly yet. With completely random votes, with large numbers of
candidates elected, occasionally this results in some votes having
negative strength for the next to last candidate or so. I suspect this
problem will go away when using ranked pairs instead.
If my above suspicion holds, then this technique has the quite nice
property that it wouldn't be necessary to actually remember all votes,
merely the number of times each ordered triplet (A, B, C) has appeared in
some ballot in that order thus far. This allows for vote collation, the
source of most of first past the post's logistical advantages, and also a
good technique for increasing voter privacy.
Many questions about this technique remain, including -
- Does my above conjecture hold? (I think it does.)
- Is it possible for electing N+1 candidates with the same votes to result
in a set of winners which is not a superset of electing N candidates? (I
suspect not.)
- How does this technique fare in terms of various forms of
gameability? (I suspect exraordinarily well.)
- How should one deal with the unranked candidates which are all
essentially tied for last place on peoples's ballots?
I have code written which implements this technique, although it uses
minmax instead of ranked pairs. It can be switched to ranked pairs without
rewriting the entire thing, just one portion. I'll send the code to anyone
who's interested.
| | 4) I think ranked pair is the best method, I have seen.
However, I would propose some additional generalizations.
First I need a solution that produce ranked weights to
replace an IRV-alike weigth procedure. I have developped
my own and I would like to compare with Mr. Cohen's work.
|
I'm very curious what your technique is as well.
Tideman has a procedure, but it's horrendously complicated and possibly
completely impractical to calculate in practical elections, and doesn't
support collation. Although he did run it on a bunch of real-world
election samples and found it gives very different results than other
techniques in several very thorny elections.
| | 6) Finally, I think ties could be handled differently.
I will tell you all about it, after you get a first occasion to comment.
|
I think in practice tiebreaks thankfully almost never have to be done.
-Bram Cohen
"Markets can remain irrational longer than you can remain solvent"
-- John Maynard Keynes
|
|
 |
|
