Approval-based elections and distortion of voting rules

We consider elections where both voters and candidates can be associated with points in a metric space and each voter prefers candidates that are closer to him/her to those that are further away. Such a metric space can be e.g. an issue space of their political views. We will measure the quality of particular candidates and of particular voting rules. We will present two significantly different approaches for this purpose. Intuitively, we could either assume that the optimal candidate is the one that minimizes the sum of distances to the voters---this approach is called distance-based, or that the optimal candidate is the one that is approved by the widest possible range of voters---this approach is called acceptability-based. In the acceptability-based approach we assume that each voter is a center of a sphere and each candidate is inside the sphere if and only if is acceptable for the voter. For given election instance and voting rule, we introduce the term ‘distortion’ as a comparison between the quality of the elected candidate and the optimal one. The distance-based distortion has been already studied in the literature and worst-case upper bounds for a number of common rules have been found. We will complement these results by the detailed analysis of Approval Voting, and we will show that its distortion strongly depends on adopted assumptions about the approval sets. The acceptability-based approach is a new idea, not studied in literature yet. In this part we will present the lower bounds for each ranking-based rule and upper bounds for a number of known rules, such as Plurality, Borda, k-approval, Veto, Copeland, Ranked Pairs and STV.