Raph Frank wrote:
On Mon, Sep 1, 2008 at 10:58 PM, Kristofer Munsterhjelm
<[EMAIL PROTECTED]> wrote:
In multiwinner election situations (like CPO-STV), the randomness might make
the losers complain that they lost because the assembly that the
optimization algorithm stumbled on didn't include them, not because the
optimal assembly didn't include them. The "everyone may propose a solution"
approach would to some extent limit these complaints - those who won could
say "well, if you're on the optimal assembly, why didn't you calculate it
and submit it as proof?" - but not eliminate it altogether.
If there is a condorcet winner, then it should be OK. Each
party/candidate could submit a result. They could be quickly checked
against each other and the condorcet winner of those submitted
determined.
However, if there is a circular tie, would that still work? I guess
it depends if the method meets independence of irrelevant
alternatives, so that parties don't think "if I had submitted this
other result, then we would have won", unless that result is actually
superior to the previous winner. In which case, they should have paid
more for supercomputer resources.
That's a good point. Since Condorcet (like all other deterministic
methods) fails IIA, and because most Condorcet methods take more than
linear time, we have a problem.
Some methods could still work. Take minmax as an example: the winner is
the candidate whose worst pairwise defeat is the least. The various
factions could submit sets to be included in the test. There would be
some form of strategy which one may call "destructive strategy", where a
faction tries to remove a winner that's already in place by finding a
very bad pairwise defeat.
Another example that might work is MAM. Call a calculation of the
pairwise results of a set against all other sets submitted a "data
piece". Then whenever a data piece is submitted, the central checks if
it puts one set above another with a greater margin/amount of votes than
in the current ordering. For instance, if
A > B > C > D is locked, and the situation was
A > B: 10 (B > A: 3)
B > C: 8
C > D: 8
Then if a new candidate E is submitted and
A > E: 9
E > B: 9
then the ordering is updated to
A > E > B > C > D.
This can't be exhaustive, since the ordering alone requires lg((n choose
k)!) bits, and the full Condorcet matrix is (n choose k)^2. But maybe
it'll be good enough?
Some numbers: For picking 10 candidates out of 100: n choose k is about
10^13 or 2^44. log(n!) is about n log n - n + (log(n)/2) +
(log(2*pi)/2). For n = 2^44, binary log, 2^44 * 44 -2^44 + (44/2) +
(lg(2*pi)/2), about 2^49 bits, which is 2^46 bytes. That's 64 (binary)
terabytes just for the ordering. Clearly, in that case, we can forget an
exhaustive application of MAM, or holding the entire Condorcet matrix in
memory for that matter.
----
Election-Methods mailing list - see http://electorama.com/em for list info
