[Back]

M. Lackner, R. Bredereck, P. Faliszewski, A. Igarashi, P. Skowron:
"Multiwinner Elections With Diversity Constraints";
Talk: AAAI 2018, New Orleans, Lousiana, USA; 2018-02-02 - 2018-02-07; in: "Proceedings of the Thirty-Second {AAAI} Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th {AAAI} Symposium on Educational Advances in Artificial Intelligence (EAAI-18)", AAAI Press, (2018), 933 - 940.

We develop a model of multiwinner elections that combines performance-based measures of the quality of the committee (such as, e.g., Borda scores of the committee members) with diversity constraints. Specifically, we assume that the candidates have certain attributes (such as being a male or a female, being junior or senior, etc.) and the goal is to elect a committee that, on the one hand, has as high a score regarding a given performance measure, but that, on the other hand, meets certain requirements (e.g., of the form "at least 30% of the committee members are junior candidates and at least 40% are females"). We analyze the computational complexity of computing winning committees in this model, obtaining polynomial-time algorithms (exact and approximate) and NP-hardness results. We focus on several natural classes of voting rules and diversity constraints.

multi-winner elections; approximation algorithms; diversity; computational social choice; voting

https://publik.tuwien.ac.at/files/publik_273383.pdf

Project Head Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen

Project Head Stefan Woltran:
START