Algorithm Design for Ordinal Settings

Abstract

Social choice theory is concerned with aggregating the preferences of agents into a single outcome. While it is natural to assume that agents have cardinal utilities, in many contexts, we can only assume access to the agents’ ordinal preferences, or rankings over the outcomes. As ordinal preferences are not as expressive as cardinal utilities, a loss of efficiency is unavoidable. Procaccia and Rosenschein (2006) introduced the notion of distortion to quantify this worst-case efficiency loss for a given social choice function.

We primarily study distortion in the context of election, or equivalently clustering problems, where we are given a set of agents and candidates in a metric space; each agent has a preference ranking over the set of candidates and we wish to elect a committee of k candidates that minimizes the total social cost incurred by the agents.

In the single-winner setting (when k = 1), we give a novel LP-duality based analysis framework that makes it easier to analyze the distortion of existing social choice functions, and extends readily to randomized social choice functions. Using this framework, we show that it is possible to give simpler proofs of known results. We also show how to efficiently compute an optimal randomized social choice function for any given instance. We utilize the latter result to obtain an instance for which any randomized social choice function has distortion at least 2.063164. This disproves the long-standing conjecture that there exists a randomized social choice function that has a worst-case distortion of at most 2.

When k is at least 2, it is not possible to compute an O(1)-distortion committee using purely ordinal information. We develop two O(1)-distortion mechanisms for this problem: one having a polylog(n) (per agent) query complexity, where n is the number of agents; and the other having O(k) query complexity (i.e., no dependence on n). We also study a much more general setting called minimum-norm k-clustering recently proposed in the clustering literature, where the objective is some monotone, symmetric norm of the the agents' costs, and we wish to find a committee of k candidates to minimize this objective. When the norm is the sum of the p largest costs, which is called the p-centrum problem in the clustering literature, we give low-distortion mechanisms by adapting our mechanisms for k-median. En route, we give a simple adaptive-sampling algorithm for this problem. Finally, we show how to leverage this adaptive-sampling idea to also obtain a constant-factor bicriteria approximation algorithm for minimum-norm k-clustering (in its full generality).