Justifying Groups in Multiwinner Approval Voting

Edith Elkind; Piotr Faliszewski; Ayumi Igarashi; Pasin Manurangsi; Ulrike Schmidt-Kraepelin; Warut Suksompong

doi:10.1007/978-3-031-15714-1_27

Justifying Groups in Multiwinner Approval Voting

Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong^*

^*Corresponding author for this work

Computer Science

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

1 Scopus citations

Abstract

Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups of fewer than k candidates, where k is the target size of the committee. In this paper, we study such groups—known as n/k-justifying groups—both theoretically and empirically. First, we show that under the impartial culture model, n/k-justifying groups of size less than k/2 are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small n/k-justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small n/k-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.

Original language	English (US)
Title of host publication	Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings
Editors	Panagiotis Kanellopoulos, Maria Kyropoulou, Alexandros Voudouris
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	472-489
Number of pages	18
ISBN (Print)	9783031157134
DOIs	https://doi.org/10.1007/978-3-031-15714-1_27
State	Published - 2022
Event	15th International Symposium on Algorithmic Game Theory, SAGT 2022 - Colchester, United Kingdom Duration: Sep 12 2022 → Sep 15 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13584 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th International Symposium on Algorithmic Game Theory, SAGT 2022
Country/Territory	United Kingdom
City	Colchester
Period	9/12/22 → 9/15/22

Funding

Acknowledgments. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 101002854), from the Deutsche Forschungsgemeinschaft under grant BR 4744/2-1, from JST PRESTO under grant number JPMJPR20C1, from the Singapore Ministry of Education under grant number MOE-T2EP20221-0001, and from an NUS Start-up Grant. We would like to thank the anonymous SAGT reviewers for their comments.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-15714-1_27

Cite this

Elkind, E., Faliszewski, P., Igarashi, A., Manurangsi, P., Schmidt-Kraepelin, U., & Suksompong, W. (2022). Justifying Groups in Multiwinner Approval Voting. In P. Kanellopoulos, M. Kyropoulou, & A. Voudouris (Eds.), Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings (pp. 472-489). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13584 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-15714-1_27

Elkind, Edith ; Faliszewski, Piotr ; Igarashi, Ayumi et al. / Justifying Groups in Multiwinner Approval Voting. Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings. editor / Panagiotis Kanellopoulos ; Maria Kyropoulou ; Alexandros Voudouris. Springer Science and Business Media Deutschland GmbH, 2022. pp. 472-489 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{dae13933cc4a409d8e7df04c088b205f,

title = "Justifying Groups in Multiwinner Approval Voting",

abstract = "Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups of fewer than k candidates, where k is the target size of the committee. In this paper, we study such groups—known as n/k-justifying groups—both theoretically and empirically. First, we show that under the impartial culture model, n/k-justifying groups of size less than k/2 are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small n/k-justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small n/k-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.",

author = "Edith Elkind and Piotr Faliszewski and Ayumi Igarashi and Pasin Manurangsi and Ulrike Schmidt-Kraepelin and Warut Suksompong",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 15th International Symposium on Algorithmic Game Theory, SAGT 2022 ; Conference date: 12-09-2022 Through 15-09-2022",

year = "2022",

doi = "10.1007/978-3-031-15714-1_27",

language = "English (US)",

isbn = "9783031157134",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "472--489",

editor = "Panagiotis Kanellopoulos and Maria Kyropoulou and Alexandros Voudouris",

booktitle = "Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings",

address = "Germany",

}

Elkind, E, Faliszewski, P, Igarashi, A, Manurangsi, P, Schmidt-Kraepelin, U & Suksompong, W 2022, Justifying Groups in Multiwinner Approval Voting. in P Kanellopoulos, M Kyropoulou & A Voudouris (eds), Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13584 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 472-489, 15th International Symposium on Algorithmic Game Theory, SAGT 2022, Colchester, United Kingdom, 9/12/22. https://doi.org/10.1007/978-3-031-15714-1_27

Justifying Groups in Multiwinner Approval Voting. / Elkind, Edith; Faliszewski, Piotr; Igarashi, Ayumi et al.
Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings. ed. / Panagiotis Kanellopoulos; Maria Kyropoulou; Alexandros Voudouris. Springer Science and Business Media Deutschland GmbH, 2022. p. 472-489 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13584 LNCS).

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

TY - GEN

T1 - Justifying Groups in Multiwinner Approval Voting

AU - Elkind, Edith

AU - Faliszewski, Piotr

AU - Igarashi, Ayumi

AU - Manurangsi, Pasin

AU - Schmidt-Kraepelin, Ulrike

AU - Suksompong, Warut

PY - 2022

Y1 - 2022

N2 - Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups of fewer than k candidates, where k is the target size of the committee. In this paper, we study such groups—known as n/k-justifying groups—both theoretically and empirically. First, we show that under the impartial culture model, n/k-justifying groups of size less than k/2 are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small n/k-justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small n/k-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.

AB - Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups of fewer than k candidates, where k is the target size of the committee. In this paper, we study such groups—known as n/k-justifying groups—both theoretically and empirically. First, we show that under the impartial culture model, n/k-justifying groups of size less than k/2 are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small n/k-justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small n/k-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.

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

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

U2 - 10.1007/978-3-031-15714-1_27

DO - 10.1007/978-3-031-15714-1_27

M3 - Conference contribution

AN - SCOPUS:85138788691

SN - 9783031157134

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 472

EP - 489

BT - Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings

A2 - Kanellopoulos, Panagiotis

A2 - Kyropoulou, Maria

A2 - Voudouris, Alexandros

PB - Springer Science and Business Media Deutschland GmbH

T2 - 15th International Symposium on Algorithmic Game Theory, SAGT 2022

Y2 - 12 September 2022 through 15 September 2022

ER -

Elkind E, Faliszewski P, Igarashi A, Manurangsi P, Schmidt-Kraepelin U, Suksompong W. Justifying Groups in Multiwinner Approval Voting. In Kanellopoulos P, Kyropoulou M, Voudouris A, editors, Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 472-489. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-15714-1_27