[EM] A computationally feasible method

[Raph Frank]

On 9/2/08, Kristofer Munsterhjelm <km-elmet at broadpark.no> wrote:
>  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?

Should be OK.

The process could have multiple rounds.  After the first submission,
parties/candidates are allowed to submit another set of outcomes.

Also, the CPO-STV final result is not likely to differ from the
standard PR-STV method by more than say 1-2 seats out of a district of
10 and condorcet ties shouldn't be massive.  The shortcuts will likely
reduce the number of viable outcomes to a small number.

What about

1) Determine the standard PR-STV outcome
2) All candidates can submit an outcome
3) Determine the Smith set of the submitted outcomes
4) Winner is the outcome from 3) that defeats 1) by the largest amount

The equivalent single seat condorcet method would be

Winner is the member of the Smith set who defeats the IRV winner by
the largest margin.

Would that have strategy issues ?

A winning outcome could be displaced by submitting the remaining
outcomes of a Smith Set.


>         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.
>

I doubt there would be that much of a difference between candidates
and seats.  However, it is certainly true that there could be a large
search space.

If there are 5 seats and 10 candidates, then the total is 252, so isn't massive.