18 March 2019, Computational Social Choice Seminar, Jérôme Lang

Abstract

Single Transferable Vote (STV) is used in large political elections around the world. It is easy to understand and has desirable normative properties, such as clone-proofness. However, voters need to report full rankings, which can make it less practical than plurality voting. We study ways to minimize the amount of communication required to use single-winner STV. In the first part of the talk, voters are assumed to report their top-k alternatives in a single shot. We empirically evaluate the extent to which STV with truncated ballots approximates STV with full information. We also study the computational complexity of the possible winner problem for top-k ballots. For k = 1, it can be solved in polynomial time, but it is NP-complete when k > 1. In the second part, we consider interactive communication protocols for STV. Building on a protocol proposed by Conitzer and Sandholm in 2005, we show how we can reduce the amount of communication required in practice. We then study empirically the average communication complexity of these protocols, based on randomly generated profiles, and on real-world election data. Our conclusion is that STV needs, in practice, much less information than in the worst case. (This is joint work with Manel Ayadi, Nahla Ben Amor, and Dominik Peters.)

For more information on the Computational Social Choice Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.