Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

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

Speaker: Jérôme Lang (Paris)
Title: Single Transferable Vote: Incomplete Knowledge and Communication Issues
Date: Monday 18 March 2019
Time: 15:00
Location: Room F0.20, Science Park 107, Amsterdam

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/.

Please note that this newsitem has been archived, and may contain outdated information or links.