Complexity of some multi-winner election rules over two-dimensional Euclidean single-peaked preferences

Prelegent(ci)

Michał Godziszewski

Afiliacja

Instytut Informatyki, UW

Termin

5 marca 2020 10:15

Pokój

p. 4050

Seminarium

Seminarium „Gry, mechanizmy i sieci społeczne”

---

For a given election E=(V,C) the preferences \{\leq_i\}_{i \in V} of voters are single-peaked when, intuitively speaking, a single issue dominates their formation. This single dominating issue is normally represented by a one-dimensional real axis and each voter is characterized by a single point on this axis. The misrepresentation function for a fixed voter is then a function of a single variable defined on that axis and the single-peakedness of preferences implies that this function has exactly one local minimum, or in other words, the preference of a given voter can be read-off from the distances of the points representing the candidates from this given voter. In the case of single-peaked profiles some computational problems have turned out to allow for more efficient solving strategies than in the general case. In particular, the study of the computational complexity of voting rules with NP-hard winner-determination problem shows that for all Condorcet-consistent ones the winner-determination problem becomes polynomial-time solvable if we restrict ourselves to single-peaked profiles. Further, it has been shown that in many instances the winner-determination problem for methods of proportional representation becomes easier as well. Since the definition of single-peakedness easily generalizes to higher dimensions, a natural move to make is to consider the preferences over two-dimensional Euclidean plane instead of Euclidean line. Intuitively, this corresponds to scenarios where candidates and voters can be represented by points in the real plane and the preference order of a given voter is monotonically determined by her Euclidean distances from the candidates. In other words, $\mathbb{R}^2$-Euclidean single-peaked preferences are the ones where voters and candidates' positions over 2 issues dominates the formation of the profile. This scenario can be arguably found in many real-life situations. We thus study the multi-winner voting methods of proportional representation for electorates that are single-peaked over a Euclidean real plane. In particular, we consider the Borda, k-Approval and Approval methods and investigate their complexity w.r.t. committee-scoring scenarios. We show that they are NP-complete. We essentially use the idea from Lewenberg, Lev and Rosenschein who studied district-based elections, where in the context of vulnerability to gerrymandering, a geographically-based manipulation problem is being introduced, where voters must vote at the ballot box closest to them. They proved that the problem is NP-complete in the worst case, modifying the reduction from the Planar X3C by adding geometrical constraints to the instances of the reduced problem and by using the reduction of the Planar 1-3-SAT by Dyer and Frieze from their work on the complexity of planar restrictions of three-dimensional matching. During the talk I will introduce the known results on the single-peaked preferences, explain the ideas of the modified planar version of the NP-complete problems, and demonstrate how we use them. This is a joint work-in-progress with Piotr Faliszewski.

---