Proportionality from Low-Dimensional Approval Data

Multiwinner voting is seeing increasing application in a wide range of domains, including participatory budgeting, online e-democracy platforms, andreinforcementlearningfromhumanfeedback(RLHF) forfine-tuningAImodels. Invirtuallyallsettings, instancescanand do exceed the scale for which it is feasible to elicit human agents’ input on the full candidate set. Motivated by this, we explore the extent to which proportionality axioms can be satisfied when each agent expresses preferences over only a few of the alternatives. We consider when only a constant number of queries per voter suffice to identify proportional committees, even as the committee size grows large. We give fine-grained guarantees when voters are one of only finitely many types, and present both query-sparse and query-efficient algorithms. The former proceeds via a complexity metric that captures the difficulty of reconstructing an approval profile from sparse queries, and may be of independent interest. We also ask when approval queries over mere pairs of candidates are enough. Such structured domains include possibly-single peaked instances, where pairwise queries are enough to both identify a global candidate order and identify proportional committees of arbitrary size.

Authors

• Zhiyi Huang University of Texas at Austin
• Gregory Kehne Washington University in St. Louis
• Chutong Yang University of Texas at Austin

Keywords

• Multiwinner voting
• Approval voting
• Participatory budgeting