[EM] Method space of 3-bloc, strictly-ranked scenarios

[Kristofer Munsterhjelm]

On 11/27/2016 12:00 AM, Kevin Venzke wrote:

> I can say part of the motivation for the 343 is to not have to do 
> simulations, and be able to exhaustively investigate a method. (Or at
> least its representation within the framework...)

You could do this in reverse, too. The problem would be something like:
given 100000 (or however many) different ballot sets and a bunch of
methods' results on these ballot sets, find eight of these so that the
methods, evaluated on these ten ballot sets, give as few duplicate
signatures as possible.

More formally, suppose the rows of a matrix M corresponds to methods and
the columns correspond to ballot sets, and M[i][j] is 0 if A won, 1 if B
won, and 2 if C won. Then pick eight (or 343 or ...) columns so that
there are as few duplicate row vectors as possible when you remove all
columns but those eight from the matrix.

This is properly speaking a set cover problem (and thus NP-hard), but it
can be approximated in many ways. The simplest greedy algorithm would
be: pick the column that breaks as many ties as possible, then pick the
next column that breaks as many ties of those that remain, etc.