Abstract (EN)

Single Transferable Vote (STV) is of particular interest for voting, for cognitive reasons (it is easy to understand) and normative reasons (it is clone-proof). However, assuming that voters have to report full rankings sometimes makes it highly unpractical. We study single-winner STV from the point of view of communication. In the first part of the paper, we assume that voters give, in a single shot, their top k alternatives; we define a version of STV that works for such k-truncated votes, and we evaluate empirically (on randomly generated profiles, and on real data) the extent to which it approximates the standard STV rule. In the second part of the paper, we start from the protocol used by Conitzer and Sandholm (2005) for assessing the communication complexity of STV. We give an improvement of it, and then we study empirically the average communication complexity of these protocols, based on the one hand on randomly generated profiles, and on the other hand on real data. We also first give a polynomial-time computable characterization of possible winners at each step of this protocol. Our conclusion is that STV needs, in practice, much less information than in the worst case