On the Distortion of Multi-Winner Elections on the Line Metric

We consider the problem of selecting a committee of 𝑘 alternatives among 𝑚 alternatives, based on the ordinal preferences of voters. Our focus is on the case where both voters and alternatives lie on a metric space-specifically, on the line-and the objective is to minimize the social additive cost. Social additive cost is the sum of the costs for all voters, where the cost for each voter is defined as the sum of their distances to each member of the selected committee. We propose a new voting rule, the Polar Comparison Rule, which achieves an upper bound of 1 + √ 2 ≈ 2.41 distortion for 𝑘 = 2, and we show that this bound is tight. Furthermore, we generalize this rule and show that it maintains a distortion of 2.41 for even committee sizes and 2.41 + (2-√ 2)/𝑘 for odd committee sizes. We also establish lower bounds on the distortion based on the parity of 𝑘 and for both small and large committee sizes.