Evaluating approval-based multiwinner voting in terms of robustness to noise

Ioannis Caragiannis; Christos Kaklamanis; Nikos Karanikolas; George Krimpas

doi:10.1007/s10458-021-09530-w

Evaluating approval-based multiwinner voting in terms of robustness to noise

Ioannis Caragiannis^*
, Christos Kaklamanis
, Nikos Karanikolas
, George Krimpas

^*Corresponding author af dette arbejde

Institut for Datalogi

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

5 Citationer (Scopus)

Abstract

Approval-based multiwinner voting rules have recently received much attention in the Computational Social Choice literature. Such rules aggregate approval ballots and determine a winning committee of alternatives. To assess effectiveness, we propose to employ new noise models that are specifically tailored for approval votes and committees. These models take as input a ground truth committee and return random approval votes to be thought of as noisy estimates of the ground truth. A minimum robustness requirement for an approval-based multiwinner voting rule is to return the ground truth when applied to profiles with sufficiently many noisy votes. Our results indicate that approval-based multiwinner voting can indeed be robust to reasonable noise. We further refine this finding by presenting a hierarchy of rules in terms of how robust to noise they are.

Originalsprog	Engelsk
Artikelnummer	1
Tidsskrift	Autonomous Agents and Multi-Agent Systems
Vol/bind	36
Nummer	1
ISSN	1387-2532
DOI	https://doi.org/10.1007/s10458-021-09530-w
Status	Udgivet - apr. 2022

Adgang til dokumentet

10.1007/s10458-021-09530-w

https://arxiv.org/pdf/2002.01776.pdf

Biblioteksadgang?

Tjek tilgængelighed hos det Kgl. Bibliotek

Citationsformater

@article{0aec9bd3cf424b4f91adc3501a7174f1,

title = "Evaluating approval-based multiwinner voting in terms of robustness to noise",

abstract = "Approval-based multiwinner voting rules have recently received much attention in the Computational Social Choice literature. Such rules aggregate approval ballots and determine a winning committee of alternatives. To assess effectiveness, we propose to employ new noise models that are specifically tailored for approval votes and committees. These models take as input a ground truth committee and return random approval votes to be thought of as noisy estimates of the ground truth. A minimum robustness requirement for an approval-based multiwinner voting rule is to return the ground truth when applied to profiles with sufficiently many noisy votes. Our results indicate that approval-based multiwinner voting can indeed be robust to reasonable noise. We further refine this finding by presenting a hierarchy of rules in terms of how robust to noise they are.",

keywords = "Approval-based voting, Computational social choice, Multiwinner voting rules, Noise models",

author = "Ioannis Caragiannis and Christos Kaklamanis and Nikos Karanikolas and George Krimpas",

year = "2022",

month = apr,

doi = "10.1007/s10458-021-09530-w",

language = "English",

volume = "36",

journal = "Autonomous Agents and Multi-Agent Systems",

issn = "1387-2532",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Evaluating approval-based multiwinner voting in terms of robustness to noise

AU - Caragiannis, Ioannis

AU - Kaklamanis, Christos

AU - Karanikolas, Nikos

AU - Krimpas, George

PY - 2022/4

Y1 - 2022/4

N2 - Approval-based multiwinner voting rules have recently received much attention in the Computational Social Choice literature. Such rules aggregate approval ballots and determine a winning committee of alternatives. To assess effectiveness, we propose to employ new noise models that are specifically tailored for approval votes and committees. These models take as input a ground truth committee and return random approval votes to be thought of as noisy estimates of the ground truth. A minimum robustness requirement for an approval-based multiwinner voting rule is to return the ground truth when applied to profiles with sufficiently many noisy votes. Our results indicate that approval-based multiwinner voting can indeed be robust to reasonable noise. We further refine this finding by presenting a hierarchy of rules in terms of how robust to noise they are.

AB - Approval-based multiwinner voting rules have recently received much attention in the Computational Social Choice literature. Such rules aggregate approval ballots and determine a winning committee of alternatives. To assess effectiveness, we propose to employ new noise models that are specifically tailored for approval votes and committees. These models take as input a ground truth committee and return random approval votes to be thought of as noisy estimates of the ground truth. A minimum robustness requirement for an approval-based multiwinner voting rule is to return the ground truth when applied to profiles with sufficiently many noisy votes. Our results indicate that approval-based multiwinner voting can indeed be robust to reasonable noise. We further refine this finding by presenting a hierarchy of rules in terms of how robust to noise they are.

KW - Approval-based voting

KW - Computational social choice

KW - Multiwinner voting rules

KW - Noise models

U2 - 10.1007/s10458-021-09530-w

DO - 10.1007/s10458-021-09530-w

M3 - Journal article

SN - 1387-2532

VL - 36

JO - Autonomous Agents and Multi-Agent Systems

JF - Autonomous Agents and Multi-Agent Systems

IS - 1

M1 - 1

ER -

Evaluating approval-based multiwinner voting in terms of robustness to noise

Abstract

Adgang til dokumentet

Biblioteksadgang?

Fingeraftryk

Citationsformater