Phase Transitions for Proportional Representation in Committee Elections with Random Approvals
Houyu Zhou
UNSW Sydney, Australia and Weizmann Institute, Israel
November 12, 2026, 13:00 in S6
Abstract
Many collective decisions, such as electing a committee, selecting projects for a participatory budget, or choosing locations for public facilities, must aggregate the preferences of many agents fairly. In this talk I will focus on proportional representation in approval-based committee elections, where n voters each approve a subset of m candidates and a committee of k candidates must be chosen. Average justified representation (AJR) requires that every large group of voters who approve common candidates receives a proportional number of approved winners on average. Since AJR cannot always be satisfied, we ask how often an AJR committee exists when approvals are random: each voter approves each candidate independently with probability p. We give a complete characterization with two phase transitions. With high probability, an AJR committee exists when p < 1/k or p > p_2 and does not exist when 1/k < p < p_2. At the two thresholds, an AJR committee exists with probability bounded away from 0 and 1. Here p_2 is the largest root of an explicit equation, and the interval (1/k, p_2) shrinks to zero as k grows.
