PhragmŽnÕs Voting Methods and Justified Representation

No. 1: Thirty-First AAAI Conference On Artificial Intelligence

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 31

AAAI Technical Track: Game Theory and Economic Paradigms

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.

10.1609/aaai.v31i1.10598