[Back]

M. Lackner, P. Faliszewski, D. Peters, N. Talmon:
"Effective Heuristics for Committee Scoring Rules";
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), 1023 - 1030.

Committee scoring rules form an important class of multiwinner voting rules. As computing winning committees under such rules is generally intractable, in this paper we investigate efficient heuristics for this task. We design two novel heuristics for computing approximate results of multiwinner elections under arbitrary committee scoring rules; notably, one of these heuristics uses concepts from cooperative game theory. We then provide an experimental evaluation of our heuristics (and two others, known from the literature): we compare the scores of the committees output by our algorithms to the scores of the optimal committees, and also use the two-dimensional Euclidean domain to compare the visual representations of the outputs of our algorithms.

social choice; voting rules; committees; heuristics; submodular optimization; spatial preferences; cooperative game theory; power indices

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

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

Project Head Stefan Woltran:
START