Technical Report Number
Minimax is a recently proposed procedure for electing committees, but it cannot be applied without an understanding of its computational complexity and its susceptibility to manipulate. We examine two compelling variations of minimax and prove both to be NP-complete. We derive upper and lower bounds on the size of minimax winner set for a given election. We present a heuristic for calculating a minimax winner set and present experiments based on its use. Finally, we present a general strategy for manipulating a minimax election.
LeGrand, Rob, "Analysis of the Minimax Procedure" Report Number: WUCSE-2004-67 (2004). All Computer Science and Engineering Research.