Theory Lunch This Week (11/14, 12:00, SAL 322)

[Grayson York]

Hi all,

Sorry for the last minute message. This week we will have what is hopefully our final theory lunch in SAL 322 before moving to the new building. Fatih will be speaking about some work that he has done jointly with David Kempe with the following title and abstract:

Title: k-Approval Veto: A Spectrum of Voting Rules Balancing Metric Distortion and Minority Protection

Abstract. In the context of single-winner ranked-choice elections between m candidates, we explore the tradeoff between two principles that are essential to constitutional democracies: the majority principle (maximizing the social welfare) and the minority principle (safeguarding minority groups from overly bad outcomes). To measure the social welfare, we use the well-established framework of metric distortion subject to various objectives: utilitarian (i.e., total cost), \alpha-percentile (e.g., median cost for \alpha = 1/2), and egalitarian (i.e., max cost). To measure the protection of minorities, we introduce the k- Droop minority criterion, which requires that if a sufficiently large (parametrized by k) coalition T of voters ranks all candidates in S at the bottom (in any order), then none of the candidates in S should win. The parameter k allows the criterion to interpolate between the minimal requirement that the winner must not be ranked last by a strict majority (when k=1) and the maximal requirement that the winner must be in the proportional veto core (when k = m - 1). The highest k for which the criterion is satisfied provides a well-defined measure of minority protection between k=0 (no protection) and k=m - 1 (the strongest protection possible to guarantee). Our main contribution is the analysis of a recently proposed class of voting rules called k-Approval Veto, offering a comprehensive range of trade-offs between the two principles. This class spans between Plurality Veto (for k=1) --- a simple rule achieving optimal metric distortion --- and Vote by Veto (for k=m) which picks a candidate from the proportional veto core. We show that k-Approval Veto has minority protection at least k-1, and thus, it accommodates any desired level of minority protection via the parameter k. However, this comes at the price of lower social welfare. For the utilitarian objective, the metric distortion becomes 2min(k+1, m)-1, i.e., increases linearly in k. For the \alpha-percentile objective, the metric distortion is the optimal value of 5 for \alpha \ge k/(k+1) and unbounded for \alpha < k/(k+1), i.e., the range of \alpha for which the rule achieves optimal distortion becomes smaller. For the egalitarian objective, the metric distortion is the optimal value of 3 for all values of k, i.e., there is no trade-off between the egalitarian objective and minority protection. Thus, our analysis of k-Approval Veto also establishes that the metric distortion of Plurality Veto is optimal with respect to all three objectives above, i.e., not only for the utilitarian objective as previously shown. 

TL;DR: We use the metric distortion framework to analyze a spectrum of voting rules called k-Approval Veto, which balances the majority and minority principles as one sees fit via the parameter k.

[Grayson York]

Hi all,

please join at the following zoom link:

https://usc.zoom.us/j/96253014755?pwd=ih6OcTRsZ7PoOXNak9xT1xBuFqnxok.1

Thanks,

G