Approximating Optimal Social Choice under Metric Preferences

Prelegent(ci)

Piotr Skowron

Afiliacja

Instytut Informatyki UW

Termin

12 kwietnia 2018 10:15

Pokój

p. 4050

Seminarium

Seminarium „Gry, mechanizmy i sieci społeczne”

---

We consider voting under metric preferences: both voters and alternatives are associated with points in a metric space, and each voter prefers alternatives that are closer to her to ones that are further away. In this setting, it is often desirable to select an alternative that minimizes the sum of distances to the voters, i.e., the utilitarian social cost, or other similar measures of social cost. However, common voting rules operate on voters' preference rankings and therefore may be unable to identify an optimal alternative. A relevant measure of the quality of a voting rule is then its distortion, defined as the worst-case ratio between the performance of an alternative selected by the rule and that of an optimal alternative. Thus, distortion measures how good a voting rule is at approximating an 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 they form a metric space. The goal of the presented paper was to quantify the distortion of well-known voting rules. We established a lower bound on the distortion of any deterministic voting rule. Next, we show that the distortion of positional scoring rules cannot be bounded by a constant, and for several popular rules in this family distortion is linear in the number of alternatives. On the other hand, for Copeland and similar rules the distortion is bounded by a factor of 5. These results hold both for the sum of voters' cost and the median voter cost. For Single Transferable Vote (STV), we obtain an upper bound of O(ln m) with respect to the sum of voters' costs, where m is the number of alternatives, as well as a lower bound of Omega(sqrt(log m)); thus, STV is a reasonable, though not a perfect rule from this perspective. Our results for median voter cost extend to more general objective functions.

---