[EM] A computationally feasible method

[Kristofer Munsterhjelm]

Raph Frank wrote:
> On Mon, Sep 1, 2008 at 10:58 PM, Kristofer Munsterhjelm
> <km-elmet at broadpark.no> 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.