The Metric Distortion of Multiwinner Voting

We extend the recently introduced framework of metric distortion to multiwinner voting. In this framework, n agents and m alternatives are located in an underlying metric space. e exact distances between agents and alternatives are unknown. Instead, each agent provides a ranking of the alternatives, ordered from the closest to the farthest. Typically, the goal is to select a single alternative that approximately minimizes the total distance from the agents, and the worst-case approximation ratio is termed distortion. In the case of multiwinner voting, the goal is to select a commi ee of k alternatives that (approximately) minimizes the total cost to all agents. We consider the scenario where the cost of an agent for a commi ee is her distance from the q-th closest alternative in the commi ee. We reveal a surprising trichotomy on the distortion of multiwinner voting rules in terms of k and q: e distortion is unbounded when q k/3, asymptotically linear in the number of agents when k/3 < q k/2, and constant when q > k/2. Anshelevich et al. [2015] built on this idea to propose the metric distortion framework, in which agents and alternatives are embedded in an underlying metric space, and the cost of an agent for an alternative is the distance between them. An agent still ranks the alternatives, but now in a non-decreasing order of their distance from her. Instead of maximizing the social welfare, the goal is now to minimize the social cost (the total cost of the agents). Like in the utilitarian case, scholars have analyzed the metric distortion of prominent voting rules [Skowron and Elkind, 2017; Goel et al., 2017; Munagala and Wang, 2019; Kempe, 2020b] and identified rules with optimal metric distortion [Gkatzelis et al., 2020] . For a detailed overview, we refer the reader to the survey by Anshelevich et al. [2021] . e goal of our work is to extend the metric distortion framework to multiwinner voting, where the objective is to select a subset of k alternatives (commi ee) for a given k > 1. To the best of our knowledge, the only prior works to address multiwinner voting with general metric costs are those of Goel et al. [2018] and Chen et al. [2020]. Both focus on a model in which an agent's cost for a commi ee is the sum of her distances to the alternatives in the commi ee. In a sense, this assumes that an agent cares equally about all the alternatives chosen in the commi ee. However, in many applications, an agent may care only about a few alternatives in the commi ee, typically the ones she prefers more. For example, when parliament members are chosen in a political election, each voter may associate with just one (or a few) of the elected candidates as her representative(s). Similarly, if a city builds parks at multiple locations, each resident may only be able to access a few parks closest to her. Motivated by these applications, we consider the case where an agent's cost for a commi ee of k alternatives is her distance to the q-th closest alternative in the commi ee, for a given q k.