Algorithms for Voting and Group Selection

Abstract

Many of the core challenges in social choice, new and old, stand to benefit from consideration through the computational lens. We demonstrate the particular applicability of approximation algorithms to the tasks of aggregating judgements and preferences for choosing one or more alternatives, and to the construction of representative committees and valuable teams.

The first part of this thesis presents contributions to the theory of judgement and preference aggregation in settings where only incomplete information is known. It considers the task of combining expert advice given only incomplete information about experts' competence in order to reach a maximally accurate judgement. For preferences, we consider two settings of choosing alternative(s) given only incomplete information about voters' preferences. In the first we aim to choose a single alternative when only the ranking of voters' valuations of alternatives is known. In the second we aim to select a committee of candidates that all coalitions within the electorate find at least partially acceptable, under the restriction that each voter is only evaluates a few candidates.

The second part studies sampling processes which arise in sortition, a direct democratic paradigm in which representative subsets (or panels) of a population are randomly chosen in order to represent the whole. Here the goal of choosing the panel at random is in tension with choosing a maximally representative panel; we present a new framework and approach to making this tradeoff, and further address the challenge of satisfying these aims via a process which is also readily comprehensible to observers.

The third part provides algorithmic approaches to group selection problems motivated by hiring, admissions, and team formation. We consider the task of making a collection of simultaneous invitations to candidates who, in contrast to the previous committee selection problems, may decline to be included in the group with some probability. We present approaches to eliciting information from participants and extending sets of invitations in order to realize a group of favorable participants which is close to the target size.