Single Transferable Vote: Incomplete Knowledge and Communication Issues

M. Ayadi, N. Ben Amor, J. Lang, D. Peters
AAMAS 2019
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 paper, 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 is NP-complete when $k\geq 2$. In the second part, we consider interactive communication protocols for STV. Building on a protocol proposed by Conitzer and Sandholm (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.

Experiments:

Election type Culture Candidates Voters Instances Parameters
Ordinal Impartial Culture {7} {100} 1000 None
Ordinal Mallows {7} {100} 1000 {0.7, 0.8, 0.9, 1}
Ordinal PrefLib {10} {5000} None https://www.preflib.org/dataset/00014
Ordinal PrefLib {12} {3662} None https://www.preflib.org/dataset/00001
Ordinal PrefLib {10} {43} None https://www.preflib.org/dataset/00007
Ordinal PrefLib {9} {548} None https://www.preflib.org/dataset/00008
Ordinal PrefLib {7} {327} None https://www.preflib.org/dataset/00002
Ordinal PrefLib {12} [10-1500] 1000 https://www.preflib.org/dataset/00001
Ordinal Impartial Culture {5} {30, 500} 1000 None
Ordinal Mallows {5} {30, 500} 1000 {0.7, 0.8, 0.9, 1}