• Recherche,

"Justified Representation", Edith Elkind, Colloque de l'IRIT

le 19 mai 2015

12h30
Manufacture des Tabacs
Salle ME303

Edith Elkind, Lecturer à l'Université d'Oxford, nous presentera ses travaux "Justified Representation"

Edith Elkind, Lecturer à l'Université d'Oxford, nous presentera ses travaux "Justified Representation". Elle donnera se séminaire entierement en anglais.

Abstract: We consider approval-based committee voting, i.e., the setting whereeach voter approves a subset of candidates, and these votes are thenused to select a fixed-size set of winners (committee). We propose anatural axiom for this setting, which we call justified representation(JR). This axiom requires that if a large enough group of votersexhibits agreement by supporting the same candidate, then at least onevoter in this group has an approved candidate in the winningcommittee. We show that for every list of ballots it is possible toselect a committee that provides JR. We then check if this axiom isfulfilled by well-known approval-based voting rules. We show that theanswer is negative for most of these rules, with notable exceptions ofPAV (Proportional Approval Voting), an extreme version of RAV(Reweighted Approval Voting), and, for a restricted preference domain,MAV (Minimax Approval Voting). We then introduce a stronger version ofthe JR axiom, which we call extended justified representation (EJR),and show that PAV satisfies EJR, while other rules do not. We alsoconsider several other questions related to JR and EJR, including therelationship between JR/EJR and unanimity, and the complexity of theassociated algorithmic problems.Based on joint work with Haris Aziz, Markus Brill, Vince Conitzer,Rupert Freeman, and Toby Walsh (AAAI'15)
Mis à jour le 9 avril 2015