Project 2: Election

Concentrations of voters of similar political inclination can dilute these voters' electoral strength because they will elect a member for their district by a wide margin. This is often referred to as a ``natural'' disadvantage for groups that tend to cluster together, e.g., in large cities.

Less natural (but still very real) dilutions of voting strength can result from gerrymandering of voting districts. Deliberate manipulation of the populations of districts can generate aggregate voting results that favor one party, typically the party in charge of setting electoral boundaries.

Threeland is a newly independent country that is deciding how to design its electoral system. In Threeland, where 3 is the national lucky number, the electoral commission (consisting of three of the country's top problem-solvers, graduates of COMS-4444) has proposed the following scheme. The country's house of representatives will contain 3⁵=243 members, elected by 3⁴=81 districts: each district will elect three members.

Elections within a district start with each of p parties nominating 3 candidates in ranked order. A voter chooses one party to vote for. All votes are tallied, and any party achieving more than 1/4 of the vote gets their top-ranked candidate elected, and 1/4 of the vote-count is subtracted from that party's running vote count. This process is repeated, with parties' lower-ranked candidates potentially being elected, until no party's running total exceeds 1/4 of the vote. At most 3 candidates can be elected in this initial step (why?).

If fewer than three candidates have been selected, then the party with the highest remaining running total elects their highest-ranked remining candidate, and their running total is set to zero. While there are still fewer than three candidates elected, this process is iterated.

Some possible scenarios in a 2-party election:

Party 1 vote %	Party1 seats	Party 2 seats
20	0	3
30	1	2
40	1	2
49	1	2
51	2	1
60	2	1
70	2	1
80	3	0

With three or more parties, things get a bit more complicated, but any party achieving more than a quarter of the vote is guaranteed a seat.

Being a brand new election system, it is not clear to the leaders of Threeland whether this proposed system is truly robust to gerrymanders, or to what extent it ameliorates the problem of dilution of city voters' votes. They suspect it might still be vulnerable to manipulation, but less so than systems in which districts elect just one member. The electoral commission has therefore tasked you, the valiant 3-member teams of COMS-4444, with quantifying the benefits and vulnerabilities of their proposed system relative to a system in which there are 243 single-member districts.

To evaluate the system you will be given a map of Threeland, which is shaped like an equilateral triangle (what else?). You will also be given some recent polling data showing the locations of each of the 333,333 voters and their voting preferences. A voting preference is a tuple of p numbers between 0 and 1, where there are p parties contesting the election. For example, in a 3-party election, Joe's voting preference might be (0.4, 0.5, 0.6). On the day of the election, each party gets a national rating depending on how well it has campaigned. These ratings are also between 0 and 1, and so we might get a rating score R of (0.2,0.3,0.1) for a particular election. Joe's vote goes to the party that maximizes the sum of Joe's preferences with R, i.e., the maximum party in the tuple (0.6,0.8,0.7) which is the second party. Note that even though Joe's initial preference was for party 3, the campaign performance was enough to change his vote. In the event of ties, the simulator will break the tie randomly.

The locations of voters on the map will not be random. In fact, one of the initial tasks in this project will be for each group to construct two maps that give locations and voting preferences of the 333,333 citizens of Threeland. Note that the distribution does not have to be random, or even balanced. One map should be for a two-party election, and one map should be for a three-party election. Your maps should be based on some kind of clustering that you find interesting, either because it is realistic (how might you base it on real-world data?), or has some special mathematical properties.

According to the laws of Threeland, districts are polygons with the following properties: a) The district has no more than 3²=9 sides. (If this were unlimited, you could carve out districts that included specific voters.) b) Districts do not overlap. c) Every voter belongs to exactly one district. d) No district's population varies from the mean district population by more than 10%.

You get to simulate a variety of district choices, and to evaluate election results under a variety of campaign performance numbers. We'll provide a simulator that validates a set of district boundaries, and executes an election for a given campain performance R. You get to choose the scenarios that are simulated, with the ultimate goal of preparing a two-page report (which will be part of your final project report) summarizing your findings for the electoral commission of Threeland.