Analysis of the Minimax Procedure

Authors

Rob LeGrand, Washington University in St. Louis

Document Type

Technical Report

Publication Date

2004-11-02

Filename

wucse-2004-67.pdf

Technical Report Number

WUCSE-2004-67

Abstract

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K78S4N92

Recommended Citation

LeGrand, Rob, "Analysis of the Minimax Procedure" Report Number: WUCSE-2004-67 (2004). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/1036