AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI   Info

AG Audience

English

30 Minutes

In this project, we are focusing on multi-winner elections. We consider the problem of selecting a committee of k alternatives among m alternatives, based on the ordinal rank list of voters. Our focus is on the case where both voters and alternatives lie on a metric space—specifically, on the real line—and the objective is to minimize the additive social cost. The additive social 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 upper bounds of 1 + √2 ≈ 2.41 and 7/3 ≈ 2.33 distortions for k = 2 and k = 3, respectively, and we show that these bounds are tight. Furthermore, we generalize this rule, showing that it maintains a distortion of roughly 7/3 for general k-winner elections. We also establish lower bounds on the achievable distortion based on the parity of k and for both small and large committee sizes.

Ina Geisler

+49 681 9325 1802

--email hidden

Zoom

passcode not visible

logged in users only