Abstract:

In multiwinner voting, voters report their preferences over the available alternatives, and the goal is to select a fixed-size subset of alternatives, usually referred to as a committee; this model captures a variety of real-life scenarios, from selecting a representative governing body to deciding which search results should appear on the first page of a search engine’s output or selecting validators for a proof-of-stake blockchain protocol.
A particularly well-studied special case of this general setting is multiwinner voting with approval ballots, where each voter reports which alternatives they approve. A key desideratum in multiwinner voting is proportionality, i.e., assuring that large groups of voters with similar preferences receive appropriate representation in the selected committee. In the context of approval ballots, a series of papers proposed a family of axioms that aim to capture this intuition, including (from weakest to strongest) justified representation, proportional/extended/full justified representation, and the core. A major research challenge, then, is to identify voting rules that are efficiently computable and whose outputs satisfy these axioms; another important goal is to design efficient verification methods that can decide whether a given committee satisfies an axiom.

In this talk, we will survey recent progress on these challenges, compare the properties of several multiwinner voting rules with strong axiomatic properties, discuss tradeoffs between proportionality and other objectives (such as, e.g., social welfare), and highlight the power of local search to produce high-quality, easily verifiable solutions in a robust and flexible manner.

Bio:

Edith Elkind is a Professor of Computer Science at the University of Oxford and the Theme lead on Game Theory at the Alan Turing Institute. She obtained her PhD from Princeton in 2005, and has worked in the UK, Israel, and Singapore before joining Oxford in 2013. She works in algorithmic game theory, with a focus on algorithms for collective decision making and coalition formation. Edith is an ELLIS Fellow, a EurAI Fellow, and a recipient of SIGAI Autonomous Agents Research Award (2023). She has served as a program chair of COMSOC, WINE, AAMAS, ACM EC, and IJCAI, and is a member of AAAI executive council, SCW council, and IJCAI board of trustees.

School of Computing: https://www.mq.edu.au/faculty-of-science-and-engineering/departments-and-schools/school-of-computing

DataX Research Centre: https://www.mqdatax.net/

Macquarie University: https://www.mq.edu.au/

Inquiries: contact us for joining the seminar or anything relating to the AI@MQU.