Condorcet discovered that, among voters with transitive preferences (meaning that if a voter prefers x to y and y to z, he or she will prefer x to z**), majority preferences between pairs of candidates may be**
intransitive. This means that among candidates x, y, and z**, it is possible for a majority of voters to prefer** x to y, y to z, and z to x, and thus a Condorcet winner, who outperforms each alternative **in a pairwise**
election, may not exist. The result that the pairwise preferences of the aggregate of rational voters may be irrational is known as the Condorcet paradox.

Beyond the applications in social sciences, in more recent times voting has also been used in many interesting problems in computation theory, including rank aggregation in search engines [39, 37] and collaborative filtering [38]. Rank aggregation can also occur when one wishes to select documents or other results based on multiple criteria [87]. Some of these applications will be addressed in the next section.

Unfortunately, it is now known that no voting system is perfect, and three major results show the weaknesses inherent in voting. Arrow's impossibility theorem [5] shows that in any election with as few as three candidates, no voting system can convert the ranked preferences of a group of voters into a community-wide ranking meeting a reasonable set of criteria: unrestricted domain, **meaning the aggregation is deterministic**
and complete for all possible profiles of the voters, nondictatorship, meaning that no single voter should be able to single-handedly determine the outcome, Pareto efficiency, meaning that if every voter prefers a candidate to another, this order must also hold in the aggregation, and **independence of irrelevant alternatives,**
meaning that changes to the voters' rankings of irrelevant candidates should not change the outcome for the candidate in question.

Beyond the problems of fairness, election systems are often subject to misuses, where the outcome of the election is unfairly affected by some of the voters, the chair of the election, or outside agents whom attempt to influence the voters. One form of misuse is when a voter **reports preferences that are insincere** to his or her true preferences for his or her own benefit, or when a **group of voters conspire to collectively** affect the outcome of the election. This is called manipulation, and is often disastrous for the system as a whole. In particular, a common problem in many election systems is the **design that encourages voters to**
bury their 2nd **desired candidate, who may also be popular, among their preference list, giving their favorite**
candidate a more significant advantage. Done as a whole in the election, this distorts the true preferences of the participants. Two important results showing this weakness are **the Gibbard-Satterthwaite theorem [6, 7]** and Duggan-Schwartz theorem [22], which show that eliminating the possibility of manipulation is impossible for any reasonable election system.

The Gibbard-Satterthwaite theorem [6, 7] shows that every election of three or more candidates that chooses a single winner must either be dictatorial (i.e., where a single individual can choose the winner), nonsurjective (i.e., where some candidate cannot win under any circumstances), or is theoretically vulnerable to tactical voting in some cases. Tactical voting occurs when a voter or coalition of voters with full knowledge of the other voters' preferences has an incentive to vote contrary to their true preferences. Since neither of the first two properties are acceptable in any reasonable election system, this can be interpreted as all elections are subject to manipulation. The Duggan-Schwartz theorem [22] shows the same result with elections that elect a nonempty set of winners.

We illustrate the problem of manipulation with the following example. In the election system Veto, the lowest candidate in each preference profile is given one veto, and the candidate with the fewest vetoes wins. Consider a system of three candidates, x, y, and z**, and, initially, 100 voters. 40 initial voters have** preferences expressed by y ≻ z ≻ x, 35 have preferences x ≻ z ≻ y, and 25 have preferences y ≻ x ≻ z. A
total of 22 manipulators have sincere preferences expressed by x ≻ y ≻ z. In an honest election, x **would** receive 40 vetoes, y 35 vetoes, and z 47 vetoes, making y **the winner. In this case, the 22 manipulators can** collectively make x the winner if 6 of the manipulators submit the preference x ≻ z ≻ y. Because x **would**
not be the winner of an honest Veto election, such manipulations may **produce a sub-optimal outcome. In**