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

M. T. Godziszewski, P. Batko, P. Skowron, P. Faliszewski
AAAI 2021
Abstract
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., (AAAI-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 depends on the exact protocol for choosing the approved candidates.

Experiments:

Election type Culture Candidates Voters Instances Parameters
Approval Euclidean 2D {100} {100} 2000 More details in Visualization and Discussion sections. Point generation models: a) uniform square, b) asymmetric Gaussian Model with two centres, c) overlapping squares. Voters \& candidates types: 1.1) Fixed voters’ radii; zero candidate radii 1.2) Fixed voters’ ballot length; zero candidate radii 2.1) Randomly selected voters’ radii from [0,3]; zero candidate radii 2.2) Randomly selected voters’ ballot length from {1,…,100}; zero candidate radii 3) (Only for asymmetric model): Voters as above; candidate radii 1 for noncenter-going gaussian side and 1.5 for center-going gaussian side