Multiwinner Temporal Voting with Aversion to Change

Valentin Zech; Niclas Boehmer; Edith Elkind; Nicholas Teh

doi:10.3233/FAIA240870

Multiwinner Temporal Voting with Aversion to Change

Valentin Zech^*, Niclas Boehmer, Edith Elkind, Nicholas Teh

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We study two-stage committee elections where voters have dynamic preferences over candidates; at each stage, a committee is chosen under a given voting rule. We are interested in identifying a winning committee for the second stage that overlaps as much as possible with the first-stage committee. We show a full complexity dichotomy for the class of Thiele rules: this problem is tractable for Approval Voting (AV) and hard for all other Thiele rules (including, in particular, Proportional Approval Voting and the Chamberlin-Courant rule). We extend this dichotomy to the greedy variants of Thiele rules. We also explore this problem from a parameterized complexity perspective for several natural parameters. We complement the theory with experimental analysis: e.g., we investigate the average number of changes in the committee as a function of changes in voters’ preferences and the role of ties.

Original language	English (US)
Title of host publication	ECAI 2024 - 27th European Conference on Artificial Intelligence, Including 13th Conference on Prestigious Applications of Intelligent Systems, PAIS 2024, Proceedings
Editors	Ulle Endriss, Francisco S. Melo, Kerstin Bach, Alberto Bugarin-Diz, Jose M. Alonso-Moral, Senen Barro, Fredrik Heintz
Publisher	IOS Press BV
Pages	3236-3243
Number of pages	8
ISBN (Electronic)	9781643685489
DOIs	https://doi.org/10.3233/FAIA240870
State	Published - Oct 16 2024
Event	27th European Conference on Artificial Intelligence, ECAI 2024 - Santiago de Compostela, Spain Duration: Oct 19 2024 → Oct 24 2024

Publication series

Name	Frontiers in Artificial Intelligence and Applications
Volume	392
ISSN (Print)	0922-6389
ISSN (Electronic)	1879-8314

Conference

Conference	27th European Conference on Artificial Intelligence, ECAI 2024
Country/Territory	Spain
City	Santiago de Compostela
Period	10/19/24 → 10/24/24

Funding

NB was supported by the DFG project ComSoc-MPMS (NI 369/22). EE was supported by the AI Programme of The Alan Turing Institute and an EPSRC Grant EP/X038548/1.

ASJC Scopus subject areas

Artificial Intelligence

Access to Document

10.3233/FAIA240870

Cite this

Zech, V., Boehmer, N., Elkind, E., & Teh, N. (2024). Multiwinner Temporal Voting with Aversion to Change. In U. Endriss, F. S. Melo, K. Bach, A. Bugarin-Diz, J. M. Alonso-Moral, S. Barro, & F. Heintz (Eds.), ECAI 2024 - 27th European Conference on Artificial Intelligence, Including 13th Conference on Prestigious Applications of Intelligent Systems, PAIS 2024, Proceedings (pp. 3236-3243). (Frontiers in Artificial Intelligence and Applications; Vol. 392). IOS Press BV. https://doi.org/10.3233/FAIA240870

Zech, Valentin ; Boehmer, Niclas ; Elkind, Edith et al. / Multiwinner Temporal Voting with Aversion to Change. ECAI 2024 - 27th European Conference on Artificial Intelligence, Including 13th Conference on Prestigious Applications of Intelligent Systems, PAIS 2024, Proceedings. editor / Ulle Endriss ; Francisco S. Melo ; Kerstin Bach ; Alberto Bugarin-Diz ; Jose M. Alonso-Moral ; Senen Barro ; Fredrik Heintz. IOS Press BV, 2024. pp. 3236-3243 (Frontiers in Artificial Intelligence and Applications).

@inproceedings{2d10f93dd4044346bfc3a423b85a3e8f,

title = "Multiwinner Temporal Voting with Aversion to Change",

abstract = "We study two-stage committee elections where voters have dynamic preferences over candidates; at each stage, a committee is chosen under a given voting rule. We are interested in identifying a winning committee for the second stage that overlaps as much as possible with the first-stage committee. We show a full complexity dichotomy for the class of Thiele rules: this problem is tractable for Approval Voting (AV) and hard for all other Thiele rules (including, in particular, Proportional Approval Voting and the Chamberlin-Courant rule). We extend this dichotomy to the greedy variants of Thiele rules. We also explore this problem from a parameterized complexity perspective for several natural parameters. We complement the theory with experimental analysis: e.g., we investigate the average number of changes in the committee as a function of changes in voters{\textquoteright} preferences and the role of ties.",

author = "Valentin Zech and Niclas Boehmer and Edith Elkind and Nicholas Teh",

note = "Publisher Copyright: {\textcopyright} 2024 The Authors.; 27th European Conference on Artificial Intelligence, ECAI 2024 ; Conference date: 19-10-2024 Through 24-10-2024",

year = "2024",

month = oct,

day = "16",

doi = "10.3233/FAIA240870",

language = "English (US)",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press BV",

pages = "3236--3243",

editor = "Ulle Endriss and Melo, {Francisco S.} and Kerstin Bach and Alberto Bugarin-Diz and Alonso-Moral, {Jose M.} and Senen Barro and Fredrik Heintz",

booktitle = "ECAI 2024 - 27th European Conference on Artificial Intelligence, Including 13th Conference on Prestigious Applications of Intelligent Systems, PAIS 2024, Proceedings",

}

