Show simple item record

hal.structure.identifier
hal.structure.identifierDepartment of Informatics
dc.contributor.authorAmanatidis, Georgios
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBarrot, Nathanaël
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLang, Jérôme
hal.structure.identifier
hal.structure.identifierDepartment of Informatics
dc.contributor.authorMarkakis, Evangelos
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorRies, Bernard
dc.date.accessioned2017-03-30T08:02:45Z
dc.date.available2017-03-30T08:02:45Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16458
dc.language.isoenen
dc.subjectSocial choiceen
dc.subjectApproval votingen
dc.subjectMinisumen
dc.subjectMinimaxen
dc.subjectOrdered weighted averagingoperatorsen
dc.subject.ddc003en
dc.titleMultiple Referenda and Multiwinner Elections Using Hamming Distances: Complexity and Manipulabilityen
dc.typeCommunication / Conférence
dc.description.abstractenWe study multiple referenda and committee elections, when the ballot of each voter is simply a set of approved binary issues (or candidates). Two well-known rules under this model are the commonly used candidate-wise majority, also called the minisum rule, as well as the minimax rule. In the former, the elected committee consists of the candidates approved by a majority of voters, whereas the latter picks a committee minimizing the maximum Hamming distance to all ballots.As these rules are in some ways extreme points in the whole spectrum of solutions, we consider a general family of rules, using the Ordered Weighted Averaging (OWA) operators. Each rule is parameterized by a weight vector, showing the importance of the i-th highest Hamming distance of the outcome to the voters. The objective then is to minimize the weighted sum of the (ordered) distances. We study mostly computational, but also manipulability properties for this family. We first exhibit that for many rules, it is NP-hard to find a winning committee. We then proceed to identify cases where the problem is either efficiently solvable, or approximable with a small approximation factor. Finally, we investigate the issue of manipulating such rules and provide conditions that make this possible.en
dc.identifier.citationpages715-723en
dc.relation.ispartoftitleAAMAS '15 Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systemsen
dc.relation.ispartofeditorBordini, Rafael H.
dc.relation.ispartofeditorElkind, Edith
dc.relation.ispartofeditorWeiss, Gerhard
dc.relation.ispartofeditorYolum, Pinar
dc.relation.ispartofpublnameIFAAMASen
dc.relation.ispartofdate2015
dc.relation.ispartofpages2022en
dc.identifier.urlsitehttp://www.ifaamas.org/Proceedings/aamas2015/forms/contents.htmen
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-1-4503-3413-6en
dc.relation.conftitle14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '15)en
dc.relation.confdate2015-05
dc.relation.confcityIstanbulen
dc.relation.confcountryTurkeyen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-03-29T09:55:03Z
hal.identifierhal-01498455*
hal.version1*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record