Dear all,

The next talk in the Computational Social Choice Seminar at the ILLC will take place next Monday. Jérôme Lang (Paris) will speak about communication issues for the rule of single transferable vote.

As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.

All the best, Ulle

-------------------------------------------------------------------------

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