UC Santa Barbara

Committee selection is a classical problem in the social sciences where the goal is to choose a fixed number of candidates based on voters’ preferences. The problem naturally models elections in representative democracies or hiring of staff, but also generalizes many other resource allocation problems such as the classical facility location problems where facilities are treated as candidates and users as voters. By explicitly modeling voters’ preferences, the committee selection problem raises a number of interesting and challenging algorithmic problems such as winner determination, fault tolerance, and fairness. In this dissertation, we study four such problems.

For the most part, we consider the committee selection problem in Euclidean d-space where candidates/voters are points and voters’ preferences are implicitly derived using their Euclidean distances to the candidates. Our first problem is to find a winning committee under the well-known Chamberlin-Courant voting rule. The goal here is to choose a committee of k candidates so that the rank of any voter’s most preferred candidate in the committee is minimized. (The problem is also equivalent to the ordinal version of the classical k-center problem.) We show that the problem is NP-hard in any dimension d ≥ 2, and is also hard to approximate. Our main results are three polynomial-time approximation schemes, each of which finds a committee with a good minimax score.

Our second problem deals with fault tolerance in committee selection. We study the following three variants: (1) given a committee and a set of f failing candidates, find their optimal replacement; (2) compute the worst-case replacement score for a given committee under failure of f candidates; and (3) design a committee with the best replacement score under worst-case failures. Our main results are polynomial-time algorithms for three problems in one dimension. We also show that the problems are NP-hard in higher dimensions and give constant-factor approximations for all three problems along with an FPT bicriterion approximation for the optimal committee problem.

In our third problem we consider non-Euclidean elections and study the following two natural questions for a given election: (1) (Winner Verification) Given a subset of candidates (committee) T, is T a winning committee? (2) (Candidate Winner) Given a candidate c, does c belong to a winning committee? We show that both the above problems are hard (coNP-complete and θ_{2}^{P}-complete, respectively) in general, but for the restricted case of single-peaked and single-crossing preferences, they admit efficient algorithms.

Our last problem is the problem of covering a multicolored set of points in R^d using (at most) k disjoint unit-radius balls chosen from a candidate set of unit-radius balls so that each color class is covered fairly in proportion to its size. Specifically, we investigate the complexity of covering the maximum number of points in this setting. In the committee selection terminology, each ball is a candidate and each point is a voter; a voter approves all candidates within a unit-radius ball around it, and our goal is to choose an optimal size k committee under fairness constraints. We show that the problem is NP-hard even in one dimension when the number of colors is not fixed. On the other hand, for a fixed number of colors, we present a polynomial-time exact algorithm in one dimension, and a PTAS in any fixed dimension d ≥ 2.