Constant-Factor Distortion Mechanisms for k-Committee Election

Abstract

In the $k$-committee election problem, we wish to aggregate the preferences of $n$ agents over a set of alternatives and select a committee of $k$ alternatives that minimizes the cost incurred by the agents. While we typically assume that agent preferences are captured by a cardinal utility function, in many contexts we only have access to ordinal information, namely the agents' rankings over the outcomes. As preference rankings are not as expressive as cardinal utilities, a loss of efficiency is inevitable, and is quantified by the notion of \emph{distortion}. We study the problem of electing a $k$-committee that minimizes the sum of the $\ell$-largest costs incurred by the agents, when agents and candidates are embedded in a metric space. This problem is called the $\ell$-centrum problem and captures both the utilitarian and egalitarian objectives. When $k \geq 2$, it is not possible to compute a bounded-distortion committee using purely ordinal information. We develop the first algorithms (that we call mechanisms) for the $\ell$-centrum problem (when $k \geq 2$), which achieve $O(1)$-distortion while eliciting only a very limited amount of cardinal information via value queries. We obtain two types of query-complexity guarantees: $O(\log k \log n)$ queries \emph{per agent}, and $O(k^2 \log^2 n)$ queries \emph{in total} (while achieving $O(1)$-distortion in both cases). En route, we give a simple adaptive-sampling algorithm for the $\ell$-centrum $k$-clustering problem.