As part of my dissertation, I set out to research on the manipulability of "Single Trasferrable Vote" voting systems and the complexity to compute a valid manipulation.
For many voting methods, it is NP-hard to compute a successful manipulation. However the research provided results to support that the NP-hardness only bounds the worst-case complexity. In fact, the research conducted supported original ideas suggested by Toby Walsh and the theoretical results suggest that a successful manipulation may often be much easier in practice.
As part of my research, I implemented an algorithm capable of performing a manipulation on the Instant Runoff Vote and the Borda vote. For each, I varied my test cases with uniformly random data whilst keeping the number of candidates in the election fixed but altering the number of total agents and the weight of the manipulators (the weight of the mannipulator refers to the number of manipulators we have, we assume every agent carries a weight of 1, therefore a total weight of 5 means we required 5 manipulating agents).
The algorithm implemented was updated for PHP and put through its paces (PHP doesn't like deep recursion as it creates such an overhead, so I had to strip it to its barebones). Overall, the results were fantastic. I demonstrated that with just one single manipulating agent you could completely alter the outcome of the election even elections of 100,000+ ballots. Taking into account the STV is used by many Goverment bodies such as New Zeleand, Scotland, Ireland and Malta.
As expected, the probability of a successful manipulation decreases as the number of ballots and candidates increases but even with 8 candidates and 100,000 ballots - there is still a high chance of a successful manipulation:
If you have any comments, queries or want to get some extra information about the manipulation algorithm or any of the Single Transferable Vote methods implemented, just leave a comment below. Alternatively you can let me know by mentioning #ALJTMedia on Twitter or leaving a comment on our Facebook or Google+ page.