### Justified representation in multiwinner voting: axioms and algorithms

Edith Elkind

University of Oxford

SWS Distinguished Lecture Series

19 Oct 2018, 10:30 am - 11:30 am

Kaiserslautern building G26, room 111

simultaneous videocast to Saarbrücken building E1 5, room 029

simultaneous videocast to Saarbrücken building E1 5, room 029

Suppose that a group of voters wants to select k \ge 1 alternatives from a
given set, and each voter indicates which of the alternatives are acceptable to
her: the alternatives could be conference submissions, applicants for a
scholarship or locations for a fast food chain. In this setting it is natural
to require that the winning set represents the voters fairly, in the sense that
large groups of voters with similar preferences have at least some of their
approved alternatives in the winning set. We describe several ways to formalize
this idea, and show how to use it to classify voting rules. For one of our
axioms, the only known voting rule that satisfies it is not polynomial-time
computable, and it was conjectured that no voting rule that satisfies this
axiom can be polynomial-time computable; however, we will show that this is not
the case.