Equity and Efficiency in Computational Social Choice

This thesis studies problems in computational social choice and fair division.Computational social choice asks how to aggregate individual votes and opinions into a joint decision. Participatory budgeting enables the allocation of public funds by collecting and aggregating individual preferences over pro-posed infrastructure projects; it has already had a sizable real-world impact.We analytically compare four preference elicitation methods through the lens of implicit utilitarian voting, and find that threshold approval votes are qualitatively superior. This conclusion is supported by experiments using data from real participatory budgeting elections. We also conduct a human subject experiment on Amazon Mechanical Turk to study the cognitive burden that different elicitation formats impose on voters.Under implicit utilitarian voting we attempt to maximize a utilitarian objective in the presence of uncertainty about voter utility functions. Next,we take a very different approach, and assume votes are noisy estimates of an unknown ground truth. We build on previous work which replaced structural assumptions on the noise with a worst-case approach, and minimize the expected error with respect to a set of feasibly true rankings. We derive mostly sharp analytical bounds on the expected error and find that our approach has useful practical properties.Fair division problems involve allocating goods to heterogeneous agents.Motivated by the problem of a food bank allocating donations to their beneficiaries without knowledge of future arrivals, we study the online allocation of indivisible items. Our goal is to design allocation algorithms that minimize the maximum envy, defined as the maximum difference between any agent’s overall value for items allocated to another agent and to herself. An algorithm has vanishing envy if the ratio of envy over time goes to zero as time goes to infinity. We find a polynomial-time, deterministic algorithm that achieves vanishing envy, and show the rate at which envy vanishes is asymptotically optimal.Finally, we consider the problem of gerrymandering. We start with an impartial protocol and derive a notion of fairness which provides guidance about what to expect from an impartial districting. Specifically, we propose that a party should win a number of districts equal to the midpoint between what they win in their best and worst districtings. We show that this notion of fairness has close ties to proportionality yet, in contrast to proportionality,there always exists a districting satisfying our notion of fairness.