In this work we consider general facility location and social choice problems, in which sets of agents @math and facilities @math are located in a metric space, and our goal is to assign agents to facilities (as well as choose which facilities to open) in order to optimize the social cost. We form new algorithms to do this in the presence of only ordinal information , i.e., when the true costs or distances from the agents to the facilities are unknown , and only the ordinal preferences of the agents for the facilities are available. The main difference between our work and previous work in this area is that while we assume that only ordinal information about agent preferences in known, we know the exact locations of the possible facilities @math . Due to this extra information about the facilities, we are able to form powerful algorithms which have small distortion , i.e., perform almost as well as omniscient algorithms but use only ordinal information about agent preferences. For example, we present natural social choice mechanisms for choosing a single facility to open with distortion of at most 3 for minimizing both the total and the median social cost; this factor is provably the best possible. We analyze many general problems including matching, @math -center, and @math -median, and present black-box reductions from omniscient approximation algorithms with approximation factor @math to ordinal algorithms with approximation factor @math ; doing this gives new ordinal algorithms for many important problems, and establishes a toolkit for analyzing such problems in the future.
We examine the quality of social choice mechanisms using a utilitarian view, in which all of the agents have costs for each of the possible alternatives. While these underlying costs determine what the optimal alternative is, they may be unknown to the social choice mechanism; instead the mechanism must decide on a good alternative based only on the ordinal preferences of the agents which are induced by the underlying costs. Due to its limited information, such a social choice mechanism cannot simply select the alternative that minimizes the total social cost (or minimizes some other objective function). Thus, we seek to bound the distortion: the worst-case ratio between the social cost of the alternative selected and the optimal alternative. Distortion measures how good a mechanism is at approximating the alternative with minimum social cost, while using only ordinal preference information. The underlying costs can be arbitrary, implicit, and unknown; our only assumption is that the agent costs form a metric space, which is a natural assumption in many settings. We quantify the distortion of many well-known social choice mechanisms. We show that for both total social cost and median agent cost, many positional scoring rules have large distortion, while on the other hand Copeland and similar mechanisms perform optimally or near-optimally, always obtaining a distortion of at most 5. We also give lower bounds on the distortion that could be obtained by any deterministic social choice mechanism, and extend our results on median agent cost to more general objective functions. We determine the quality of randomized social choice mechanisms in a setting in which the agents have metric preferences: every agent has a cost for each alternative, and these costs form a metric. We assume that these costs are unknown to the mechanisms (and possibly even to the agents themselves), which means we cannot simply select the optimal alternative, i.e. the alternative that minimizes the total agent cost (or median agent cost). However, we do assume that the agents know their ordinal preferences that are induced by the metric space. We examine randomized social choice functions that require only this ordinal information and select an alternative that is good in expectation with respect to the costs from the metric. To quantify how good a randomized social choice function is, we bound the distortion, which is the worst-case ratio between expected cost of the alternative selected and the cost of the optimal alternative. We provide new distortion bounds for a variety of randomized mechanisms, for both general metrics and for important special cases. Our results show a sizable improvement in distortion over deterministic mechanisms.