New algorithm ensures fair multiwinner voting with minimal voter input

In multiwinner elections with many candidates—such as participatory budgeting or large-scale recommendations—standard proportional-fairness guarantees like EJR+ assume voters can evaluate every candidate, an implausible expectation. A new paper by Springham et al. tackles this by eliciting only a little information per voter. They model preferences using a spatial Axis-aligned Random Rectangle Voter (ARRV) model, where candidates exist in a d-dimensional issue space, and each voter approves a hyper-rectangle—a tolerance interval on each issue.

Preferences are revealed through planar queries: each query compares a voter's tolerance to a candidate on a single issue. The authors present an algorithm that returns an EJR+ committee for any distribution of rectangular preferences, using an expected O(d log d k) planar queries per voter, independent of the number of candidates m. The algorithm employs a dimension-agnostic verify-or-fallback framework, with query cost governed by interchangeable modules. They provide such modules for known, unknown, and smooth distributions, offering end-to-end guarantees. This work promises to make proportional representation practical in settings with massive candidate pools and limited voter attention.