An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections

We study approval-based committee elections for the case where the voters' preferences come from a 2D-Euclidean model. We consider two main issues: First, we ask for the complexity of computing election results. Second, we evaluate election outcomes experimentally, following the visualization technique of Elkind et al. (2017) . Regarding the first issue, we find that many NP-hard rules remain intractable for 2D-Euclidean elections. For the second one, we observe that the behavior and nature of many rules strongly depend on the exact protocol for choosing the approved candidates. all the domain restrictions considered by Elkind and Lackner (2015) are one-dimensional). We check if these polynomial-time results can be extended to the two-dimensional case. We consider voting rules that seek committees of different types. In particular, we consider Multiwinner Approval Voting (AV), which focuses on individual excellence, Proportional Approval Voting (PAV), Phragmén's Sequential rule (Phr), and Rule X, which focus on proportionality, and Approval Chamberlin-Courant (CC), which focuses on diversity. Additionally, we also consider Minimax Approval Voting (MAV), which is based on the egalitarian principle. Approval-Based Euclidean Elections. Briefly put, in a Euclidean model each candidate and each voter is represented as his or her ideal point, i.e., a point in some Euclidean space R , whose coordinates are interpreted as a given candidate's or voter's positions on some issues (for example, in a two-dimensional model these two issues may correspond to the extents to which an individual supports personal and economic freedom). To derive the voters' approval sets, we use the following two principles: 1. In the voter-range model, if a voter approves some candidate then he or she also approves all