Carnegie Mellon University
Browse

Equity and Efficiency in Computational Social Choice

Download (1.87 MB)
thesis
posted on 2019-08-22, 17:42 authored by Johannes BenadeJohannes Benade
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.

History

Date

2019-05-19

Degree Type

  • Dissertation

Department

  • Tepper School of Business

Degree Name

  • Doctor of Philosophy (PhD)

Advisor(s)

Ariel Procaccia John Hooker

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC