Minimax approval
Minimax approval is a consensus Approval multiwinner method devised by Brams, Kilgour, and Sanver.[1] It elects the assembly that minimizes the Hamming distance to the voter with the greatest such distance. Here, the Hamming distance is the number of candidates who is either in the outcome or approved on the voter's ballot, but not both or neither.
As minimax approval aims at representing everybody, it is not a proportional method. In a six-seat election with the following ballots:
- 100: A B C
- 100: D E F
- 1: G H I
the proportional outcome is {A B C D E F}, but the minimax outcome contains two candidates from each ballot, e.g. {A B D E G H}.
Complexity
Determining the optimal outcome is NP-hard[2], but polynomial-time approximation algorithms exist.[3]
References
- ↑ Brams, Steven J.; Kilgour, D. Marc; Sanver, M. Remzi (2007-04-28). "A minimax procedure for electing committees". Public Choice. Springer Science and Business Media LLC. 132 (3–4): 401–420. doi:10.1007/s11127-007-9165-x. ISSN 0048-5829.
- ↑ LeGrand, Rob (2004-11-02). "Analysis of the Minimax Procedure". Washington University Open Scholarship. Retrieved 2020-02-06.
- ↑ Byrka, Jarosław; Sornat, Krzysztof (2014). "PTAS for Minimax Approval Voting". Web and Internet Economics. Cham: Springer International Publishing. pp. 203–217. doi:10.1007/978-3-319-13129-0_15. ISBN 978-3-319-13128-3. ISSN 0302-9743.