Zech, V, Boehmer, N, Elkind, E & Teh, N 2024, Multiwinner Temporal Voting with Aversion to Change. in U Endriss, FS Melo, K Bach, A Bugarin-Diz, JM Alonso-Moral, S Barro & F Heintz (eds), ECAI 2024 - 27th European Conference on Artificial Intelligence, Including 13th Conference on Prestigious Applications of Intelligent Systems, PAIS 2024, Proceedings. Frontiers in Artificial Intelligence and Applications, vol. 392, IOS Press BV, pp. 3236-3243, 27th European Conference on Artificial Intelligence, ECAI 2024, Santiago de Compostela, Spain, 10/19/24. https://doi.org/10.3233/FAIA240870

Multiwinner Temporal Voting with Aversion to Change. / Zech, Valentin; Boehmer, Niclas; Elkind, Edith et al.
ECAI 2024 - 27th European Conference on Artificial Intelligence, Including 13th Conference on Prestigious Applications of Intelligent Systems, PAIS 2024, Proceedings. ed. / Ulle Endriss; Francisco S. Melo; Kerstin Bach; Alberto Bugarin-Diz; Jose M. Alonso-Moral; Senen Barro; Fredrik Heintz. IOS Press BV, 2024. p. 3236-3243 (Frontiers in Artificial Intelligence and Applications; Vol. 392).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Multiwinner Temporal Voting with Aversion to Change

AU - Zech, Valentin

AU - Boehmer, Niclas

AU - Elkind, Edith

AU - Teh, Nicholas

PY - 2024/10/16

Y1 - 2024/10/16

N2 - We study two-stage committee elections where voters have dynamic preferences over candidates; at each stage, a committee is chosen under a given voting rule. We are interested in identifying a winning committee for the second stage that overlaps as much as possible with the first-stage committee. We show a full complexity dichotomy for the class of Thiele rules: this problem is tractable for Approval Voting (AV) and hard for all other Thiele rules (including, in particular, Proportional Approval Voting and the Chamberlin-Courant rule). We extend this dichotomy to the greedy variants of Thiele rules. We also explore this problem from a parameterized complexity perspective for several natural parameters. We complement the theory with experimental analysis: e.g., we investigate the average number of changes in the committee as a function of changes in voters’ preferences and the role of ties.

AB - We study two-stage committee elections where voters have dynamic preferences over candidates; at each stage, a committee is chosen under a given voting rule. We are interested in identifying a winning committee for the second stage that overlaps as much as possible with the first-stage committee. We show a full complexity dichotomy for the class of Thiele rules: this problem is tractable for Approval Voting (AV) and hard for all other Thiele rules (including, in particular, Proportional Approval Voting and the Chamberlin-Courant rule). We extend this dichotomy to the greedy variants of Thiele rules. We also explore this problem from a parameterized complexity perspective for several natural parameters. We complement the theory with experimental analysis: e.g., we investigate the average number of changes in the committee as a function of changes in voters’ preferences and the role of ties.

UR - http://www.scopus.com/inward/record.url?scp=85216708879&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85216708879&partnerID=8YFLogxK

U2 - 10.3233/FAIA240870

DO - 10.3233/FAIA240870

M3 - Conference contribution

AN - SCOPUS:85216708879

T3 - Frontiers in Artificial Intelligence and Applications

SP - 3236

EP - 3243

BT - ECAI 2024 - 27th European Conference on Artificial Intelligence, Including 13th Conference on Prestigious Applications of Intelligent Systems, PAIS 2024, Proceedings

A2 - Endriss, Ulle

A2 - Melo, Francisco S.

A2 - Bach, Kerstin

A2 - Bugarin-Diz, Alberto

A2 - Alonso-Moral, Jose M.

A2 - Barro, Senen

A2 - Heintz, Fredrik

PB - IOS Press BV

T2 - 27th European Conference on Artificial Intelligence, ECAI 2024

Y2 - 19 October 2024 through 24 October 2024

ER -

Zech V, Boehmer N, Elkind E, Teh N. Multiwinner Temporal Voting with Aversion to Change. In Endriss U, Melo FS, Bach K, Bugarin-Diz A, Alonso-Moral JM, Barro S, Heintz F, editors, ECAI 2024 - 27th European Conference on Artificial Intelligence, Including 13th Conference on Prestigious Applications of Intelligent Systems, PAIS 2024, Proceedings. IOS Press BV. 2024. p. 3236-3243. (Frontiers in Artificial Intelligence and Applications). doi: 10.3233/FAIA240870

Multiwinner Temporal Voting with Aversion to Change

Abstract

Publication series

Conference

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this