Dear all,

the Institute for Information Systems cordially invites you to
the following
talk:

=============================================================================

Speaker: Piotr
Skowron

TU Berlin, Research
Group: Algorithmics and Computational
Complexity

http://www.akt.tu-berlin.de/menue/team/skowron_piotr/

=============================================================================

DATE: Monday, November13, 2017

TIME: 16:00 c.t.

VENUE: Seminarraum Goedel, Favoritenstr.
9-11, EG, Zugang vom Innenhof, RoomNo:
HB EG 10

=============================================================================

TITLE:

Approximating
Optimal Social Choice under Metric Preferences

=============================================================================

Abstract:

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.

=============================================================================

With
kind support of the Vienna Center for Logic and Algorithms
(VCLA)