Fair Division in Theory and Practice
[CSE/Poli Sci 245A (Spring 2015)]
How manupulable are voting systems?

As you learned from the Gibbard-Satterthwaite theorem, it can be advantageous for a voter to vote strategically, expressing preferences in an election that are insincere.

But how manipulable are elections? In this lab you will simulate all possible elections, and within each, all attempts at manipulation. You will measure how often the manipulation is successful, thereby establishing a measure of a voting system's manipulability.

Here we shall look at plurality, Borda, and single transferable vote.

Instructions

• Consider an election scenario with 10 voters and, 3 alternatives. Each voter's sincere prefereces is some total ordering over the alternatives.
  • There are thus 6 possible preference lists for any given voter.
  • There are thus 6¹⁰ possible elections.
• For each election described above, you can compute the outcome if every voter votes sincerely.
• You can also run an election where some number of voters (from 1 to 10 of them) express a strategic ordering of the alternatives in lieu of their sincere ordering.
• You can measure whether, for a given voter, the use of a strategic ordering obtained a better (or worse) outcome for that voter.

Using the approach sketched above, simulate all possible elections and determine how often manipulation is successful. Make your voting rule abstract, so that you can experiment with plurality, Borda, and single transferable vote.

To help you with managing combinations of things, code is posted on piazza and here for efficiently iterating over combinations of sets, lists, etc. Place those Java files in a combo package in your eclipse project.

If 10 voters proves too expensive to compute, then try a smaller number of voters until the computation becomes managable.