|
Re: Generalizations...
|
Bram Cohen
|
Apr 13, 2002 18:40 PDT
|
Blake Cretney wrote:
| | Let me suggest an alternate way of doing it. If the ballot ranks P over
Q, and x elected candidates come before P on the ballot, then instead of
contributing 1 vote to the P vs. Q comparison, the ballot contributes
1/(2x+1) votes. That is analogous to using the St. Lague rule of
proportional representation.
|
That technique has a certain aesthetic appeal, although I'm pretty sure
there are cases in which it fails horribly, which I shall explain.
The most difficult elections I've come up with for a PR system to solve
are what I'll call two-party problems. This is when there are two parties,
X and Y, each of which ranks all their ballots with all candidates for
their party followed by all candidates for the opposing party.
We would like, if there are N candidates getting elected, for X/N of them
to be from party X and Y/N of them to be from party Y, with the last
candidate going to the party which has the greatest remaining fraction.
This isn't particularly difficult to do when the members of a party all
rank all candidates in the same order, but becomes a major problem when
one of the parties is schizophrenic - that is, everyone ranks their
party's candidates in random order, or, worse, ranks them in cyclic order
with each succeeding votes starting one hop farther in the cycle.
Doing separate vote weakening for each already elected candidate, and
making sure each one of them weakens by exactly V/(N+1) votes, does a very
good job of handling these situations. Proving that it always handles them
properly appears tricky, but I've manually constructed a whole bunch of
instances and it's gotten the right answer in every instance I've tried (a
whole bunch of variants didn't.)
Notably, existing deployed PR systems are based on essentially the same
principle as the one I've given, and they mostly suffer from unfair
fascination with who one happens to have ranked exactly first. My
technique gets rid of the special place of the top slot, while still
adhering as much as possible to the design principles of older techniques.
-Bram Cohen
"Markets can remain irrational longer than you can remain solvent"
-- John Maynard Keynes
|
|
 |
|
