AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Phragmén’s Voting Methods and Justified Representation
Markus Brill, Rupert Freeman, Svante Janson, Martin Lackner

Last modified: 2017-02-10

Abstract


In the late 19th century, Lars Edvard Phragmén proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants one minimizing the maximal load and one minimizing the variance of loads —and a sequential variant. We study Phragmén's methods from an axiomatic point of view, focussing on justified representation and related properties that have recently been introduced by Aziz et al. (2015a) and Sánchez-Fernández et al. (2017). We show that the sequential variant satisfies proportional justified representation, making it the first known polynomial-time computable method with this property. Moreover, we show that the optimization variants satisfy perfect representation. We also analyze the com- putational complexity of Phragmén's methods and provide mixed-integer programming based algorithms for computing them.

Keywords


committee voting; load balancing; approval ballots; representation

Full Text: PDF