Next: Heat Diffusion Up: 1997 UMCP High School Programming Contest Previous: Internet Routing

# Voting Paradox

from http://www.ccrc.wustl.edu/~lorracks/dsv/diss/
by Lorrie Cranor

The paradox of voting was discovered over 200 years ago by M. Condorcet, a French mathematician, philosopher, economist, and social scientist. However, it received little attention until Duncan Black explained its significance in a series of essays he began in the 1940s. The importance of the voting paradox was not fully realized until several years after Kenneth Arrow published Social Choice and Individual Values in 1951, which contained his General Possibility Theorem. The essence of this theorem is that there is no method of aggregating individual preferences over three or more alternatives that satisfies several conditions of fairness and always produces a logical result.

For this problem, you must write a program that evaluates different voting strategies on voter preferences. We consider just the case of 3 candidates, and each vote orders the candidates according to their preferences. There are a total of 5 schemes you need to consider:

• plurality winner - there is one ballot, and each voter casts their vote for their favorite candidate. Whoever gets the most votes wins, even if they don't get a majority of the votes cast.
• exhaustive ballot - On each ballot, each voter casts their vote for their favorite candidate (that is on the ballot). The candidate who gets the fewest votes is eliminated, and the survivers move on to the next round of voting. For three candidates, there will be just two ballots.
• 1&2 primary - Candidates 1 & 2 face off in a primary ballot. Whoever wins goes on to face candidate 3 in a second ballot. Whoever wins that vote wins the election.
• 1&3 primary - Candidates 1 & 3 face off in a primary ballot. Whoever wins goes on to face candidate 2 in a second ballot. Whoever wins that vote wins the election.
• 2&3 primary - Candidates 2 & 3 face off in a primary ballot. Whoever wins goes on to face candidate 1 in a second ballot. Whoever wins that vote wins the election.

Note that in all votes, each voter casts their vote for the candidate they like most who is on the ballot (as a result of the voting paradox, this doesn't always maximize the chance that a candidate they like will be elected).

You do not need to worry about election ties; none will occur in the data sets you will be tested on.

## Input Format

Your input will be a series of voter preferences, each consisting of 3 integers on a line. These numbers consist of the voter's first, second and third choice; each choice will be a number in the range 1-3. If the first number is 0, it means that this set of voter preferences is complete, and you should print the results for this set and then read in another set. If the first number is -1, it indicates end of input. This set of voter preferences is complete and is the last set of voter preferences; you should print the results and terminate.

## Output Format

For each set of voter preferences, you should print a header, the plurality election winner, the exhaustive ballot winner, and the winner if two of the candidates are paired in a primary first. The sample output shows the appropriate format, but don't worry about the number of spaces.

## Example

Input: Output:
```1 2 3
1 2 3
1 2 3
2 1 3
2 3 1
3 1 2
0 0 0
1 3 2
1 3 2
1 3 2
1 2 3
1 3 2
3 2 1
2 3 1
2 3 1
2 3 1
3 2 1
3 2 1
2 3 1
-1 -1 -1
```
```-------- election  1
plurality winner  1
exhaustive ballot  1
12 primary  1
13 primary  1
23 primary  1
-------- election  2
plurality winner  1
exhaustive ballot  2
12 primary  3
13 primary  3
23 primary  3
```

Input Output

## Our solution

Next: Heat Diffusion Up: 1997 UMCP High School Programming Contest Previous: Internet Routing

Bill Pugh
Mon Mar 17 14:34:34 EST 1997