Proportionality in Multiwinner Voting: The Power of Local Search

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.